#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int n,k,nxL[100005][18],nxR[100005][18];
const int mx=200010;
pii seg[100005];
set<pii> range;
map<int,int> mp;
pii fen1[200015], fen2[200015];
int find1(int x) {
int ma=-INT_MAX, ans;
while (x) {
if (fen1[x].first && ma<=fen1[x].first){
ma=fen1[x].first;
ans=fen1[x].second;
}
x-=x&-x;
}
return ans;
}
void update1(int x, int val, int idx) {
while (x<=mx+2) {
if (fen1[x].first==0 || val>fen1[x].first) {
fen1[x]=pii(val,idx);
}
x+=x&-x;
}
}
int find2(int x) {
int mi=INT_MAX, ans;
while (x) {
if (fen2[x].first && fen2[x].first<=mi) {
mi=fen2[x].first;
ans=fen2[x].second;
}
x-=x&-x;
}
return ans;
}
void update2(int x, int val, int idx) {
while (x<=mx+2) {
if (fen2[x].first==0 || fen2[x].first>val) fen2[x]=pii(val,idx);
x+=x&-x;
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie();
freopen("sample-04-in.txt","r",stdin);
cin>>n>>k;
seg[0]=pii(-INT_MAX,-INT_MAX);
seg[n+1]=pii(INT_MAX,INT_MAX);
mp[-INT_MAX]=0; mp[INT_MAX]=0;
for (int i=0; i<18; ++i) nxL[0][i]=0, nxR[n+1][i]=n+1;
for (int i=1; i<=n; ++i) {
cin>>seg[i].first>>seg[i].second;
mp[seg[i].first]=0;
mp[seg[i].second]=0;
}
int cnt=0;
for (auto s : mp) mp[s.first]=++cnt;
//find L
for (int i=0; i<=n; ++i) update1(mp[seg[i].second],seg[i].first,i);
for (int i=n; i>0; --i) {
nxL[i][0]=find1(mp[seg[i].first]);
for (int j=1; j<18; ++j) nxL[i][j]=nxL[nxL[i][j-1]][j-1];
}
//find R
for (int i=1; i<=n+1; ++i) update2(mx-mp[seg[i].first],seg[i].second,i);
for (int i=n; i>0; --i) {
nxR[i][0]=find2(mx-mp[seg[i].second]);
for (int j=1; j<18; ++j) nxR[i][j]=nxR[nxR[i][j-1]][j-1];
}
vector<int> ans;
range.insert(pii(1,1e9));
for (int i=1; i<=n; ++i) {
auto it=range.upper_bound(pii(seg[i].first,INT_MAX));
if (it==range.begin()) continue;
--it;
if ((*it).second<seg[i].second) continue;
int l=(*it).first, r=(*it).second, cnt=0;
int idx=i;
for (int j=17; j>=0; --j) {
if (seg[nxL[idx][j]].first>=l) idx=nxL[idx][j], cnt+=(1<<j);
}
idx=i;
for (int j=17; j>=0; --j) {
if (seg[nxR[idx][j]].second<=r) idx=nxR[idx][j], cnt+=(1<<j);
}
if (cnt>=k-ans.size()-1) {
ans.push_back(i);
range.erase(it);
if (seg[i].first!=l) range.insert(pii(l,seg[i].first));
if (seg[i].second!=r) range.insert(pii(seg[i].second,r));
}
if (ans.size()==k) {
for (auto s : ans) cout<<s<<"\n";
return 0;
}
}
cout<<-1;
}
Compilation message
event2.cpp: In function 'int main()':
event2.cpp:106:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | if (cnt>=k-ans.size()-1) {
| ~~~^~~~~~~~~~~~~~~~
event2.cpp:113:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
113 | if (ans.size()==k) {
| ~~~~~~~~~~^~~
event2.cpp:55:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | freopen("sample-04-in.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
event2.cpp: In function 'int find1(int)':
event2.cpp:21:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
21 | return ans;
| ^~~
event2.cpp: In function 'int find2(int)':
event2.cpp:42:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
42 | return ans;
| ^~~
event2.cpp: In function 'int main()':
event2.cpp:82:18: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
82 | nxR[i][0]=find2(mx-mp[seg[i].second]);
| ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
event2.cpp:75:18: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
75 | nxL[i][0]=find1(mp[seg[i].first]);
| ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
