oj.uz

Submission #1014191

# Submission time Handle Problem Language Result Execution time Memory
1014191 2024-07-04T13:52:24 Z pcc New Home (APIO18_new_home) C++17
57 / 100
 5000 ms 752144 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")

#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*30];
	int head[mxn*30];
	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 257 ms 665788 KB Output is correct
2 Correct 287 ms 665672 KB Output is correct
3 Correct 292 ms 665684 KB Output is correct
4 Correct 318 ms 665680 KB Output is correct
5 Correct 288 ms 665648 KB Output is correct
6 Correct 324 ms 665928 KB Output is correct
7 Correct 274 ms 665940 KB Output is correct
8 Correct 293 ms 665824 KB Output is correct
9 Correct 311 ms 665936 KB Output is correct
10 Correct 324 ms 665912 KB Output is correct
11 Correct 277 ms 665928 KB Output is correct
12 Correct 297 ms 665744 KB Output is correct
13 Correct 311 ms 665960 KB Output is correct
14 Correct 314 ms 666080 KB Output is correct
15 Correct 352 ms 665940 KB Output is correct
16 Correct 277 ms 665936 KB Output is correct
17 Correct 334 ms 665880 KB Output is correct
18 Correct 277 ms 665836 KB Output is correct
19 Correct 289 ms 665788 KB Output is correct
20 Correct 286 ms 665936 KB Output is correct
21 Correct 293 ms 665760 KB Output is correct
22 Correct 326 ms 665864 KB Output is correct
23 Correct 324 ms 665888 KB Output is correct
24 Correct 268 ms 665936 KB Output is correct
25 Correct 283 ms 665940 KB Output is correct
26 Correct 305 ms 665900 KB Output is correct
27 Correct 292 ms 665680 KB Output is correct
28 Correct 334 ms 665868 KB Output is correct
29 Correct 336 ms 665940 KB Output is correct
30 Correct 294 ms 665936 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 665788 KB Output is correct
2 Correct 287 ms 665672 KB Output is correct
3 Correct 292 ms 665684 KB Output is correct
4 Correct 318 ms 665680 KB Output is correct
5 Correct 288 ms 665648 KB Output is correct
6 Correct 324 ms 665928 KB Output is correct
7 Correct 274 ms 665940 KB Output is correct
8 Correct 293 ms 665824 KB Output is correct
9 Correct 311 ms 665936 KB Output is correct
10 Correct 324 ms 665912 KB Output is correct
11 Correct 277 ms 665928 KB Output is correct
12 Correct 297 ms 665744 KB Output is correct
13 Correct 311 ms 665960 KB Output is correct
14 Correct 314 ms 666080 KB Output is correct
15 Correct 352 ms 665940 KB Output is correct
16 Correct 277 ms 665936 KB Output is correct
17 Correct 334 ms 665880 KB Output is correct
18 Correct 277 ms 665836 KB Output is correct
19 Correct 289 ms 665788 KB Output is correct
20 Correct 286 ms 665936 KB Output is correct
21 Correct 293 ms 665760 KB Output is correct
22 Correct 326 ms 665864 KB Output is correct
23 Correct 324 ms 665888 KB Output is correct
24 Correct 268 ms 665936 KB Output is correct
25 Correct 283 ms 665940 KB Output is correct
26 Correct 305 ms 665900 KB Output is correct
27 Correct 292 ms 665680 KB Output is correct
28 Correct 334 ms 665868 KB Output is correct
29 Correct 336 ms 665940 KB Output is correct
30 Correct 294 ms 665936 KB Output is correct
31 Correct 1446 ms 688764 KB Output is correct
32 Correct 464 ms 675412 KB Output is correct
33 Correct 1491 ms 690800 KB Output is correct
34 Correct 1445 ms 690692 KB Output is correct
35 Correct 1504 ms 688832 KB Output is correct
36 Correct 1455 ms 688636 KB Output is correct
37 Correct 1330 ms 690864 KB Output is correct
38 Correct 1289 ms 690828 KB Output is correct
39 Correct 1028 ms 690740 KB Output is correct
40 Correct 1092 ms 690884 KB Output is correct
41 Correct 1153 ms 690416 KB Output is correct
42 Correct 1144 ms 690280 KB Output is correct
43 Correct 365 ms 676804 KB Output is correct
44 Correct 1127 ms 690628 KB Output is correct
45 Correct 1124 ms 690288 KB Output is correct
46 Correct 1528 ms 690324 KB Output is correct
47 Correct 828 ms 688836 KB Output is correct
48 Correct 846 ms 688580 KB Output is correct
49 Correct 906 ms 688972 KB Output is correct
50 Correct 940 ms 690004 KB Output is correct
51 Correct 931 ms 688952 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1874 ms 718800 KB Output is correct
2 Correct 1950 ms 721468 KB Output is correct
3 Correct 1880 ms 751948 KB Output is correct
4 Correct 1910 ms 733144 KB Output is correct
5 Correct 2085 ms 720972 KB Output is correct
6 Correct 2448 ms 721452 KB Output is correct
7 Correct 1644 ms 751936 KB Output is correct
8 Correct 1612 ms 733248 KB Output is correct
9 Correct 1712 ms 726296 KB Output is correct
10 Correct 1828 ms 722452 KB Output is correct
11 Correct 1371 ms 721228 KB Output is correct
12 Correct 1516 ms 722268 KB Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 665788 KB Output is correct
2 Correct 287 ms 665672 KB Output is correct
3 Correct 292 ms 665684 KB Output is correct
4 Correct 318 ms 665680 KB Output is correct
5 Correct 288 ms 665648 KB Output is correct
6 Correct 324 ms 665928 KB Output is correct
7 Correct 274 ms 665940 KB Output is correct
8 Correct 293 ms 665824 KB Output is correct
9 Correct 311 ms 665936 KB Output is correct
10 Correct 324 ms 665912 KB Output is correct
11 Correct 277 ms 665928 KB Output is correct
12 Correct 297 ms 665744 KB Output is correct
13 Correct 311 ms 665960 KB Output is correct
14 Correct 314 ms 666080 KB Output is correct
15 Correct 352 ms 665940 KB Output is correct
16 Correct 277 ms 665936 KB Output is correct
17 Correct 334 ms 665880 KB Output is correct
18 Correct 277 ms 665836 KB Output is correct
19 Correct 289 ms 665788 KB Output is correct
20 Correct 286 ms 665936 KB Output is correct
21 Correct 293 ms 665760 KB Output is correct
22 Correct 326 ms 665864 KB Output is correct
23 Correct 324 ms 665888 KB Output is correct
24 Correct 268 ms 665936 KB Output is correct
25 Correct 283 ms 665940 KB Output is correct
26 Correct 305 ms 665900 KB Output is correct
27 Correct 292 ms 665680 KB Output is correct
28 Correct 334 ms 665868 KB Output is correct
29 Correct 336 ms 665940 KB Output is correct
30 Correct 294 ms 665936 KB Output is correct
31 Correct 1446 ms 688764 KB Output is correct
32 Correct 464 ms 675412 KB Output is correct
33 Correct 1491 ms 690800 KB Output is correct
34 Correct 1445 ms 690692 KB Output is correct
35 Correct 1504 ms 688832 KB Output is correct
36 Correct 1455 ms 688636 KB Output is correct
37 Correct 1330 ms 690864 KB Output is correct
38 Correct 1289 ms 690828 KB Output is correct
39 Correct 1028 ms 690740 KB Output is correct
40 Correct 1092 ms 690884 KB Output is correct
41 Correct 1153 ms 690416 KB Output is correct
42 Correct 1144 ms 690280 KB Output is correct
43 Correct 365 ms 676804 KB Output is correct
44 Correct 1127 ms 690628 KB Output is correct
45 Correct 1124 ms 690288 KB Output is correct
46 Correct 1528 ms 690324 KB Output is correct
47 Correct 828 ms 688836 KB Output is correct
48 Correct 846 ms 688580 KB Output is correct
49 Correct 906 ms 688972 KB Output is correct
50 Correct 940 ms 690004 KB Output is correct
51 Correct 931 ms 688952 KB Output is correct
52 Correct 906 ms 693744 KB Output is correct
53 Correct 954 ms 695764 KB Output is correct
54 Correct 1042 ms 690116 KB Output is correct
55 Correct 993 ms 691656 KB Output is correct
56 Correct 1000 ms 692664 KB Output is correct
57 Correct 1106 ms 690584 KB Output is correct
58 Correct 1018 ms 691648 KB Output is correct
59 Correct 970 ms 692600 KB Output is correct
60 Correct 1104 ms 690960 KB Output is correct
61 Correct 350 ms 682368 KB Output is correct
62 Correct 794 ms 695452 KB Output is correct
63 Correct 877 ms 691400 KB Output is correct
64 Correct 861 ms 691144 KB Output is correct
65 Correct 1002 ms 690960 KB Output is correct
66 Correct 1129 ms 690312 KB Output is correct
67 Correct 405 ms 677872 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 665788 KB Output is correct
2 Correct 287 ms 665672 KB Output is correct
3 Correct 292 ms 665684 KB Output is correct
4 Correct 318 ms 665680 KB Output is correct
5 Correct 288 ms 665648 KB Output is correct
6 Correct 324 ms 665928 KB Output is correct
7 Correct 274 ms 665940 KB Output is correct
8 Correct 293 ms 665824 KB Output is correct
9 Correct 311 ms 665936 KB Output is correct
10 Correct 324 ms 665912 KB Output is correct
11 Correct 277 ms 665928 KB Output is correct
12 Correct 297 ms 665744 KB Output is correct
13 Correct 311 ms 665960 KB Output is correct
14 Correct 314 ms 666080 KB Output is correct
15 Correct 352 ms 665940 KB Output is correct
16 Correct 277 ms 665936 KB Output is correct
17 Correct 334 ms 665880 KB Output is correct
18 Correct 277 ms 665836 KB Output is correct
19 Correct 289 ms 665788 KB Output is correct
20 Correct 286 ms 665936 KB Output is correct
21 Correct 293 ms 665760 KB Output is correct
22 Correct 326 ms 665864 KB Output is correct
23 Correct 324 ms 665888 KB Output is correct
24 Correct 268 ms 665936 KB Output is correct
25 Correct 283 ms 665940 KB Output is correct
26 Correct 305 ms 665900 KB Output is correct
27 Correct 292 ms 665680 KB Output is correct
28 Correct 334 ms 665868 KB Output is correct
29 Correct 336 ms 665940 KB Output is correct
30 Correct 294 ms 665936 KB Output is correct
31 Correct 1446 ms 688764 KB Output is correct
32 Correct 464 ms 675412 KB Output is correct
33 Correct 1491 ms 690800 KB Output is correct
34 Correct 1445 ms 690692 KB Output is correct
35 Correct 1504 ms 688832 KB Output is correct
36 Correct 1455 ms 688636 KB Output is correct
37 Correct 1330 ms 690864 KB Output is correct
38 Correct 1289 ms 690828 KB Output is correct
39 Correct 1028 ms 690740 KB Output is correct
40 Correct 1092 ms 690884 KB Output is correct
41 Correct 1153 ms 690416 KB Output is correct
42 Correct 1144 ms 690280 KB Output is correct
43 Correct 365 ms 676804 KB Output is correct
44 Correct 1127 ms 690628 KB Output is correct
45 Correct 1124 ms 690288 KB Output is correct
46 Correct 1528 ms 690324 KB Output is correct
47 Correct 828 ms 688836 KB Output is correct
48 Correct 846 ms 688580 KB Output is correct
49 Correct 906 ms 688972 KB Output is correct
50 Correct 940 ms 690004 KB Output is correct
51 Correct 931 ms 688952 KB Output is correct
52 Correct 1874 ms 718800 KB Output is correct
53 Correct 1950 ms 721468 KB Output is correct
54 Correct 1880 ms 751948 KB Output is correct
55 Correct 1910 ms 733144 KB Output is correct
56 Correct 2085 ms 720972 KB Output is correct
57 Correct 2448 ms 721452 KB Output is correct
58 Correct 1644 ms 751936 KB Output is correct
59 Correct 1612 ms 733248 KB Output is correct
60 Correct 1712 ms 726296 KB Output is correct
61 Correct 1828 ms 722452 KB Output is correct
62 Correct 1371 ms 721228 KB Output is correct
63 Correct 1516 ms 722268 KB Output is correct
64 Execution timed out 5041 ms 752144 KB Time limit exceeded
65 Halted 0 ms 0 KB -