oj.uz

Submission #1014208

# Submission time Handle Problem Language Result Execution time Memory
1014208 2024-07-04T14:09:56 Z pcc New Home (APIO18_new_home) C++17
57 / 100
 5000 ms 517304 KB 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt")
 
#define _all(T) T.begin(),T.end()
#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 1e6;
const int inf = 1e9;
const int lim = 1e8+10;
 
struct SEG{
#define mid ((l+r)>>1)
#define ls now*2+1
#define rs now*2+2
	int seg[mxn*4];
	pii op[mxn*15];
	int head[mxn];
	int cnt = 0;
	SEG(){
		fill(seg,seg+mxn*4,-inf);
	}
	void modify(int now,int l,int r,int s,int e,int v,bool rec = false){
		if(rec&&now == 0){
			cnt++;
			head[cnt] = head[cnt-1];
		}
		if(l>=s&&e>=r){
			if(rec){
				op[++head[cnt]] = pii(now,seg[now]);
			}
			seg[now] = max(seg[now],v);
			return;
		}
		if(mid>=s)modify(ls,l,mid,s,e,v,rec);
		if(mid<e)modify(rs,mid+1,r,s,e,v,rec);
		return;
	}
	void undo(){
		assert(cnt);
		while(head[cnt]>head[cnt-1]){
			auto &[p,v] = op[head[cnt]--];
			seg[p] = v;
		}
		cnt--;
		return;
	}
	int getval(int now,int l,int r,int p){
		if(l == r)return seg[now];
		if(mid>=p)return max(seg[now],getval(ls,l,mid,p));
		else return max(seg[now],getval(rs,mid+1,r,p));
	}
#undef mid
#undef ls
#undef rs
};
 
SEG seg1,seg2;
int N,K,Q;
multiset<int> st[mxn];
vector<int> all;
vector<int> allt;
vector<pii> req;
array<int,4> shop[mxn];
int ans[mxn];
vector<pii> tseg[mxn*4];
vector<pii> ask[mxn];
 
void addev(int now,int l,int r,int s,int e,pii val){
	assert(e>=s);
	if(l>=s&&e>=r){
		tseg[now].push_back(val);
		return;
	}
	int mid = (l+r)>>1;
	if(mid>=s)addev(now*2+1,l,mid,s,e,val);
	if(mid<e)addev(now*2+2,mid+1,r,s,e,val);
	return;
}
 
void del(int pos,int tp){
	st[tp].erase(st[tp].find(pos));
	auto lit = --st[tp].lower_bound(pos);
	auto rit = st[tp].lower_bound(pos);
	int mid = all[*lit]+(all[*rit]-all[*lit])/2;
	int mp = upper_bound(_all(all),mid)-all.begin();
	//cerr<<"DEL: "<<pos<<' '<<tp<<"::"<<*lit<<' '<<mp<<' '<<*rit<<endl;
	seg1.modify(0,0,all.size(),*lit,mp-1,-all[*lit],1);
	seg2.modify(0,0,all.size(),mp,*rit,all[*rit],1);
	//cerr<<"DEL DONE! "<<endl;
	return;
}
 
void undo(){
	seg1.undo();
	seg2.undo();
}
 
void dfs(int now,int l,int r){
	//cerr<<"DFS IN: "<<l<<' '<<r<<endl;
	for(auto &i:tseg[now])del(i.fs,i.sc);
	if(l == r){
		for(auto &i:ask[l]){//p,idx
			//cerr<<"ASK: "<<i.fs<<','<<i.sc<<' '<<all[i.fs]<<' '<<seg1.getval(0,0,all.size(),i.fs)<<' '<<seg2.getval(0,0,all.size(),i.fs)<<endl;
			ans[i.sc] = max(all[i.fs]+seg1.getval(0,0,all.size(),i.fs),seg2.getval(0,0,all.size(),i.fs)-all[i.fs]);
		}
	}
	else{
		int mid = (l+r)>>1;
		dfs(now*2+1,l,mid);
		dfs(now*2+2,mid+1,r);
	}
	for(auto &[pos,tp]:tseg[now]){
		undo();
		//cerr<<"UNDO: "<<pos<<','<<tp<<endl;
		st[tp].insert(pos);
	}
	//cerr<<"DFS OUT: "<<l<<' '<<r<<endl;
	return;
}
 
int main(){
 
	cin>>N>>K>>Q;
	allt.push_back(-1);
	for(int i = 1;i<=N;i++){
		cin>>shop[i][0]>>shop[i][1]>>shop[i][2]>>shop[i][3];//x,t,a,b
		all.push_back(shop[i][0]);
		allt.push_back(shop[i][2]);
		allt.push_back(shop[i][3]);
	}
	for(int i = 0;i<Q;i++){
		int l,y;
		cin>>l>>y;
		all.push_back(l);
		allt.push_back(y);
		req.push_back(pii(l,y));
	}
	all.push_back(-inf);all.push_back(inf);
	sort(_all(all));all.resize(unique(_all(all))-all.begin());
	sort(_all(allt));allt.resize(unique(_all(allt))-allt.begin());
	//cerr<<"ALL: ";for(auto &i:all)cerr<<i<<' ';cerr<<endl;
	//cerr<<"ALLT: ";for(auto &i:allt)cerr<<i<<' ';cerr<<endl;
	for(int i = 1;i<=K;i++){
		st[i].insert(0);
		st[i].insert(all.size()-1);
	}
	for(int i = 1;i<=N;i++){
		shop[i][0] = lower_bound(_all(all),shop[i][0])-all.begin();
		st[shop[i][1]].insert(shop[i][0]);
		shop[i][2] = lower_bound(_all(allt),shop[i][2])-allt.begin();
		shop[i][3] = lower_bound(_all(allt),shop[i][3])-allt.begin();
	}
	for(int i = 1;i<=K;i++){
		for(auto it = ++st[i].begin();it != st[i].end();it++){
			int l = *prev(it),r = *it;
			int mid = all[l]+(all[r]-all[l])/2;
			auto pos = upper_bound(_all(all),mid)-all.begin();
			seg1.modify(0,0,all.size(),l,pos-1,-all[l]);
			seg2.modify(0,0,all.size(),pos,r,all[r]);
		}
	}
	//cerr<<"INIT DONE!"<<endl;
	for(int i = 1;i<=N;i++){
		int pos = shop[i][0],tp = shop[i][1],s = shop[i][2],e = shop[i][3];
		//cerr<<"ADDEV: "<<0<<' '<<s-1<<' '<<pos<<' '<<tp<<endl;
		//cerr<<"ADDEV: "<<e+1<<' '<<allt.size()<<' '<<pos<<' '<<tp<<endl;
		addev(0,0,allt.size(),0,s-1,pii(pos,tp));
		addev(0,0,allt.size(),e+1,allt.size(),pii(pos,tp));
	}
	for(int i = 0;i<Q;i++){
		auto &[p,t] = req[i];
		p = lower_bound(_all(all),p)-all.begin();
		t = lower_bound(_all(allt),t)-allt.begin();
		//cerr<<"ASK POS: "<<p<<' '<<t<<endl;
		ask[t].push_back(pii(p,i));
	}
 
	//cerr<<"ADDEV DONE!"<<' '<<seg1.getval(0,0,all.size(),req[0].fs)<<' '<<seg2.getval(0,0,all.size(),req[0].fs)<<endl;
 
	dfs(0,0,allt.size());
	assert(!seg1.cnt);
	assert(!seg2.cnt);
	//cerr<<"DFS DONE! "<<endl;
	for(int i = 0;i<Q;i++)cout<<(ans[i]>lim?-1:ans[i])<<'\n';
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 430932 KB Output is correct
2 Correct 188 ms 430804 KB Output is correct
3 Correct 183 ms 430928 KB Output is correct
4 Correct 179 ms 430928 KB Output is correct
5 Correct 187 ms 430920 KB Output is correct
6 Correct 178 ms 430928 KB Output is correct
7 Correct 185 ms 430932 KB Output is correct
8 Correct 190 ms 430932 KB Output is correct
9 Correct 169 ms 430928 KB Output is correct
10 Correct 171 ms 430928 KB Output is correct
11 Correct 184 ms 430928 KB Output is correct
12 Correct 176 ms 430928 KB Output is correct
13 Correct 185 ms 431248 KB Output is correct
14 Correct 177 ms 431020 KB Output is correct
15 Correct 156 ms 430932 KB Output is correct
16 Correct 155 ms 430932 KB Output is correct
17 Correct 161 ms 430952 KB Output is correct
18 Correct 157 ms 430932 KB Output is correct
19 Correct 172 ms 430928 KB Output is correct
20 Correct 162 ms 431028 KB Output is correct
21 Correct 158 ms 431032 KB Output is correct
22 Correct 156 ms 430932 KB Output is correct
23 Correct 183 ms 430928 KB Output is correct
24 Correct 177 ms 430928 KB Output is correct
25 Correct 173 ms 430932 KB Output is correct
26 Correct 162 ms 430932 KB Output is correct
27 Correct 173 ms 430932 KB Output is correct
28 Correct 178 ms 431028 KB Output is correct
29 Correct 176 ms 430928 KB Output is correct
30 Correct 177 ms 430940 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 430932 KB Output is correct
2 Correct 188 ms 430804 KB Output is correct
3 Correct 183 ms 430928 KB Output is correct
4 Correct 179 ms 430928 KB Output is correct
5 Correct 187 ms 430920 KB Output is correct
6 Correct 178 ms 430928 KB Output is correct
7 Correct 185 ms 430932 KB Output is correct
8 Correct 190 ms 430932 KB Output is correct
9 Correct 169 ms 430928 KB Output is correct
10 Correct 171 ms 430928 KB Output is correct
11 Correct 184 ms 430928 KB Output is correct
12 Correct 176 ms 430928 KB Output is correct
13 Correct 185 ms 431248 KB Output is correct
14 Correct 177 ms 431020 KB Output is correct
15 Correct 156 ms 430932 KB Output is correct
16 Correct 155 ms 430932 KB Output is correct
17 Correct 161 ms 430952 KB Output is correct
18 Correct 157 ms 430932 KB Output is correct
19 Correct 172 ms 430928 KB Output is correct
20 Correct 162 ms 431028 KB Output is correct
21 Correct 158 ms 431032 KB Output is correct
22 Correct 156 ms 430932 KB Output is correct
23 Correct 183 ms 430928 KB Output is correct
24 Correct 177 ms 430928 KB Output is correct
25 Correct 173 ms 430932 KB Output is correct
26 Correct 162 ms 430932 KB Output is correct
27 Correct 173 ms 430932 KB Output is correct
28 Correct 178 ms 431028 KB Output is correct
29 Correct 176 ms 430928 KB Output is correct
30 Correct 177 ms 430940 KB Output is correct
31 Correct 1268 ms 450976 KB Output is correct
32 Correct 369 ms 439572 KB Output is correct
33 Correct 1323 ms 452884 KB Output is correct
34 Correct 1255 ms 453064 KB Output is correct
35 Correct 1290 ms 450920 KB Output is correct
36 Correct 1255 ms 450964 KB Output is correct
37 Correct 1121 ms 453156 KB Output is correct
38 Correct 1179 ms 453056 KB Output is correct
39 Correct 1173 ms 453160 KB Output is correct
40 Correct 1027 ms 453320 KB Output is correct
41 Correct 1047 ms 452800 KB Output is correct
42 Correct 1067 ms 452544 KB Output is correct
43 Correct 273 ms 439732 KB Output is correct
44 Correct 1050 ms 452804 KB Output is correct
45 Correct 1079 ms 452764 KB Output is correct
46 Correct 1159 ms 452644 KB Output is correct
47 Correct 813 ms 451780 KB Output is correct
48 Correct 853 ms 451380 KB Output is correct
49 Correct 854 ms 451896 KB Output is correct
50 Correct 862 ms 452548 KB Output is correct
51 Correct 896 ms 451932 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1986 ms 483928 KB Output is correct
2 Correct 2032 ms 477016 KB Output is correct
3 Correct 1794 ms 506292 KB Output is correct
4 Correct 1945 ms 487628 KB Output is correct
5 Correct 2033 ms 476500 KB Output is correct
6 Correct 1990 ms 476972 KB Output is correct
7 Correct 1383 ms 506344 KB Output is correct
8 Correct 1506 ms 487572 KB Output is correct
9 Correct 1665 ms 481104 KB Output is correct
10 Correct 1936 ms 477684 KB Output is correct
11 Correct 1352 ms 476752 KB Output is correct
12 Correct 1406 ms 477404 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5083 ms 517304 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 430932 KB Output is correct
2 Correct 188 ms 430804 KB Output is correct
3 Correct 183 ms 430928 KB Output is correct
4 Correct 179 ms 430928 KB Output is correct
5 Correct 187 ms 430920 KB Output is correct
6 Correct 178 ms 430928 KB Output is correct
7 Correct 185 ms 430932 KB Output is correct
8 Correct 190 ms 430932 KB Output is correct
9 Correct 169 ms 430928 KB Output is correct
10 Correct 171 ms 430928 KB Output is correct
11 Correct 184 ms 430928 KB Output is correct
12 Correct 176 ms 430928 KB Output is correct
13 Correct 185 ms 431248 KB Output is correct
14 Correct 177 ms 431020 KB Output is correct
15 Correct 156 ms 430932 KB Output is correct
16 Correct 155 ms 430932 KB Output is correct
17 Correct 161 ms 430952 KB Output is correct
18 Correct 157 ms 430932 KB Output is correct
19 Correct 172 ms 430928 KB Output is correct
20 Correct 162 ms 431028 KB Output is correct
21 Correct 158 ms 431032 KB Output is correct
22 Correct 156 ms 430932 KB Output is correct
23 Correct 183 ms 430928 KB Output is correct
24 Correct 177 ms 430928 KB Output is correct
25 Correct 173 ms 430932 KB Output is correct
26 Correct 162 ms 430932 KB Output is correct
27 Correct 173 ms 430932 KB Output is correct
28 Correct 178 ms 431028 KB Output is correct
29 Correct 176 ms 430928 KB Output is correct
30 Correct 177 ms 430940 KB Output is correct
31 Correct 1268 ms 450976 KB Output is correct
32 Correct 369 ms 439572 KB Output is correct
33 Correct 1323 ms 452884 KB Output is correct
34 Correct 1255 ms 453064 KB Output is correct
35 Correct 1290 ms 450920 KB Output is correct
36 Correct 1255 ms 450964 KB Output is correct
37 Correct 1121 ms 453156 KB Output is correct
38 Correct 1179 ms 453056 KB Output is correct
39 Correct 1173 ms 453160 KB Output is correct
40 Correct 1027 ms 453320 KB Output is correct
41 Correct 1047 ms 452800 KB Output is correct
42 Correct 1067 ms 452544 KB Output is correct
43 Correct 273 ms 439732 KB Output is correct
44 Correct 1050 ms 452804 KB Output is correct
45 Correct 1079 ms 452764 KB Output is correct
46 Correct 1159 ms 452644 KB Output is correct
47 Correct 813 ms 451780 KB Output is correct
48 Correct 853 ms 451380 KB Output is correct
49 Correct 854 ms 451896 KB Output is correct
50 Correct 862 ms 452548 KB Output is correct
51 Correct 896 ms 451932 KB Output is correct
52 Correct 852 ms 456528 KB Output is correct
53 Correct 870 ms 458436 KB Output is correct
54 Correct 923 ms 452548 KB Output is correct
55 Correct 907 ms 454292 KB Output is correct
56 Correct 921 ms 455344 KB Output is correct
57 Correct 1022 ms 453060 KB Output is correct
58 Correct 921 ms 454280 KB Output is correct
59 Correct 844 ms 454848 KB Output is correct
60 Correct 993 ms 453572 KB Output is correct
61 Correct 301 ms 445124 KB Output is correct
62 Correct 845 ms 457920 KB Output is correct
63 Correct 819 ms 454084 KB Output is correct
64 Correct 908 ms 453884 KB Output is correct
65 Correct 948 ms 453316 KB Output is correct
66 Correct 1020 ms 452916 KB Output is correct
67 Correct 296 ms 441796 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 430932 KB Output is correct
2 Correct 188 ms 430804 KB Output is correct
3 Correct 183 ms 430928 KB Output is correct
4 Correct 179 ms 430928 KB Output is correct
5 Correct 187 ms 430920 KB Output is correct
6 Correct 178 ms 430928 KB Output is correct
7 Correct 185 ms 430932 KB Output is correct
8 Correct 190 ms 430932 KB Output is correct
9 Correct 169 ms 430928 KB Output is correct
10 Correct 171 ms 430928 KB Output is correct
11 Correct 184 ms 430928 KB Output is correct
12 Correct 176 ms 430928 KB Output is correct
13 Correct 185 ms 431248 KB Output is correct
14 Correct 177 ms 431020 KB Output is correct
15 Correct 156 ms 430932 KB Output is correct
16 Correct 155 ms 430932 KB Output is correct
17 Correct 161 ms 430952 KB Output is correct
18 Correct 157 ms 430932 KB Output is correct
19 Correct 172 ms 430928 KB Output is correct
20 Correct 162 ms 431028 KB Output is correct
21 Correct 158 ms 431032 KB Output is correct
22 Correct 156 ms 430932 KB Output is correct
23 Correct 183 ms 430928 KB Output is correct
24 Correct 177 ms 430928 KB Output is correct
25 Correct 173 ms 430932 KB Output is correct
26 Correct 162 ms 430932 KB Output is correct
27 Correct 173 ms 430932 KB Output is correct
28 Correct 178 ms 431028 KB Output is correct
29 Correct 176 ms 430928 KB Output is correct
30 Correct 177 ms 430940 KB Output is correct
31 Correct 1268 ms 450976 KB Output is correct
32 Correct 369 ms 439572 KB Output is correct
33 Correct 1323 ms 452884 KB Output is correct
34 Correct 1255 ms 453064 KB Output is correct
35 Correct 1290 ms 450920 KB Output is correct
36 Correct 1255 ms 450964 KB Output is correct
37 Correct 1121 ms 453156 KB Output is correct
38 Correct 1179 ms 453056 KB Output is correct
39 Correct 1173 ms 453160 KB Output is correct
40 Correct 1027 ms 453320 KB Output is correct
41 Correct 1047 ms 452800 KB Output is correct
42 Correct 1067 ms 452544 KB Output is correct
43 Correct 273 ms 439732 KB Output is correct
44 Correct 1050 ms 452804 KB Output is correct
45 Correct 1079 ms 452764 KB Output is correct
46 Correct 1159 ms 452644 KB Output is correct
47 Correct 813 ms 451780 KB Output is correct
48 Correct 853 ms 451380 KB Output is correct
49 Correct 854 ms 451896 KB Output is correct
50 Correct 862 ms 452548 KB Output is correct
51 Correct 896 ms 451932 KB Output is correct
52 Correct 1986 ms 483928 KB Output is correct
53 Correct 2032 ms 477016 KB Output is correct
54 Correct 1794 ms 506292 KB Output is correct
55 Correct 1945 ms 487628 KB Output is correct
56 Correct 2033 ms 476500 KB Output is correct
57 Correct 1990 ms 476972 KB Output is correct
58 Correct 1383 ms 506344 KB Output is correct
59 Correct 1506 ms 487572 KB Output is correct
60 Correct 1665 ms 481104 KB Output is correct
61 Correct 1936 ms 477684 KB Output is correct
62 Correct 1352 ms 476752 KB Output is correct
63 Correct 1406 ms 477404 KB Output is correct
64 Execution timed out 5083 ms 517304 KB Time limit exceeded
65 Halted 0 ms 0 KB -