oj.uz

Submission #94800

# Submission time Handle Problem Language Result Execution time Memory
94800 2019-01-24T05:35:09 Z jangwonyoung New Home (APIO18_new_home) C++14
80 / 100
 5000 ms 259088 KB 
#include<iostream>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int N=3e5+1,Q=3e5+1,K=3e5+1;
int n,k,q;
struct pt{
	ll x,tp,t;//<0: add, =0: qry, >0: rmv
};
bool operator<(pt x,pt y){
	return x.t<y.t;
}
pt a[2*N];
multiset<ll>s[K];
int mptr=0;
vector<int>bin[3*N];
map<pair<ll,ll>,int>mp;//should clear after inserting all stores :)
struct upd{
	ll x,l,r,pos;
};
bool operator<(upd x,upd y){
	return x.pos<y.pos;
}
vector<upd>pve,nve;
string f(ll x){
	string ret;
	if(x<=-1e8) return "-inf";
	if(x>=1e8) return "inf";
	if(x==0) ret+='0';
	while(x>0){
		char c=x%10+48;
		x/=10;
		ret=c+ret;
	}
	return ret;
}
void add(ll xl,ll xr,ll t){
	int num=mp[{xl,xr}];
	if(num==0) mp[{xl,xr}]=num=++mptr;
	bin[num].push_back(t);
}
void rmv(ll xl,ll xr,ll t){
	int cur=mp[{xl,xr}];
	ll p=bin[cur].back();
	bin[cur].pop_back();
	if(p==t) return;t--;
	upd pl={-xl,p,t,-(xl+xr)/2};
	upd nl={xr,p,t,(xl+xr+1)/2};
	pve.push_back(pl);nve.push_back(nl);
}
ll ans[Q];
pair<pair<ll,ll>,int>b[Q];
pair<ll,ll>c[Q];
ll st[1<<20];
void init(int id,int l,int r){
	st[id]=-1e9;
	if(l==r) return;
	int mid=(l+r)/2;
	init(id*2,l,mid);init(id*2+1,mid+1,r);
}
void upd(int id,int l,int r,int ql,int qr,ll v){
	if(st[id]>=v) return;
	if(l>qr || r<ql) return;
	if(ql<=l && r<=qr){
		st[id]=max(st[id],v);
		return;
	}
	int mid=(l+r)/2;
	upd(id*2,l,mid,ql,qr,v);
	upd(id*2+1,mid+1,r,ql,qr,v);
}
ll qry(int id,int l,int r,int p){
	if(l==r) return st[id];
	int mid=(l+r)/2;
	if(p<=mid) return max(st[id],qry(id*2,l,mid,p));
	else return max(st[id],qry(id*2+1,mid+1,r,p));
}
void in(int& x){
	char c=getchar();
	while(c<48 || c>57) c=getchar();
	x=0;
	while(c>=48 && c<=57){
		x=x*10+c-48;
		c=getchar();
	}
}
void in(ll& x){
	char c=getchar();
	while(c<48 || c>57) c=getchar();
	x=0;
	while(c>=48 && c<=57){
		x=x*10+c-48;
		c=getchar();
	}
}
int main(){
	ios::sync_with_stdio(false);
	in(n);in(k);in(q);
	for(int i=1; i<=3*n ;i++) bin[i].reserve(2);
	for(int i=1; i<=n ;i++){
		ll x,tp,u,v;in(x);in(tp);in(u);in(v);
		a[i*2-1]={x,-tp,u};
		a[i*2]={x,tp,v+1};
	}
	mptr=1;
	for(int i=1; i<=k ;i++){
		s[i].insert(-1e9);
		s[i].insert(1e9);
		mp[{(ll)-1e9,(ll)1e9}]=mptr;
		bin[mptr].push_back(1);
	}
	sort(a+1,a+2*n+1);
	for(int i=1; i<=2*n ;i++){
		ll x=a[i].x,tp=a[i].tp,t=a[i].t;
		if(tp<0){
			tp=-tp;
			auto it=s[tp].lower_bound(x);
			auto it2=it;--it2;
			rmv(*it2,*it,t);add(*it2,x,t);add(x,*it,t);
			s[tp].insert(x);
		}
		else{
			auto it3=s[tp].lower_bound(x);
			auto it=it3;++it;
			auto it2=it3;--it2;
			rmv(*it2,x,t);rmv(x,*it,t);add(*it2,*it,t);
			s[tp].erase(it3);
		}
	}
	for(int i=1; i<=k ;i++) rmv(-1e9,1e9,1e9);
	sort(nve.begin(),nve.end());
	sort(pve.begin(),pve.end());
	for(int i=1; i<=q ;i++){
		in(b[i].fi.fi);in(b[i].fi.se);
		b[i].se=i;
		c[i]={b[i].fi.se,i};
	}
	sort(c+1,c+q+1);
	for(int i=1; i<=q ;i++) b[c[i].se].fi.se=i;
	sort(b+1,b+q+1);
	int ptr=0;
	init(1,1,q);
	for(int i=1; i<=q ;i++){
		while(ptr<nve.size() && nve[ptr].pos<=b[i].fi.fi){
			int l=lower_bound(c+1,c+q+1,(pair<ll,ll>){nve[ptr].l,0LL})-c;
			int r=lower_bound(c+1,c+q+1,(pair<ll,ll>){nve[ptr].r+1,0LL})-c-1;
			if(l<=r) upd(1,1,q,l,r,nve[ptr].x);
			ptr++;
		}
		ans[b[i].se]=max(ans[b[i].se],qry(1,1,q,b[i].fi.se)-b[i].fi.fi);
	}
	init(1,1,q);
	reverse(b+1,b+q+1);
	for(int i=1; i<=q ;i++) b[i].fi.fi=-b[i].fi.fi;
	ptr=0;
	for(int i=1; i<=q ;i++){
		while(ptr<pve.size() && pve[ptr].pos<=b[i].fi.fi){
			int l=lower_bound(c+1,c+q+1,(pair<ll,ll>){pve[ptr].l,0LL})-c;
			int r=lower_bound(c+1,c+q+1,(pair<ll,ll>){pve[ptr].r+1,0LL})-c-1;
			if(l<=r) upd(1,1,q,l,r,pve[ptr].x);
			ptr++;
		}
		ans[b[i].se]=max(ans[b[i].se],qry(1,1,q,b[i].fi.se)-b[i].fi.fi);
	}
	for(int i=1; i<=q ;i++){
		if(ans[i]>=(ll)1e8) cout << "-1\n";
		else cout << ans[i] << '\n';
	}
}

Compilation message

new_home.cpp: In function 'void rmv(ll, ll, ll)':
new_home.cpp:51:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(p==t) return;t--;
  ^~
new_home.cpp:51:18: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(p==t) return;t--;
                  ^
new_home.cpp: In function 'int main()':
new_home.cpp:149:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr<nve.size() && nve[ptr].pos<=b[i].fi.fi){
         ~~~^~~~~~~~~~~
new_home.cpp:162:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr<pve.size() && pve[ptr].pos<=b[i].fi.fi){
         ~~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 35604 KB Output is correct
2 Correct 28 ms 35548 KB Output is correct
3 Correct 34 ms 35576 KB Output is correct
4 Correct 28 ms 35576 KB Output is correct
5 Correct 35 ms 35704 KB Output is correct
6 Correct 36 ms 35960 KB Output is correct
7 Correct 37 ms 35960 KB Output is correct
8 Correct 36 ms 35960 KB Output is correct
9 Correct 34 ms 35960 KB Output is correct
10 Correct 37 ms 35960 KB Output is correct
11 Correct 30 ms 35832 KB Output is correct
12 Correct 33 ms 35960 KB Output is correct
13 Correct 35 ms 35960 KB Output is correct
14 Correct 35 ms 35960 KB Output is correct
15 Correct 35 ms 35960 KB Output is correct
16 Correct 31 ms 35960 KB Output is correct
17 Correct 37 ms 35960 KB Output is correct
18 Correct 35 ms 36012 KB Output is correct
19 Correct 35 ms 35960 KB Output is correct
20 Correct 30 ms 35968 KB Output is correct
21 Correct 35 ms 36020 KB Output is correct
22 Correct 36 ms 35960 KB Output is correct
23 Correct 37 ms 35960 KB Output is correct
24 Correct 33 ms 35944 KB Output is correct
25 Correct 36 ms 35960 KB Output is correct
26 Correct 35 ms 35960 KB Output is correct
27 Correct 35 ms 35832 KB Output is correct
28 Correct 36 ms 35832 KB Output is correct
29 Correct 36 ms 36000 KB Output is correct
30 Correct 35 ms 35832 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 35604 KB Output is correct
2 Correct 28 ms 35548 KB Output is correct
3 Correct 34 ms 35576 KB Output is correct
4 Correct 28 ms 35576 KB Output is correct
5 Correct 35 ms 35704 KB Output is correct
6 Correct 36 ms 35960 KB Output is correct
7 Correct 37 ms 35960 KB Output is correct
8 Correct 36 ms 35960 KB Output is correct
9 Correct 34 ms 35960 KB Output is correct
10 Correct 37 ms 35960 KB Output is correct
11 Correct 30 ms 35832 KB Output is correct
12 Correct 33 ms 35960 KB Output is correct
13 Correct 35 ms 35960 KB Output is correct
14 Correct 35 ms 35960 KB Output is correct
15 Correct 35 ms 35960 KB Output is correct
16 Correct 31 ms 35960 KB Output is correct
17 Correct 37 ms 35960 KB Output is correct
18 Correct 35 ms 36012 KB Output is correct
19 Correct 35 ms 35960 KB Output is correct
20 Correct 30 ms 35968 KB Output is correct
21 Correct 35 ms 36020 KB Output is correct
22 Correct 36 ms 35960 KB Output is correct
23 Correct 37 ms 35960 KB Output is correct
24 Correct 33 ms 35944 KB Output is correct
25 Correct 36 ms 35960 KB Output is correct
26 Correct 35 ms 35960 KB Output is correct
27 Correct 35 ms 35832 KB Output is correct
28 Correct 36 ms 35832 KB Output is correct
29 Correct 36 ms 36000 KB Output is correct
30 Correct 35 ms 35832 KB Output is correct
31 Correct 694 ms 75996 KB Output is correct
32 Correct 144 ms 52116 KB Output is correct
33 Correct 661 ms 73840 KB Output is correct
34 Correct 619 ms 73788 KB Output is correct
35 Correct 611 ms 75884 KB Output is correct
36 Correct 593 ms 75944 KB Output is correct
37 Correct 429 ms 72880 KB Output is correct
38 Correct 455 ms 73064 KB Output is correct
39 Correct 361 ms 72732 KB Output is correct
40 Correct 394 ms 72712 KB Output is correct
41 Correct 538 ms 73648 KB Output is correct
42 Correct 523 ms 73672 KB Output is correct
43 Correct 129 ms 57852 KB Output is correct
44 Correct 529 ms 73716 KB Output is correct
45 Correct 537 ms 73644 KB Output is correct
46 Correct 473 ms 73716 KB Output is correct
47 Correct 273 ms 71308 KB Output is correct
48 Correct 290 ms 71428 KB Output is correct
49 Correct 310 ms 72560 KB Output is correct
50 Correct 341 ms 72744 KB Output is correct
51 Correct 349 ms 72332 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3158 ms 198612 KB Output is correct
2 Correct 3740 ms 189700 KB Output is correct
3 Correct 2171 ms 247680 KB Output is correct
4 Correct 2596 ms 205444 KB Output is correct
5 Correct 2947 ms 189124 KB Output is correct
6 Correct 2983 ms 189404 KB Output is correct
7 Correct 2258 ms 247532 KB Output is correct
8 Correct 2121 ms 208608 KB Output is correct
9 Correct 2087 ms 197164 KB Output is correct
10 Correct 2580 ms 191296 KB Output is correct
11 Correct 1482 ms 188220 KB Output is correct
12 Correct 1475 ms 190320 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3538 ms 210908 KB Output is correct
2 Correct 806 ms 136720 KB Output is correct
3 Correct 4361 ms 209796 KB Output is correct
4 Correct 3077 ms 244040 KB Output is correct
5 Correct 3942 ms 212156 KB Output is correct
6 Correct 3922 ms 215960 KB Output is correct
7 Correct 4056 ms 208428 KB Output is correct
8 Correct 3497 ms 208740 KB Output is correct
9 Correct 2410 ms 244960 KB Output is correct
10 Correct 2948 ms 212000 KB Output is correct
11 Correct 3163 ms 209352 KB Output is correct
12 Correct 3949 ms 207916 KB Output is correct
13 Correct 1663 ms 202280 KB Output is correct
14 Correct 1646 ms 200648 KB Output is correct
15 Correct 1893 ms 204520 KB Output is correct
16 Correct 2135 ms 206908 KB Output is correct
17 Correct 2037 ms 203716 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 35604 KB Output is correct
2 Correct 28 ms 35548 KB Output is correct
3 Correct 34 ms 35576 KB Output is correct
4 Correct 28 ms 35576 KB Output is correct
5 Correct 35 ms 35704 KB Output is correct
6 Correct 36 ms 35960 KB Output is correct
7 Correct 37 ms 35960 KB Output is correct
8 Correct 36 ms 35960 KB Output is correct
9 Correct 34 ms 35960 KB Output is correct
10 Correct 37 ms 35960 KB Output is correct
11 Correct 30 ms 35832 KB Output is correct
12 Correct 33 ms 35960 KB Output is correct
13 Correct 35 ms 35960 KB Output is correct
14 Correct 35 ms 35960 KB Output is correct
15 Correct 35 ms 35960 KB Output is correct
16 Correct 31 ms 35960 KB Output is correct
17 Correct 37 ms 35960 KB Output is correct
18 Correct 35 ms 36012 KB Output is correct
19 Correct 35 ms 35960 KB Output is correct
20 Correct 30 ms 35968 KB Output is correct
21 Correct 35 ms 36020 KB Output is correct
22 Correct 36 ms 35960 KB Output is correct
23 Correct 37 ms 35960 KB Output is correct
24 Correct 33 ms 35944 KB Output is correct
25 Correct 36 ms 35960 KB Output is correct
26 Correct 35 ms 35960 KB Output is correct
27 Correct 35 ms 35832 KB Output is correct
28 Correct 36 ms 35832 KB Output is correct
29 Correct 36 ms 36000 KB Output is correct
30 Correct 35 ms 35832 KB Output is correct
31 Correct 694 ms 75996 KB Output is correct
32 Correct 144 ms 52116 KB Output is correct
33 Correct 661 ms 73840 KB Output is correct
34 Correct 619 ms 73788 KB Output is correct
35 Correct 611 ms 75884 KB Output is correct
36 Correct 593 ms 75944 KB Output is correct
37 Correct 429 ms 72880 KB Output is correct
38 Correct 455 ms 73064 KB Output is correct
39 Correct 361 ms 72732 KB Output is correct
40 Correct 394 ms 72712 KB Output is correct
41 Correct 538 ms 73648 KB Output is correct
42 Correct 523 ms 73672 KB Output is correct
43 Correct 129 ms 57852 KB Output is correct
44 Correct 529 ms 73716 KB Output is correct
45 Correct 537 ms 73644 KB Output is correct
46 Correct 473 ms 73716 KB Output is correct
47 Correct 273 ms 71308 KB Output is correct
48 Correct 290 ms 71428 KB Output is correct
49 Correct 310 ms 72560 KB Output is correct
50 Correct 341 ms 72744 KB Output is correct
51 Correct 349 ms 72332 KB Output is correct
52 Correct 498 ms 80724 KB Output is correct
53 Correct 443 ms 78848 KB Output is correct
54 Correct 639 ms 75824 KB Output is correct
55 Correct 483 ms 75184 KB Output is correct
56 Correct 418 ms 76800 KB Output is correct
57 Correct 474 ms 73156 KB Output is correct
58 Correct 454 ms 75184 KB Output is correct
59 Correct 459 ms 76468 KB Output is correct
60 Correct 506 ms 73128 KB Output is correct
61 Correct 152 ms 70364 KB Output is correct
62 Correct 455 ms 80744 KB Output is correct
63 Correct 506 ms 77488 KB Output is correct
64 Correct 686 ms 76112 KB Output is correct
65 Correct 642 ms 73392 KB Output is correct
66 Correct 512 ms 72472 KB Output is correct
67 Correct 204 ms 56268 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 35604 KB Output is correct
2 Correct 28 ms 35548 KB Output is correct
3 Correct 34 ms 35576 KB Output is correct
4 Correct 28 ms 35576 KB Output is correct
5 Correct 35 ms 35704 KB Output is correct
6 Correct 36 ms 35960 KB Output is correct
7 Correct 37 ms 35960 KB Output is correct
8 Correct 36 ms 35960 KB Output is correct
9 Correct 34 ms 35960 KB Output is correct
10 Correct 37 ms 35960 KB Output is correct
11 Correct 30 ms 35832 KB Output is correct
12 Correct 33 ms 35960 KB Output is correct
13 Correct 35 ms 35960 KB Output is correct
14 Correct 35 ms 35960 KB Output is correct
15 Correct 35 ms 35960 KB Output is correct
16 Correct 31 ms 35960 KB Output is correct
17 Correct 37 ms 35960 KB Output is correct
18 Correct 35 ms 36012 KB Output is correct
19 Correct 35 ms 35960 KB Output is correct
20 Correct 30 ms 35968 KB Output is correct
21 Correct 35 ms 36020 KB Output is correct
22 Correct 36 ms 35960 KB Output is correct
23 Correct 37 ms 35960 KB Output is correct
24 Correct 33 ms 35944 KB Output is correct
25 Correct 36 ms 35960 KB Output is correct
26 Correct 35 ms 35960 KB Output is correct
27 Correct 35 ms 35832 KB Output is correct
28 Correct 36 ms 35832 KB Output is correct
29 Correct 36 ms 36000 KB Output is correct
30 Correct 35 ms 35832 KB Output is correct
31 Correct 694 ms 75996 KB Output is correct
32 Correct 144 ms 52116 KB Output is correct
33 Correct 661 ms 73840 KB Output is correct
34 Correct 619 ms 73788 KB Output is correct
35 Correct 611 ms 75884 KB Output is correct
36 Correct 593 ms 75944 KB Output is correct
37 Correct 429 ms 72880 KB Output is correct
38 Correct 455 ms 73064 KB Output is correct
39 Correct 361 ms 72732 KB Output is correct
40 Correct 394 ms 72712 KB Output is correct
41 Correct 538 ms 73648 KB Output is correct
42 Correct 523 ms 73672 KB Output is correct
43 Correct 129 ms 57852 KB Output is correct
44 Correct 529 ms 73716 KB Output is correct
45 Correct 537 ms 73644 KB Output is correct
46 Correct 473 ms 73716 KB Output is correct
47 Correct 273 ms 71308 KB Output is correct
48 Correct 290 ms 71428 KB Output is correct
49 Correct 310 ms 72560 KB Output is correct
50 Correct 341 ms 72744 KB Output is correct
51 Correct 349 ms 72332 KB Output is correct
52 Correct 3158 ms 198612 KB Output is correct
53 Correct 3740 ms 189700 KB Output is correct
54 Correct 2171 ms 247680 KB Output is correct
55 Correct 2596 ms 205444 KB Output is correct
56 Correct 2947 ms 189124 KB Output is correct
57 Correct 2983 ms 189404 KB Output is correct
58 Correct 2258 ms 247532 KB Output is correct
59 Correct 2121 ms 208608 KB Output is correct
60 Correct 2087 ms 197164 KB Output is correct
61 Correct 2580 ms 191296 KB Output is correct
62 Correct 1482 ms 188220 KB Output is correct
63 Correct 1475 ms 190320 KB Output is correct
64 Correct 3538 ms 210908 KB Output is correct
65 Correct 806 ms 136720 KB Output is correct
66 Correct 4361 ms 209796 KB Output is correct
67 Correct 3077 ms 244040 KB Output is correct
68 Correct 3942 ms 212156 KB Output is correct
69 Correct 3922 ms 215960 KB Output is correct
70 Correct 4056 ms 208428 KB Output is correct
71 Correct 3497 ms 208740 KB Output is correct
72 Correct 2410 ms 244960 KB Output is correct
73 Correct 2948 ms 212000 KB Output is correct
74 Correct 3163 ms 209352 KB Output is correct
75 Correct 3949 ms 207916 KB Output is correct
76 Correct 1663 ms 202280 KB Output is correct
77 Correct 1646 ms 200648 KB Output is correct
78 Correct 1893 ms 204520 KB Output is correct
79 Correct 2135 ms 206908 KB Output is correct
80 Correct 2037 ms 203716 KB Output is correct
81 Correct 498 ms 80724 KB Output is correct
82 Correct 443 ms 78848 KB Output is correct
83 Correct 639 ms 75824 KB Output is correct
84 Correct 483 ms 75184 KB Output is correct
85 Correct 418 ms 76800 KB Output is correct
86 Correct 474 ms 73156 KB Output is correct
87 Correct 454 ms 75184 KB Output is correct
88 Correct 459 ms 76468 KB Output is correct
89 Correct 506 ms 73128 KB Output is correct
90 Correct 152 ms 70364 KB Output is correct
91 Correct 455 ms 80744 KB Output is correct
92 Correct 506 ms 77488 KB Output is correct
93 Correct 686 ms 76112 KB Output is correct
94 Correct 642 ms 73392 KB Output is correct
95 Correct 512 ms 72472 KB Output is correct
96 Correct 204 ms 56268 KB Output is correct
97 Correct 3616 ms 259088 KB Output is correct
98 Correct 779 ms 117596 KB Output is correct
99 Execution timed out 5017 ms 217520 KB Time limit exceeded
100 Halted 0 ms 0 KB -