#include<bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target ("sse4")
using namespace std;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define MEM(x,a) memset((x),a,sizeof((x)))
#define F first
#define S second
#define L (idx*2)
#define R (L+1)
#define imx INT_MAX
const long long MOD = (long long)(1e9+7);
const long long MMX = (long long)(1e18);
typedef long long LL;
typedef pair<int,int> pii;
int n,k,N,cn[100005],seq[800010],pr,mx,ss;
set<int>s;
vector<int>puu[100005];
map<int,int>mp;
struct node
{
int l,r;
}ev[100005];
vector<int>sor;
priority_queue<pii>pq;
void seq_up(int st,int ed,int idx,int pos,int val)
{
int mid=(st+ed)/2;
if(pos<st||pos>ed)return;
if(st==ed)
{
seq[idx]=max(seq[idx],val);
return;
}
seq_up(st,mid,L,pos,val);
seq_up(mid+1,ed,R,pos,val);
seq[idx]=max(seq[L],seq[R]);
return;
}
int seq_mx(int st,int ed,int idx,int ll,int rr)
{
int mid=(st+ed)/2;
if(rr<st||ll>ed)return 0;
if(ll<=st&&rr>=ed)return seq[idx];
return max(seq_mx(st,mid,L,ll,rr),seq_mx(mid+1,ed,R,ll,rr));
}
int main()
{
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d %d",&ev[i].l,&ev[i].r);
if(mp[ev[i].l]==0)
{
sor.pb(ev[i].l);
mp[ev[i].l]=1;
}
if(mp[ev[i].r]==0)
{
sor.pb(ev[i].r);
mp[ev[i].r]=1;
}
}
sort(all(sor));
for(int i=0;i<sor.size();i++)
{
mp[sor[i]]=i+1;
}
N=sor.size();
sor.clear();
for(int i=1;i<=n;i++)
{
ev[i].l=mp[ev[i].l];
ev[i].r=mp[ev[i].r];
pq.push({ev[i].l,i});
}
while(!pq.empty())
{
pr=pq.top().S;
pq.pop();
mx=seq_mx(1,N,1,ev[pr].r,N);
seq_up(1,N,1,ev[pr].l,mx+1);
cn[pr]=mx+1;
}
ss=imx;
for(int i=1;i<=n;i++)
{
if(cn[i]>=k)
{
ss=min(i,ss);
}
puu[cn[i]].pb(i);
}
if(ss==imx)
{
printf("-1");
}
else
{
sor.pb(ss);
for(int i=n;i>=k;i--)
{
for(int j=0;j<puu[i].size();j++)
{
s.insert(puu[i][j]);
pq.push({-ev[puu[i][j]].l,puu[i][j]});
}
}
for(int i=k-1;i>0;i--)
{
for(int j=0;j<puu[i].size();j++)
{
s.insert(puu[i][j]);
pq.push({-ev[puu[i][j]].l,puu[i][j]});
}
while(-pq.top().F<ev[ss].r)
{
s.erase(pq.top().S);
pq.pop();
}
ss=*(s.begin());
sor.pb(ss);
}
sort(all(sor));
for(int i=0;i<sor.size();i++)
{
printf("%d\n",sor[i]);
}
}
}
Compilation message
event2.cpp: In function 'int main()':
event2.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int i=0;i<sor.size();i++)
| ~^~~~~~~~~~~
event2.cpp:106:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for(int j=0;j<puu[i].size();j++)
| ~^~~~~~~~~~~~~~
event2.cpp:114:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for(int j=0;j<puu[i].size();j++)
| ~^~~~~~~~~~~~~~
event2.cpp:128:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | for(int i=0;i<sor.size();i++)
| ~^~~~~~~~~~~
event2.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
52 | scanf("%d %d",&n,&k);
| ~~~~~^~~~~~~~~~~~~~~
event2.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
55 | scanf("%d %d",&ev[i].l,&ev[i].r);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
201 ms |
21432 KB |
Output is correct |
5 |
Correct |
218 ms |
21288 KB |
Output is correct |
6 |
Correct |
214 ms |
21560 KB |
Output is correct |
7 |
Correct |
217 ms |
21964 KB |
Output is correct |
8 |
Correct |
197 ms |
21164 KB |
Output is correct |
9 |
Correct |
223 ms |
21392 KB |
Output is correct |
10 |
Correct |
218 ms |
21528 KB |
Output is correct |
11 |
Correct |
233 ms |
21960 KB |
Output is correct |
12 |
Correct |
183 ms |
19788 KB |
Output is correct |
13 |
Correct |
199 ms |
20052 KB |
Output is correct |
14 |
Correct |
204 ms |
20264 KB |
Output is correct |
15 |
Correct |
198 ms |
20808 KB |
Output is correct |
16 |
Correct |
185 ms |
18492 KB |
Output is correct |
17 |
Correct |
203 ms |
19084 KB |
Output is correct |
18 |
Correct |
218 ms |
19540 KB |
Output is correct |
19 |
Correct |
202 ms |
18192 KB |
Output is correct |
20 |
Correct |
209 ms |
18868 KB |
Output is correct |
21 |
Correct |
238 ms |
19120 KB |
Output is correct |
22 |
Correct |
217 ms |
18360 KB |
Output is correct |
23 |
Correct |
225 ms |
18972 KB |
Output is correct |
24 |
Correct |
222 ms |
19372 KB |
Output is correct |
25 |
Correct |
253 ms |
18484 KB |
Output is correct |
26 |
Correct |
289 ms |
18648 KB |
Output is correct |
27 |
Correct |
257 ms |
19120 KB |
Output is correct |
28 |
Correct |
187 ms |
20676 KB |
Output is correct |
29 |
Correct |
177 ms |
19428 KB |
Output is correct |
30 |
Correct |
211 ms |
18332 KB |
Output is correct |
31 |
Correct |
184 ms |
18312 KB |
Output is correct |
32 |
Correct |
201 ms |
18356 KB |
Output is correct |
33 |
Correct |
232 ms |
18104 KB |
Output is correct |
34 |
Correct |
198 ms |
21580 KB |
Output is correct |
35 |
Correct |
227 ms |
22448 KB |
Output is correct |
36 |
Correct |
192 ms |
23328 KB |
Output is correct |
37 |
Correct |
228 ms |
19552 KB |
Output is correct |
38 |
Correct |
239 ms |
19648 KB |
Output is correct |
39 |
Correct |
237 ms |
19820 KB |
Output is correct |
40 |
Correct |
257 ms |
20112 KB |
Output is correct |
41 |
Correct |
239 ms |
20272 KB |
Output is correct |
42 |
Correct |
185 ms |
19212 KB |
Output is correct |
43 |
Correct |
235 ms |
19764 KB |
Output is correct |
44 |
Correct |
214 ms |
19832 KB |
Output is correct |
45 |
Correct |
225 ms |
20108 KB |
Output is correct |
46 |
Correct |
216 ms |
20212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
201 ms |
21432 KB |
Output is correct |
5 |
Correct |
218 ms |
21288 KB |
Output is correct |
6 |
Correct |
214 ms |
21560 KB |
Output is correct |
7 |
Correct |
217 ms |
21964 KB |
Output is correct |
8 |
Correct |
197 ms |
21164 KB |
Output is correct |
9 |
Correct |
223 ms |
21392 KB |
Output is correct |
10 |
Correct |
218 ms |
21528 KB |
Output is correct |
11 |
Correct |
233 ms |
21960 KB |
Output is correct |
12 |
Correct |
183 ms |
19788 KB |
Output is correct |
13 |
Correct |
199 ms |
20052 KB |
Output is correct |
14 |
Correct |
204 ms |
20264 KB |
Output is correct |
15 |
Correct |
198 ms |
20808 KB |
Output is correct |
16 |
Correct |
185 ms |
18492 KB |
Output is correct |
17 |
Correct |
203 ms |
19084 KB |
Output is correct |
18 |
Correct |
218 ms |
19540 KB |
Output is correct |
19 |
Correct |
202 ms |
18192 KB |
Output is correct |
20 |
Correct |
209 ms |
18868 KB |
Output is correct |
21 |
Correct |
238 ms |
19120 KB |
Output is correct |
22 |
Correct |
217 ms |
18360 KB |
Output is correct |
23 |
Correct |
225 ms |
18972 KB |
Output is correct |
24 |
Correct |
222 ms |
19372 KB |
Output is correct |
25 |
Correct |
253 ms |
18484 KB |
Output is correct |
26 |
Correct |
289 ms |
18648 KB |
Output is correct |
27 |
Correct |
257 ms |
19120 KB |
Output is correct |
28 |
Correct |
187 ms |
20676 KB |
Output is correct |
29 |
Correct |
177 ms |
19428 KB |
Output is correct |
30 |
Correct |
211 ms |
18332 KB |
Output is correct |
31 |
Correct |
184 ms |
18312 KB |
Output is correct |
32 |
Correct |
201 ms |
18356 KB |
Output is correct |
33 |
Correct |
232 ms |
18104 KB |
Output is correct |
34 |
Correct |
198 ms |
21580 KB |
Output is correct |
35 |
Correct |
227 ms |
22448 KB |
Output is correct |
36 |
Correct |
192 ms |
23328 KB |
Output is correct |
37 |
Correct |
228 ms |
19552 KB |
Output is correct |
38 |
Correct |
239 ms |
19648 KB |
Output is correct |
39 |
Correct |
237 ms |
19820 KB |
Output is correct |
40 |
Correct |
257 ms |
20112 KB |
Output is correct |
41 |
Correct |
239 ms |
20272 KB |
Output is correct |
42 |
Correct |
185 ms |
19212 KB |
Output is correct |
43 |
Correct |
235 ms |
19764 KB |
Output is correct |
44 |
Correct |
214 ms |
19832 KB |
Output is correct |
45 |
Correct |
225 ms |
20108 KB |
Output is correct |
46 |
Correct |
216 ms |
20212 KB |
Output is correct |
47 |
Correct |
2 ms |
2636 KB |
Output is correct |
48 |
Correct |
2 ms |
2636 KB |
Output is correct |
49 |
Correct |
2 ms |
2636 KB |
Output is correct |
50 |
Correct |
2 ms |
2636 KB |
Output is correct |
51 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
52 |
Halted |
0 ms |
0 KB |
- |