|

General

# Author Problem Lang Verdict Time Memory Sent Judged
63236828 Practice:
Roohi
1249D2 - 13 GNU C++14 Accepted 264 ms 16756 KB 2019-10-23 15:30:38 2019-10-23 15:30:39

→ Source
#include<bits/stdc++.h>
using namespace std;

typedef long long int lli;
typedef unsigned long long int ulli;
typedef pair<int,int> pii;
typedef priority_queue< int, vector< int >, greater< int > >  minHeap;

#define ones(x) __builtin_popcount(x)
#define onesl(x) __builtin_popcountl(x)
#define onesll(x) __builtin_popcountll(x)

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define scn(n) scanf("%d",&n)
#define scnll(n) scanf("%lld",&n)
#define scn2(n,m) scanf("%d%d",&n,&m)
#define scn3(n,m,w) scanf("%d%d%d",&n,&m,&w)
#define scn2ll(n,m) scanf("%lld%lld",&n,&m)
#define atoz(v) v.begin(),v.end()
#define ratoz(v) v.rbegin(),v.rend()
#define Fill(a,v) memset(a,v,sizeof(a))
#define fi first
#define se second
#define inf 1e9
#define pi acos(-1.0)
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define mod 1000000007
#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define bug(x) cerr << __LINE__ << " says: " << #x << " = " << (x) << "\n"

int Set(int N,int pos)
{
return N=N | (1<<pos);
}
int reset(int N,int pos)
{
return N = N & ~(1<<pos);
}
bool check(int N,int pos)
{
return (bool)(N & (1<<pos));
}

{
return (x%mod + y%mod)%mod;
}
inline int submod(int x,int y)
{
return (x%mod - y%mod + mod)%mod;
}
inline int mulmod(int x,int y)
{
return (x%mod *1LL* y%mod)%mod;
}
{
}

template<typename T>
void we_r_done(T mssg)
{
cout<<mssg;
exit(0);
}

const int N = 2e5 + 3;

vector<pii>B[N];
vector<int>E[N];
bool gone[N];

int main()
{
///freopen("output.txt","w",stdout);
///freopen("input.txt","r",stdin);

///FastIO;

int n,k;
scn2(n,k);

for(int i=1; i<=n; i++){
int l,r;
scn2(l,r);

B[l].pb({r,i});
E[r].pb(i);
}

priority_queue<pii>pq;
set<int>now;
vector<int>res;

for(int p=1; p<N; p++){

for(pii x : B[p]){
pq.push(x);
now.insert(x.se);
}

while(now.size()>k){

pii x = pq.top();
pq.pop();

if(gone[x.se]) continue;

if(now.find(x.se) != now.end()){
now.erase(x.se);
res.pb(x.se);
}
}

for(int x : E[p]){
gone[x] = true;
if(now.find(x) != now.end()){
now.erase(x);
}
}
}

printf("%d\n",res.size());
for(int idx : res) printf("%d ",idx);

return 0;

}

///sin and cos expect input in radians not degrees. so use , sin(degrees * pi / 180)
///using bs = bitset<MX>; // how many distinct number can be form?
///sort(atoz(v), [](const data x, const data y){return (x.a==y.a?x.b>y.b : x.a<y.a);});


?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
?
?