oj.uz

Submission #947076

# Submission time Handle Problem Language Result Execution time Memory
947076 2024-03-15T13:12:10 Z amirhoseinfar1385 Event Hopping 2 (JOI21_event2) C++17
100 / 100
 253 ms 65692 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10,lg=20;
vector<long long>res;
long long n,k,sp[lg][maxn+10],dp[maxn],lnk[maxn],last[maxn];
pair<long long,long long>all[maxn];
vector<long long>alll[maxn],allr[maxn];
long long ted=0;
vector<pair<long long,long long>>allv;
set<pair<long long,long long>>inds;

long long callen(long long ind){
  	if(ind>=(int)allv.size()){
   	   return 0;
  	}
	long long l=allv[ind].first;
	auto x=inds.lower_bound(make_pair(l,l));
	long long bad=(*x).first;
	x--;
	long long ghabl=(*x).second;
	if(l<=ghabl){
		return 0;
	}
	if(lnk[l]>=bad||l>=bad){
		return 0;
	}
	long long ret=1;
	for(int i=lg-1;i>=0;i--){
		if(sp[i][l]<bad&&lnk[sp[i][l]]<bad){
			ret+=(1<<i);
			l=sp[i][l];
		}
	}
//	while(lnk[l]<bad&&l<bad){
//		ret++;
//		l=sp[0][l];
//	}
	return ret;
}

void vorod(){
	cin>>n>>k;
	vector<long long>allind;
	for(long long i=1;i<=n;i++){
		cin>>all[i].first>>all[i].second;
		all[i].second--;
		allind.push_back(all[i].first);
		allind.push_back(all[i].second);
	}
	sort(allind.begin(),allind.end());
	allind.resize(unique(allind.begin(),allind.end())-allind.begin());
	for(long long i=1;i<=n;i++){
		all[i].first=lower_bound(allind.begin(),allind.end(),all[i].first)-allind.begin();
		all[i].second=lower_bound(allind.begin(),allind.end(),all[i].second)-allind.begin();
		alll[all[i].first].push_back(i);
		allr[all[i].second].push_back(i);
	}
}
void pre(){
	inds.insert(make_pair(-1,-1));
	inds.insert(make_pair(maxn,maxn));
	set<pair<long long,long long>>st;
	for(long long i=0;i<maxn;i++){
		last[i]=maxn+2;
	}
	for(long long i=0;i<maxn;i++){
		long long mn=maxn+2;
		for(auto x:alll[i]){
			mn=min(mn,all[x].second);
		}
		while((long long)st.size()>0&&(*st.rbegin()).first>=mn){
			st.erase(*st.rbegin());
		}
		for(auto x:alll[i]){
			if(all[x].second==mn){
				st.insert(make_pair(all[x].second,x));
				mn=-1;
			}
		}
		for(auto x:allr[i]){
			if(st.count(make_pair(i,x))==1){
				st.erase(make_pair(i,x));
				allv.push_back(make_pair(all[x].first,all[x].second));
				last[all[x].first-1]=all[x].first;
				lnk[all[x].first]=all[x].second;
			}
		}
	}
	for(long long i=maxn-2;i>=0;i--){
		last[i]=min(last[i],last[i+1]);
	}
	for(long long i=0;i<maxn+9;i++){
		for(long long j=0;j<lg;j++){
			sp[j][i]=maxn+2;
		}
	}
	for(long long i=1;i<=n;i++){
		sp[0][all[i].first]=min(sp[0][all[i].first],last[lnk[all[i].first]]);
	}
	for(long long i=1;i<lg;i++){
		for(long long j=0;j<maxn;j++){
			sp[i][j]=sp[i-1][sp[i-1][j]];
		}
	}
	dp[0]=callen(0);
	ted+=dp[0];
}

bool eshy(long long l,long long r,long long ll,long long rr){
	if(l>ll){
		swap(l,ll);
		swap(r,rr);
	}
	return ll<=r;
}

bool esh(long long a,long long b){
	return eshy(all[a].first,all[a].second,all[b].first,all[b].second);
}

/*long long cal(){
	long long ret=0,r=-1;
	for(auto x:allv){
		long long f=1;
		auto z=inds.lower_bound(make_pair(x.first,x.first));
		if((long long)inds.size()>0&&(*inds.rbegin()).first>=x.first){
			if(eshy(x.first,x.second,(*z).first,(*z).second)){
				f=0;
			}
		}
		if((long long)inds.size()>0&&(*inds.begin()).first<x.first){
			z--;
			if(eshy(x.first,x.second,(*z).first,(*z).second)){
				f=0;
			}
		}
		if(x.first<=r||f==0){
			continue;
		}
		ret++;
		r=x.second;
	}
	return ret;
}*/

void ins(long long i){
  res.push_back(i);
	auto x=inds.lower_bound(make_pair(all[i].first,all[i].second));
	auto bad=*x;
	x--;
	auto ghabl=*x;
	long long p1=lower_bound(allv.begin(),allv.end(),make_pair(ghabl.second+1,-1ll))-allv.begin();
	long long p2=lower_bound(allv.begin(),allv.end(),make_pair(all[i].second+1,-1ll))-allv.begin();
	long long p3=lower_bound(allv.begin(),allv.end(),make_pair(bad.second+1,-1ll))-allv.begin();
	inds.insert(make_pair(all[i].first,all[i].second));
	if(p1!=p3){
		ted-=dp[p1];
	}
	dp[p1]=callen(p1);
	dp[p2]=callen(p2);
	if(p1!=p2){
		ted+=dp[p1];
	}
	if(p2!=p3){
		ted+=dp[p2];
	}
}

void erase(long long i){
  res.pop_back();
	inds.erase(make_pair(all[i].first,all[i].second));
	auto x=inds.lower_bound(make_pair(all[i].first,all[i].second));
	auto bad=*x;
	x--;
	auto ghabl=*x;
	long long p1=lower_bound(allv.begin(),allv.end(),make_pair(ghabl.second+1,-1ll))-allv.begin();
	long long p2=lower_bound(allv.begin(),allv.end(),make_pair(all[i].second+1,-1ll))-allv.begin();
	long long p3=lower_bound(allv.begin(),allv.end(),make_pair(bad.second+1,-1ll))-allv.begin();
	if(p1!=p2){
		ted-=dp[p1];
	}
	if(p2!=p3){
		ted-=dp[p2];
	}
	dp[p1]=callen(p1);
	dp[p2]=callen(p2);
	if(p1!=p3){
		ted+=dp[p1];
	}
}

void can(long long i){
	auto x=all[i];
	auto z=inds.lower_bound(make_pair(x.first,x.first));
	if((long long)inds.size()>0&&(*inds.rbegin()).first>=x.first){
		if(eshy(x.first,x.second,(*z).first,(*z).second)){
			return ;
		}
	}
	if((long long)inds.size()>0&&(*inds.begin()).first<x.first){
		z--;
		if(eshy(x.first,x.second,(*z).first,(*z).second)){
			return ;
		}
	}
	ins(i);
	if(ted+(long long)res.size()<k){
		erase(i);
	}
}

void solve(){
	for(long long i=1;i<=n;i++){
		if((long long)res.size()==k){
			break;
		}
		can(i);
	}
}

void khor(){
	if((long long)res.size()<k){
		cout<<-1<<"\n";
		return ;
	}
	for(auto x:res){
		cout<<x<<"\n";
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	vorod();
	pre();
	solve();
	khor();
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 46940 KB Output is correct
2 Correct 14 ms 46940 KB Output is correct
3 Correct 13 ms 46940 KB Output is correct
4 Correct 128 ms 65192 KB Output is correct
5 Correct 129 ms 64664 KB Output is correct
6 Correct 119 ms 64408 KB Output is correct
7 Correct 110 ms 63640 KB Output is correct
8 Correct 131 ms 65152 KB Output is correct
9 Correct 125 ms 64696 KB Output is correct
10 Correct 125 ms 64356 KB Output is correct
11 Correct 115 ms 63728 KB Output is correct
12 Correct 110 ms 62324 KB Output is correct
13 Correct 106 ms 62088 KB Output is correct
14 Correct 100 ms 62108 KB Output is correct
15 Correct 94 ms 61464 KB Output is correct
16 Correct 83 ms 58284 KB Output is correct
17 Correct 78 ms 58288 KB Output is correct
18 Correct 78 ms 58412 KB Output is correct
19 Correct 74 ms 57344 KB Output is correct
20 Correct 82 ms 57260 KB Output is correct
21 Correct 77 ms 57176 KB Output is correct
22 Correct 75 ms 56596 KB Output is correct
23 Correct 91 ms 56592 KB Output is correct
24 Correct 78 ms 56732 KB Output is correct
25 Correct 77 ms 56496 KB Output is correct
26 Correct 85 ms 56488 KB Output is correct
27 Correct 80 ms 56552 KB Output is correct
28 Correct 104 ms 60080 KB Output is correct
29 Correct 102 ms 60004 KB Output is correct
30 Correct 100 ms 58404 KB Output is correct
31 Correct 112 ms 57260 KB Output is correct
32 Correct 104 ms 56776 KB Output is correct
33 Correct 126 ms 56580 KB Output is correct
34 Correct 90 ms 60740 KB Output is correct
35 Correct 74 ms 60056 KB Output is correct
36 Correct 68 ms 60068 KB Output is correct
37 Correct 97 ms 61084 KB Output is correct
38 Correct 93 ms 60852 KB Output is correct
39 Correct 89 ms 60632 KB Output is correct
40 Correct 90 ms 60692 KB Output is correct
41 Correct 93 ms 60464 KB Output is correct
42 Correct 105 ms 58284 KB Output is correct
43 Correct 104 ms 60824 KB Output is correct
44 Correct 105 ms 60620 KB Output is correct
45 Correct 98 ms 60488 KB Output is correct
46 Correct 100 ms 60316 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 46940 KB Output is correct
2 Correct 15 ms 46940 KB Output is correct
3 Correct 13 ms 46940 KB Output is correct
4 Correct 13 ms 46936 KB Output is correct
5 Correct 15 ms 47192 KB Output is correct
6 Correct 13 ms 46788 KB Output is correct
7 Correct 13 ms 46940 KB Output is correct
8 Correct 13 ms 46940 KB Output is correct
9 Correct 13 ms 46704 KB Output is correct
10 Correct 12 ms 46940 KB Output is correct
11 Correct 13 ms 46940 KB Output is correct
12 Correct 14 ms 46904 KB Output is correct
13 Correct 13 ms 46940 KB Output is correct
14 Correct 13 ms 46744 KB Output is correct
15 Correct 14 ms 46940 KB Output is correct
16 Correct 13 ms 46940 KB Output is correct
17 Correct 15 ms 46940 KB Output is correct
18 Correct 14 ms 46940 KB Output is correct
19 Correct 13 ms 46940 KB Output is correct
20 Correct 13 ms 46936 KB Output is correct
21 Correct 13 ms 46940 KB Output is correct
22 Correct 13 ms 46804 KB Output is correct
23 Correct 14 ms 46940 KB Output is correct
24 Correct 12 ms 46944 KB Output is correct
25 Correct 13 ms 46940 KB Output is correct
26 Correct 13 ms 46936 KB Output is correct
27 Correct 13 ms 46940 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 46940 KB Output is correct
2 Correct 15 ms 46940 KB Output is correct
3 Correct 13 ms 46940 KB Output is correct
4 Correct 13 ms 46936 KB Output is correct
5 Correct 15 ms 47192 KB Output is correct
6 Correct 13 ms 46788 KB Output is correct
7 Correct 13 ms 46940 KB Output is correct
8 Correct 13 ms 46940 KB Output is correct
9 Correct 13 ms 46704 KB Output is correct
10 Correct 12 ms 46940 KB Output is correct
11 Correct 13 ms 46940 KB Output is correct
12 Correct 14 ms 46904 KB Output is correct
13 Correct 13 ms 46940 KB Output is correct
14 Correct 13 ms 46744 KB Output is correct
15 Correct 14 ms 46940 KB Output is correct
16 Correct 13 ms 46940 KB Output is correct
17 Correct 15 ms 46940 KB Output is correct
18 Correct 14 ms 46940 KB Output is correct
19 Correct 13 ms 46940 KB Output is correct
20 Correct 13 ms 46936 KB Output is correct
21 Correct 13 ms 46940 KB Output is correct
22 Correct 13 ms 46804 KB Output is correct
23 Correct 14 ms 46940 KB Output is correct
24 Correct 12 ms 46944 KB Output is correct
25 Correct 13 ms 46940 KB Output is correct
26 Correct 13 ms 46936 KB Output is correct
27 Correct 13 ms 46940 KB Output is correct
28 Correct 15 ms 47192 KB Output is correct
29 Correct 16 ms 47184 KB Output is correct
30 Correct 15 ms 47208 KB Output is correct
31 Correct 14 ms 47196 KB Output is correct
32 Correct 16 ms 47196 KB Output is correct
33 Correct 15 ms 47196 KB Output is correct
34 Correct 16 ms 47196 KB Output is correct
35 Correct 18 ms 47448 KB Output is correct
36 Correct 17 ms 47304 KB Output is correct
37 Correct 16 ms 47196 KB Output is correct
38 Correct 16 ms 47128 KB Output is correct
39 Correct 17 ms 47192 KB Output is correct
40 Correct 16 ms 47296 KB Output is correct
41 Correct 17 ms 47304 KB Output is correct
42 Correct 17 ms 47196 KB Output is correct
43 Correct 18 ms 47196 KB Output is correct
44 Correct 16 ms 47196 KB Output is correct
45 Correct 15 ms 47196 KB Output is correct
46 Correct 17 ms 47196 KB Output is correct
47 Correct 15 ms 46972 KB Output is correct
48 Correct 17 ms 47196 KB Output is correct
49 Correct 15 ms 47240 KB Output is correct
50 Correct 16 ms 47196 KB Output is correct
51 Correct 15 ms 47004 KB Output is correct
52 Correct 15 ms 47092 KB Output is correct
53 Correct 15 ms 47196 KB Output is correct
54 Correct 17 ms 46972 KB Output is correct
55 Correct 16 ms 47260 KB Output is correct
56 Correct 16 ms 47452 KB Output is correct
57 Correct 16 ms 47452 KB Output is correct
58 Correct 16 ms 47448 KB Output is correct
59 Correct 15 ms 47452 KB Output is correct
60 Correct 16 ms 47456 KB Output is correct
61 Correct 16 ms 47452 KB Output is correct
62 Correct 16 ms 47392 KB Output is correct
63 Correct 16 ms 47236 KB Output is correct
64 Correct 16 ms 47196 KB Output is correct

Subtask #4
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 46940 KB Output is correct
2 Correct 14 ms 46940 KB Output is correct
3 Correct 13 ms 46940 KB Output is correct
4 Correct 128 ms 65192 KB Output is correct
5 Correct 129 ms 64664 KB Output is correct
6 Correct 119 ms 64408 KB Output is correct
7 Correct 110 ms 63640 KB Output is correct
8 Correct 131 ms 65152 KB Output is correct
9 Correct 125 ms 64696 KB Output is correct
10 Correct 125 ms 64356 KB Output is correct
11 Correct 115 ms 63728 KB Output is correct
12 Correct 110 ms 62324 KB Output is correct
13 Correct 106 ms 62088 KB Output is correct
14 Correct 100 ms 62108 KB Output is correct
15 Correct 94 ms 61464 KB Output is correct
16 Correct 83 ms 58284 KB Output is correct
17 Correct 78 ms 58288 KB Output is correct
18 Correct 78 ms 58412 KB Output is correct
19 Correct 74 ms 57344 KB Output is correct
20 Correct 82 ms 57260 KB Output is correct
21 Correct 77 ms 57176 KB Output is correct
22 Correct 75 ms 56596 KB Output is correct
23 Correct 91 ms 56592 KB Output is correct
24 Correct 78 ms 56732 KB Output is correct
25 Correct 77 ms 56496 KB Output is correct
26 Correct 85 ms 56488 KB Output is correct
27 Correct 80 ms 56552 KB Output is correct
28 Correct 104 ms 60080 KB Output is correct
29 Correct 102 ms 60004 KB Output is correct
30 Correct 100 ms 58404 KB Output is correct
31 Correct 112 ms 57260 KB Output is correct
32 Correct 104 ms 56776 KB Output is correct
33 Correct 126 ms 56580 KB Output is correct
34 Correct 90 ms 60740 KB Output is correct
35 Correct 74 ms 60056 KB Output is correct
36 Correct 68 ms 60068 KB Output is correct
37 Correct 97 ms 61084 KB Output is correct
38 Correct 93 ms 60852 KB Output is correct
39 Correct 89 ms 60632 KB Output is correct
40 Correct 90 ms 60692 KB Output is correct
41 Correct 93 ms 60464 KB Output is correct
42 Correct 105 ms 58284 KB Output is correct
43 Correct 104 ms 60824 KB Output is correct
44 Correct 105 ms 60620 KB Output is correct
45 Correct 98 ms 60488 KB Output is correct
46 Correct 100 ms 60316 KB Output is correct
47 Correct 13 ms 46940 KB Output is correct
48 Correct 15 ms 46940 KB Output is correct
49 Correct 13 ms 46940 KB Output is correct
50 Correct 13 ms 46936 KB Output is correct
51 Correct 15 ms 47192 KB Output is correct
52 Correct 13 ms 46788 KB Output is correct
53 Correct 13 ms 46940 KB Output is correct
54 Correct 13 ms 46940 KB Output is correct
55 Correct 13 ms 46704 KB Output is correct
56 Correct 12 ms 46940 KB Output is correct
57 Correct 13 ms 46940 KB Output is correct
58 Correct 14 ms 46904 KB Output is correct
59 Correct 13 ms 46940 KB Output is correct
60 Correct 13 ms 46744 KB Output is correct
61 Correct 14 ms 46940 KB Output is correct
62 Correct 13 ms 46940 KB Output is correct
63 Correct 15 ms 46940 KB Output is correct
64 Correct 14 ms 46940 KB Output is correct
65 Correct 13 ms 46940 KB Output is correct
66 Correct 13 ms 46936 KB Output is correct
67 Correct 13 ms 46940 KB Output is correct
68 Correct 13 ms 46804 KB Output is correct
69 Correct 14 ms 46940 KB Output is correct
70 Correct 12 ms 46944 KB Output is correct
71 Correct 13 ms 46940 KB Output is correct
72 Correct 13 ms 46936 KB Output is correct
73 Correct 13 ms 46940 KB Output is correct
74 Correct 15 ms 47192 KB Output is correct
75 Correct 16 ms 47184 KB Output is correct
76 Correct 15 ms 47208 KB Output is correct
77 Correct 14 ms 47196 KB Output is correct
78 Correct 16 ms 47196 KB Output is correct
79 Correct 15 ms 47196 KB Output is correct
80 Correct 16 ms 47196 KB Output is correct
81 Correct 18 ms 47448 KB Output is correct
82 Correct 17 ms 47304 KB Output is correct
83 Correct 16 ms 47196 KB Output is correct
84 Correct 16 ms 47128 KB Output is correct
85 Correct 17 ms 47192 KB Output is correct
86 Correct 16 ms 47296 KB Output is correct
87 Correct 17 ms 47304 KB Output is correct
88 Correct 17 ms 47196 KB Output is correct
89 Correct 18 ms 47196 KB Output is correct
90 Correct 16 ms 47196 KB Output is correct
91 Correct 15 ms 47196 KB Output is correct
92 Correct 17 ms 47196 KB Output is correct
93 Correct 15 ms 46972 KB Output is correct
94 Correct 17 ms 47196 KB Output is correct
95 Correct 15 ms 47240 KB Output is correct
96 Correct 16 ms 47196 KB Output is correct
97 Correct 15 ms 47004 KB Output is correct
98 Correct 15 ms 47092 KB Output is correct
99 Correct 15 ms 47196 KB Output is correct
100 Correct 17 ms 46972 KB Output is correct
101 Correct 16 ms 47260 KB Output is correct
102 Correct 16 ms 47452 KB Output is correct
103 Correct 16 ms 47452 KB Output is correct
104 Correct 16 ms 47448 KB Output is correct
105 Correct 15 ms 47452 KB Output is correct
106 Correct 16 ms 47456 KB Output is correct
107 Correct 16 ms 47452 KB Output is correct
108 Correct 16 ms 47392 KB Output is correct
109 Correct 16 ms 47236 KB Output is correct
110 Correct 16 ms 47196 KB Output is correct
111 Correct 111 ms 56420 KB Output is correct
112 Correct 112 ms 56476 KB Output is correct
113 Correct 114 ms 56492 KB Output is correct
114 Correct 122 ms 56452 KB Output is correct
115 Correct 106 ms 56316 KB Output is correct
116 Correct 151 ms 56540 KB Output is correct
117 Correct 164 ms 56336 KB Output is correct
118 Correct 242 ms 65176 KB Output is correct
119 Correct 249 ms 64596 KB Output is correct
120 Correct 190 ms 61244 KB Output is correct
121 Correct 212 ms 59860 KB Output is correct
122 Correct 208 ms 62368 KB Output is correct
123 Correct 185 ms 61852 KB Output is correct
124 Correct 185 ms 61336 KB Output is correct
125 Correct 227 ms 60088 KB Output is correct
126 Correct 156 ms 58472 KB Output is correct
127 Correct 164 ms 58264 KB Output is correct
128 Correct 143 ms 58712 KB Output is correct
129 Correct 222 ms 58404 KB Output is correct
130 Correct 139 ms 57068 KB Output is correct
131 Correct 130 ms 57312 KB Output is correct
132 Correct 124 ms 57312 KB Output is correct
133 Correct 227 ms 57124 KB Output is correct
134 Correct 126 ms 56532 KB Output is correct
135 Correct 120 ms 56772 KB Output is correct
136 Correct 120 ms 56736 KB Output is correct
137 Correct 178 ms 56700 KB Output is correct
138 Correct 118 ms 56492 KB Output is correct
139 Correct 114 ms 56488 KB Output is correct
140 Correct 109 ms 56488 KB Output is correct
141 Correct 149 ms 56580 KB Output is correct
142 Correct 132 ms 65516 KB Output is correct
143 Correct 131 ms 65692 KB Output is correct
144 Correct 131 ms 65688 KB Output is correct
145 Correct 110 ms 65532 KB Output is correct
146 Correct 107 ms 65436 KB Output is correct
147 Correct 109 ms 65308 KB Output is correct
148 Correct 108 ms 65184 KB Output is correct
149 Correct 107 ms 65060 KB Output is correct
150 Correct 106 ms 64764 KB Output is correct
151 Correct 95 ms 63896 KB Output is correct
152 Correct 101 ms 59968 KB Output is correct
153 Correct 118 ms 65652 KB Output is correct
154 Correct 109 ms 65444 KB Output is correct
155 Correct 120 ms 65276 KB Output is correct
156 Correct 124 ms 65484 KB Output is correct
157 Correct 108 ms 64924 KB Output is correct
158 Correct 104 ms 64924 KB Output is correct
159 Correct 119 ms 64408 KB Output is correct
160 Correct 102 ms 59052 KB Output is correct
161 Correct 183 ms 60380 KB Output is correct
162 Correct 173 ms 60312 KB Output is correct
163 Correct 176 ms 60176 KB Output is correct
164 Correct 172 ms 60152 KB Output is correct
165 Correct 180 ms 59876 KB Output is correct
166 Correct 99 ms 57008 KB Output is correct
167 Correct 107 ms 59512 KB Output is correct
168 Correct 97 ms 59408 KB Output is correct
169 Correct 97 ms 59288 KB Output is correct
170 Correct 96 ms 59072 KB Output is correct
171 Correct 90 ms 60504 KB Output is correct
172 Correct 95 ms 60432 KB Output is correct
173 Correct 253 ms 60392 KB Output is correct
174 Correct 223 ms 60624 KB Output is correct
175 Correct 220 ms 60312 KB Output is correct
176 Correct 163 ms 59624 KB Output is correct