oj.uz

Submission #834975

# Submission time Handle Problem Language Result Execution time Memory
834975 2023-08-23T04:12:12 Z sunwukong123 Event Hopping 2 (JOI21_event2) C++14
8 / 100
 330 ms 148944 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long 
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = 200005;
const int inf=1000000500ll;
const int oo =1000000000000000000ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
int n,k;
array<int,3> A[MAXN];
int rtwok[MAXN][20];
int ltwok[MAXN][20];
struct node1 {
	int s,e,m,val;
	node1 *l, *r;
	node1 (int _s, int _e){
		s=_s;e=_e;m=(s+e)/2;
		val=inf;
		if(s!=e){
			l=new node1(s,m);
			r=new node1(m+1,e);
		}
	}
	void update(int x, int nval){
		if(s==e){
			val=min(val,nval);
			return;
		}
		if(x>m)r->update(x,nval);
		else l->update(x,nval);
		val=min(l->val,r->val);
	}
	int query(int x, int y){
		if(s==x&&e==y){
			return val;
		}
		if(x>m)return r->query(x,y);
		else if(y<=m)return l->query(x,y);
		else return min(l->query(x,m), r->query(m+1,y));
	}
}*mnseg;
struct node2{
	int s,e,m,val;
	node2 *l, *r;
	node2 (int _s, int _e){
		s=_s;e=_e;m=(s+e)/2;
		val=-1;
		if(s!=e){
			l=new node2(s,m);
			r=new node2(m+1,e);
		}
	}
	void update(int x, int nval){
		if(s==e){
			val=max(val,nval);
			return;
		}
		if(x>m)r->update(x,nval);
		else l->update(x,nval);
		val=max(l->val,r->val);
	}
	int query(int x, int y){
		if(s==x&&e==y){
			return val;
		}
		if(x>m)return r->query(x,y);
		else if(y<=m)return l->query(x,y);
		else return max(l->query(x,m), r->query(m+1,y));
	}
}*mxseg;
map<int,int> to_n;
map<int,int> to_1;
struct fenw {
	int fw[MAXN], fw2[MAXN];
	void update(int x, int y, int v) { //inclusive
	    for (int tx=x; tx < MAXN; tx += tx&(-tx)) fw[tx] += v, fw2[tx] -= v*(x-1);
	    for (int ty=y+1; ty < MAXN; ty += ty&(-ty)) fw[ty] -= v, fw2[ty] += v*y; 
	}
	int sum (int x) {
	    int res = 0;
	    for (int tx=x; tx; tx -= tx&(-tx)) res += fw[tx]*x + fw2[tx];
	    return res;    
	}
	int range_sum(int x, int y) { //inclusive
	    return sum(y)-sum(x-1);
	}
}fw;
map<int,int> mapper;
int32_t main() 
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	int m=2*n+2;
	memset(rtwok,-1,sizeof rtwok);
	memset(ltwok,-1,sizeof ltwok);
	mnseg=new node1(0,m);
	mxseg=new node2(0,m);

	vector<pair<int,int>> in;
	vector<int> disc;
	for(int i=1;i<=n;i++){
		int a,b; cin >> a >> b;
		in.push_back({a,b});
		disc.push_back(a);
		disc.push_back(b);
	}
	sort(disc.begin(),disc.end());
	disc.resize(unique(disc.begin(),disc.end())-disc.begin());
	for(int i=0;i<(int)disc.size();i++){
		mapper[disc[i]]=i+1;
	}

	for(int i=1;i<=n;i++){
		A[i][0] = mapper[in[i-1].first];
		A[i][1] = mapper[in[i-1].second];
		A[i][2] = i;
	}
	for(int i=1;i<=n;i++){
		mnseg->update(A[i][0],A[i][1]);
		mxseg->update(A[i][1],A[i][0]);
	}
	for(int i=1;i<=m;i++){
		rtwok[i][0]=mnseg->query(i,m);
		if(rtwok[i][0]==inf)rtwok[i][0]=-1;
		ltwok[i][0]=mxseg->query(1,i);

	}
	for(int i=m;i>=1;i--){
		for(int j=1;j<=19;j++){
			if(rtwok[i][j-1] == -1)continue;
			rtwok[i][j]=rtwok[rtwok[i][j-1]][j-1];
		}
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=19;++j){
			if(ltwok[i][j-1]==-1)continue;
			ltwok[i][j]=ltwok[ltwok[i][j-1]][j-1];
		}
	}
	vector<int>out;
	for(int i=1;i<=n;i++){
		int L=A[i][0], R=A[i][1];

		if(fw.range_sum(L,R-1)>0){
			continue;
		}
		
		auto it=to_n.lower_bound(R);
		pair<int,int> gn={m+1,0};
		if(it!=to_n.end())gn=*it;
		int sum = 1;
		int sumL = 0, sumR=0;
		for(int k=19;k>=0;k--){
			if(rtwok[R][k] != -1 && rtwok[R][k] <= gn.first){
				R=rtwok[R][k];
				sum+=(1<<k);
				sumR+=(1<<k);
			}
		}
		sumR+=gn.second;
		sum+=gn.second;

		it=to_1.upper_bound(L);
		pair<int,int> g1={0,0};
		if(it!=to_1.begin())g1=*prev(it);

		for(int k=19;k>=0;k--){

			if(ltwok[L][k] != -1 && ltwok[L][k] >= g1.first){
				L=ltwok[L][k];
				sum+=(1<<k);
				sumL+=(1<<k);
			}
		}
		//debug(g1.first,g1.second);
		sumL+=g1.second;
		sum+=g1.second;
		//debug(i,sum,sumL,sumR);
		if(sum>=k && (int)out.size()<k){
			out.push_back(i);
			fw.update(A[i][0],A[i][1]-1,1);

			to_n[A[i][0]]=1+sumR;
			to_1[A[i][1]]=1+sumL;
		} 
	}
	if(out.empty())cout<<-1<<'\n';
	else{
		assert((int)out.size()==k);
		for(auto x:out)cout<<x<<"\n";
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 63016 KB Output is correct
2 Correct 20 ms 62928 KB Output is correct
3 Correct 22 ms 62936 KB Output is correct
4 Correct 328 ms 147112 KB Output is correct
5 Correct 322 ms 148216 KB Output is correct
6 Correct 324 ms 147360 KB Output is correct
7 Correct 320 ms 145832 KB Output is correct
8 Correct 329 ms 148944 KB Output is correct
9 Correct 328 ms 148252 KB Output is correct
10 Correct 317 ms 147376 KB Output is correct
11 Correct 330 ms 145852 KB Output is correct
12 Correct 290 ms 144020 KB Output is correct
13 Correct 263 ms 143564 KB Output is correct
14 Correct 281 ms 143016 KB Output is correct
15 Correct 278 ms 141888 KB Output is correct
16 Correct 222 ms 137864 KB Output is correct
17 Correct 236 ms 137632 KB Output is correct
18 Correct 240 ms 137240 KB Output is correct
19 Correct 225 ms 136280 KB Output is correct
20 Correct 263 ms 136284 KB Output is correct
21 Correct 215 ms 136192 KB Output is correct
22 Correct 232 ms 135960 KB Output is correct
23 Correct 220 ms 135748 KB Output is correct
24 Correct 229 ms 135576 KB Output is correct
25 Correct 237 ms 133548 KB Output is correct
26 Correct 236 ms 133524 KB Output is correct
27 Correct 234 ms 133412 KB Output is correct
28 Correct 253 ms 133112 KB Output is correct
29 Correct 259 ms 132912 KB Output is correct
30 Correct 241 ms 133008 KB Output is correct
31 Correct 241 ms 132920 KB Output is correct
32 Correct 253 ms 132900 KB Output is correct
33 Correct 262 ms 132960 KB Output is correct
34 Correct 284 ms 139648 KB Output is correct
35 Correct 276 ms 137412 KB Output is correct
36 Correct 290 ms 135248 KB Output is correct
37 Correct 275 ms 143048 KB Output is correct
38 Correct 269 ms 142612 KB Output is correct
39 Correct 274 ms 142232 KB Output is correct
40 Correct 269 ms 141852 KB Output is correct
41 Correct 302 ms 141460 KB Output is correct
42 Correct 266 ms 133012 KB Output is correct
43 Correct 286 ms 142696 KB Output is correct
44 Correct 290 ms 142480 KB Output is correct
45 Correct 285 ms 141924 KB Output is correct
46 Correct 292 ms 141564 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 63028 KB Output is correct
2 Correct 21 ms 62916 KB Output is correct
3 Correct 20 ms 63016 KB Output is correct
4 Correct 21 ms 63064 KB Output is correct
5 Correct 21 ms 62968 KB Output is correct
6 Correct 22 ms 62948 KB Output is correct
7 Correct 21 ms 62980 KB Output is correct
8 Correct 22 ms 62984 KB Output is correct
9 Correct 21 ms 63064 KB Output is correct
10 Correct 22 ms 63060 KB Output is correct
11 Correct 22 ms 62948 KB Output is correct
12 Correct 21 ms 63048 KB Output is correct
13 Correct 24 ms 63032 KB Output is correct
14 Correct 21 ms 63064 KB Output is correct
15 Correct 21 ms 62952 KB Output is correct
16 Correct 22 ms 62960 KB Output is correct
17 Correct 21 ms 63000 KB Output is correct
18 Correct 21 ms 63060 KB Output is correct
19 Correct 24 ms 62928 KB Output is correct
20 Correct 21 ms 62984 KB Output is correct
21 Correct 21 ms 63000 KB Output is correct
22 Correct 21 ms 63004 KB Output is correct
23 Correct 21 ms 62956 KB Output is correct
24 Correct 21 ms 62880 KB Output is correct
25 Correct 21 ms 62904 KB Output is correct
26 Correct 20 ms 62956 KB Output is correct
27 Correct 22 ms 62952 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 63028 KB Output is correct
2 Correct 21 ms 62916 KB Output is correct
3 Correct 20 ms 63016 KB Output is correct
4 Correct 21 ms 63064 KB Output is correct
5 Correct 21 ms 62968 KB Output is correct
6 Correct 22 ms 62948 KB Output is correct
7 Correct 21 ms 62980 KB Output is correct
8 Correct 22 ms 62984 KB Output is correct
9 Correct 21 ms 63064 KB Output is correct
10 Correct 22 ms 63060 KB Output is correct
11 Correct 22 ms 62948 KB Output is correct
12 Correct 21 ms 63048 KB Output is correct
13 Correct 24 ms 63032 KB Output is correct
14 Correct 21 ms 63064 KB Output is correct
15 Correct 21 ms 62952 KB Output is correct
16 Correct 22 ms 62960 KB Output is correct
17 Correct 21 ms 63000 KB Output is correct
18 Correct 21 ms 63060 KB Output is correct
19 Correct 24 ms 62928 KB Output is correct
20 Correct 21 ms 62984 KB Output is correct
21 Correct 21 ms 63000 KB Output is correct
22 Correct 21 ms 63004 KB Output is correct
23 Correct 21 ms 62956 KB Output is correct
24 Correct 21 ms 62880 KB Output is correct
25 Correct 21 ms 62904 KB Output is correct
26 Correct 20 ms 62956 KB Output is correct
27 Correct 22 ms 62952 KB Output is correct
28 Correct 29 ms 65244 KB Output is correct
29 Correct 31 ms 65180 KB Output is correct
30 Runtime error 77 ms 132020 KB Execution killed with signal 6
31 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 63016 KB Output is correct
2 Correct 20 ms 62928 KB Output is correct
3 Correct 22 ms 62936 KB Output is correct
4 Correct 328 ms 147112 KB Output is correct
5 Correct 322 ms 148216 KB Output is correct
6 Correct 324 ms 147360 KB Output is correct
7 Correct 320 ms 145832 KB Output is correct
8 Correct 329 ms 148944 KB Output is correct
9 Correct 328 ms 148252 KB Output is correct
10 Correct 317 ms 147376 KB Output is correct
11 Correct 330 ms 145852 KB Output is correct
12 Correct 290 ms 144020 KB Output is correct
13 Correct 263 ms 143564 KB Output is correct
14 Correct 281 ms 143016 KB Output is correct
15 Correct 278 ms 141888 KB Output is correct
16 Correct 222 ms 137864 KB Output is correct
17 Correct 236 ms 137632 KB Output is correct
18 Correct 240 ms 137240 KB Output is correct
19 Correct 225 ms 136280 KB Output is correct
20 Correct 263 ms 136284 KB Output is correct
21 Correct 215 ms 136192 KB Output is correct
22 Correct 232 ms 135960 KB Output is correct
23 Correct 220 ms 135748 KB Output is correct
24 Correct 229 ms 135576 KB Output is correct
25 Correct 237 ms 133548 KB Output is correct
26 Correct 236 ms 133524 KB Output is correct
27 Correct 234 ms 133412 KB Output is correct
28 Correct 253 ms 133112 KB Output is correct
29 Correct 259 ms 132912 KB Output is correct
30 Correct 241 ms 133008 KB Output is correct
31 Correct 241 ms 132920 KB Output is correct
32 Correct 253 ms 132900 KB Output is correct
33 Correct 262 ms 132960 KB Output is correct
34 Correct 284 ms 139648 KB Output is correct
35 Correct 276 ms 137412 KB Output is correct
36 Correct 290 ms 135248 KB Output is correct
37 Correct 275 ms 143048 KB Output is correct
38 Correct 269 ms 142612 KB Output is correct
39 Correct 274 ms 142232 KB Output is correct
40 Correct 269 ms 141852 KB Output is correct
41 Correct 302 ms 141460 KB Output is correct
42 Correct 266 ms 133012 KB Output is correct
43 Correct 286 ms 142696 KB Output is correct
44 Correct 290 ms 142480 KB Output is correct
45 Correct 285 ms 141924 KB Output is correct
46 Correct 292 ms 141564 KB Output is correct
47 Correct 21 ms 63028 KB Output is correct
48 Correct 21 ms 62916 KB Output is correct
49 Correct 20 ms 63016 KB Output is correct
50 Correct 21 ms 63064 KB Output is correct
51 Correct 21 ms 62968 KB Output is correct
52 Correct 22 ms 62948 KB Output is correct
53 Correct 21 ms 62980 KB Output is correct
54 Correct 22 ms 62984 KB Output is correct
55 Correct 21 ms 63064 KB Output is correct
56 Correct 22 ms 63060 KB Output is correct
57 Correct 22 ms 62948 KB Output is correct
58 Correct 21 ms 63048 KB Output is correct
59 Correct 24 ms 63032 KB Output is correct
60 Correct 21 ms 63064 KB Output is correct
61 Correct 21 ms 62952 KB Output is correct
62 Correct 22 ms 62960 KB Output is correct
63 Correct 21 ms 63000 KB Output is correct
64 Correct 21 ms 63060 KB Output is correct
65 Correct 24 ms 62928 KB Output is correct
66 Correct 21 ms 62984 KB Output is correct
67 Correct 21 ms 63000 KB Output is correct
68 Correct 21 ms 63004 KB Output is correct
69 Correct 21 ms 62956 KB Output is correct
70 Correct 21 ms 62880 KB Output is correct
71 Correct 21 ms 62904 KB Output is correct
72 Correct 20 ms 62956 KB Output is correct
73 Correct 22 ms 62952 KB Output is correct
74 Correct 29 ms 65244 KB Output is correct
75 Correct 31 ms 65180 KB Output is correct
76 Runtime error 77 ms 132020 KB Execution killed with signal 6
77 Halted 0 ms 0 KB -