oj.uz

Submission #94801

# Submission time Handle Problem Language Result Execution time Memory
94801 2019-01-24T05:40:20 Z jangwonyoung New Home (APIO18_new_home) C++14
100 / 100
 4888 ms 264100 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<=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:148: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:161: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 34 ms 35576 KB Output is correct
2 Correct 34 ms 35576 KB Output is correct
3 Correct 34 ms 35576 KB Output is correct
4 Correct 34 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 34 ms 35960 KB Output is correct
8 Correct 36 ms 35960 KB Output is correct
9 Correct 36 ms 35960 KB Output is correct
10 Correct 36 ms 35960 KB Output is correct
11 Correct 31 ms 35808 KB Output is correct
12 Correct 35 ms 35832 KB Output is correct
13 Correct 30 ms 35804 KB Output is correct
14 Correct 31 ms 35832 KB Output is correct
15 Correct 29 ms 35960 KB Output is correct
16 Correct 30 ms 35960 KB Output is correct
17 Correct 37 ms 35960 KB Output is correct
18 Correct 36 ms 35960 KB Output is correct
19 Correct 35 ms 35960 KB Output is correct
20 Correct 36 ms 35912 KB Output is correct
21 Correct 34 ms 35832 KB Output is correct
22 Correct 35 ms 35960 KB Output is correct
23 Correct 35 ms 35960 KB Output is correct
24 Correct 36 ms 35960 KB Output is correct
25 Correct 35 ms 35896 KB Output is correct
26 Correct 35 ms 35960 KB Output is correct
27 Correct 29 ms 35832 KB Output is correct
28 Correct 30 ms 35832 KB Output is correct
29 Correct 30 ms 35832 KB Output is correct
30 Correct 34 ms 35832 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35576 KB Output is correct
2 Correct 34 ms 35576 KB Output is correct
3 Correct 34 ms 35576 KB Output is correct
4 Correct 34 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 34 ms 35960 KB Output is correct
8 Correct 36 ms 35960 KB Output is correct
9 Correct 36 ms 35960 KB Output is correct
10 Correct 36 ms 35960 KB Output is correct
11 Correct 31 ms 35808 KB Output is correct
12 Correct 35 ms 35832 KB Output is correct
13 Correct 30 ms 35804 KB Output is correct
14 Correct 31 ms 35832 KB Output is correct
15 Correct 29 ms 35960 KB Output is correct
16 Correct 30 ms 35960 KB Output is correct
17 Correct 37 ms 35960 KB Output is correct
18 Correct 36 ms 35960 KB Output is correct
19 Correct 35 ms 35960 KB Output is correct
20 Correct 36 ms 35912 KB Output is correct
21 Correct 34 ms 35832 KB Output is correct
22 Correct 35 ms 35960 KB Output is correct
23 Correct 35 ms 35960 KB Output is correct
24 Correct 36 ms 35960 KB Output is correct
25 Correct 35 ms 35896 KB Output is correct
26 Correct 35 ms 35960 KB Output is correct
27 Correct 29 ms 35832 KB Output is correct
28 Correct 30 ms 35832 KB Output is correct
29 Correct 30 ms 35832 KB Output is correct
30 Correct 34 ms 35832 KB Output is correct
31 Correct 618 ms 72684 KB Output is correct
32 Correct 124 ms 46436 KB Output is correct
33 Correct 629 ms 71468 KB Output is correct
34 Correct 540 ms 71596 KB Output is correct
35 Correct 603 ms 72932 KB Output is correct
36 Correct 627 ms 72532 KB Output is correct
37 Correct 464 ms 71344 KB Output is correct
38 Correct 490 ms 71336 KB Output is correct
39 Correct 403 ms 71168 KB Output is correct
40 Correct 435 ms 71220 KB Output is correct
41 Correct 554 ms 72528 KB Output is correct
42 Correct 530 ms 72360 KB Output is correct
43 Correct 115 ms 51072 KB Output is correct
44 Correct 565 ms 72516 KB Output is correct
45 Correct 551 ms 72496 KB Output is correct
46 Correct 514 ms 72640 KB Output is correct
47 Correct 296 ms 69788 KB Output is correct
48 Correct 294 ms 69888 KB Output is correct
49 Correct 308 ms 71088 KB Output is correct
50 Correct 333 ms 71464 KB Output is correct
51 Correct 357 ms 70984 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3422 ms 187756 KB Output is correct
2 Correct 3791 ms 178956 KB Output is correct
3 Correct 2955 ms 236452 KB Output is correct
4 Correct 3428 ms 194752 KB Output is correct
5 Correct 3505 ms 178396 KB Output is correct
6 Correct 3745 ms 178760 KB Output is correct
7 Correct 2706 ms 236252 KB Output is correct
8 Correct 2756 ms 196892 KB Output is correct
9 Correct 2672 ms 185220 KB Output is correct
10 Correct 2857 ms 180804 KB Output is correct
11 Correct 1638 ms 177868 KB Output is correct
12 Correct 1877 ms 179776 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4133 ms 200572 KB Output is correct
2 Correct 700 ms 108348 KB Output is correct
3 Correct 4287 ms 199620 KB Output is correct
4 Correct 3478 ms 234184 KB Output is correct
5 Correct 4288 ms 202436 KB Output is correct
6 Correct 4132 ms 206596 KB Output is correct
7 Correct 4630 ms 198860 KB Output is correct
8 Correct 3792 ms 199316 KB Output is correct
9 Correct 2359 ms 235128 KB Output is correct
10 Correct 3710 ms 201820 KB Output is correct
11 Correct 3822 ms 199036 KB Output is correct
12 Correct 4033 ms 197668 KB Output is correct
13 Correct 1755 ms 192508 KB Output is correct
14 Correct 1740 ms 191108 KB Output is correct
15 Correct 1961 ms 194688 KB Output is correct
16 Correct 2284 ms 196908 KB Output is correct
17 Correct 2219 ms 193756 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35576 KB Output is correct
2 Correct 34 ms 35576 KB Output is correct
3 Correct 34 ms 35576 KB Output is correct
4 Correct 34 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 34 ms 35960 KB Output is correct
8 Correct 36 ms 35960 KB Output is correct
9 Correct 36 ms 35960 KB Output is correct
10 Correct 36 ms 35960 KB Output is correct
11 Correct 31 ms 35808 KB Output is correct
12 Correct 35 ms 35832 KB Output is correct
13 Correct 30 ms 35804 KB Output is correct
14 Correct 31 ms 35832 KB Output is correct
15 Correct 29 ms 35960 KB Output is correct
16 Correct 30 ms 35960 KB Output is correct
17 Correct 37 ms 35960 KB Output is correct
18 Correct 36 ms 35960 KB Output is correct
19 Correct 35 ms 35960 KB Output is correct
20 Correct 36 ms 35912 KB Output is correct
21 Correct 34 ms 35832 KB Output is correct
22 Correct 35 ms 35960 KB Output is correct
23 Correct 35 ms 35960 KB Output is correct
24 Correct 36 ms 35960 KB Output is correct
25 Correct 35 ms 35896 KB Output is correct
26 Correct 35 ms 35960 KB Output is correct
27 Correct 29 ms 35832 KB Output is correct
28 Correct 30 ms 35832 KB Output is correct
29 Correct 30 ms 35832 KB Output is correct
30 Correct 34 ms 35832 KB Output is correct
31 Correct 618 ms 72684 KB Output is correct
32 Correct 124 ms 46436 KB Output is correct
33 Correct 629 ms 71468 KB Output is correct
34 Correct 540 ms 71596 KB Output is correct
35 Correct 603 ms 72932 KB Output is correct
36 Correct 627 ms 72532 KB Output is correct
37 Correct 464 ms 71344 KB Output is correct
38 Correct 490 ms 71336 KB Output is correct
39 Correct 403 ms 71168 KB Output is correct
40 Correct 435 ms 71220 KB Output is correct
41 Correct 554 ms 72528 KB Output is correct
42 Correct 530 ms 72360 KB Output is correct
43 Correct 115 ms 51072 KB Output is correct
44 Correct 565 ms 72516 KB Output is correct
45 Correct 551 ms 72496 KB Output is correct
46 Correct 514 ms 72640 KB Output is correct
47 Correct 296 ms 69788 KB Output is correct
48 Correct 294 ms 69888 KB Output is correct
49 Correct 308 ms 71088 KB Output is correct
50 Correct 333 ms 71464 KB Output is correct
51 Correct 357 ms 70984 KB Output is correct
52 Correct 544 ms 78512 KB Output is correct
53 Correct 461 ms 76216 KB Output is correct
54 Correct 556 ms 73648 KB Output is correct
55 Correct 540 ms 74424 KB Output is correct
56 Correct 517 ms 75548 KB Output is correct
57 Correct 543 ms 72744 KB Output is correct
58 Correct 548 ms 73656 KB Output is correct
59 Correct 523 ms 74856 KB Output is correct
60 Correct 494 ms 72504 KB Output is correct
61 Correct 137 ms 64476 KB Output is correct
62 Correct 542 ms 78552 KB Output is correct
63 Correct 523 ms 75532 KB Output is correct
64 Correct 562 ms 74528 KB Output is correct
65 Correct 713 ms 73088 KB Output is correct
66 Correct 547 ms 72104 KB Output is correct
67 Correct 184 ms 50068 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35576 KB Output is correct
2 Correct 34 ms 35576 KB Output is correct
3 Correct 34 ms 35576 KB Output is correct
4 Correct 34 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 34 ms 35960 KB Output is correct
8 Correct 36 ms 35960 KB Output is correct
9 Correct 36 ms 35960 KB Output is correct
10 Correct 36 ms 35960 KB Output is correct
11 Correct 31 ms 35808 KB Output is correct
12 Correct 35 ms 35832 KB Output is correct
13 Correct 30 ms 35804 KB Output is correct
14 Correct 31 ms 35832 KB Output is correct
15 Correct 29 ms 35960 KB Output is correct
16 Correct 30 ms 35960 KB Output is correct
17 Correct 37 ms 35960 KB Output is correct
18 Correct 36 ms 35960 KB Output is correct
19 Correct 35 ms 35960 KB Output is correct
20 Correct 36 ms 35912 KB Output is correct
21 Correct 34 ms 35832 KB Output is correct
22 Correct 35 ms 35960 KB Output is correct
23 Correct 35 ms 35960 KB Output is correct
24 Correct 36 ms 35960 KB Output is correct
25 Correct 35 ms 35896 KB Output is correct
26 Correct 35 ms 35960 KB Output is correct
27 Correct 29 ms 35832 KB Output is correct
28 Correct 30 ms 35832 KB Output is correct
29 Correct 30 ms 35832 KB Output is correct
30 Correct 34 ms 35832 KB Output is correct
31 Correct 618 ms 72684 KB Output is correct
32 Correct 124 ms 46436 KB Output is correct
33 Correct 629 ms 71468 KB Output is correct
34 Correct 540 ms 71596 KB Output is correct
35 Correct 603 ms 72932 KB Output is correct
36 Correct 627 ms 72532 KB Output is correct
37 Correct 464 ms 71344 KB Output is correct
38 Correct 490 ms 71336 KB Output is correct
39 Correct 403 ms 71168 KB Output is correct
40 Correct 435 ms 71220 KB Output is correct
41 Correct 554 ms 72528 KB Output is correct
42 Correct 530 ms 72360 KB Output is correct
43 Correct 115 ms 51072 KB Output is correct
44 Correct 565 ms 72516 KB Output is correct
45 Correct 551 ms 72496 KB Output is correct
46 Correct 514 ms 72640 KB Output is correct
47 Correct 296 ms 69788 KB Output is correct
48 Correct 294 ms 69888 KB Output is correct
49 Correct 308 ms 71088 KB Output is correct
50 Correct 333 ms 71464 KB Output is correct
51 Correct 357 ms 70984 KB Output is correct
52 Correct 3422 ms 187756 KB Output is correct
53 Correct 3791 ms 178956 KB Output is correct
54 Correct 2955 ms 236452 KB Output is correct
55 Correct 3428 ms 194752 KB Output is correct
56 Correct 3505 ms 178396 KB Output is correct
57 Correct 3745 ms 178760 KB Output is correct
58 Correct 2706 ms 236252 KB Output is correct
59 Correct 2756 ms 196892 KB Output is correct
60 Correct 2672 ms 185220 KB Output is correct
61 Correct 2857 ms 180804 KB Output is correct
62 Correct 1638 ms 177868 KB Output is correct
63 Correct 1877 ms 179776 KB Output is correct
64 Correct 4133 ms 200572 KB Output is correct
65 Correct 700 ms 108348 KB Output is correct
66 Correct 4287 ms 199620 KB Output is correct
67 Correct 3478 ms 234184 KB Output is correct
68 Correct 4288 ms 202436 KB Output is correct
69 Correct 4132 ms 206596 KB Output is correct
70 Correct 4630 ms 198860 KB Output is correct
71 Correct 3792 ms 199316 KB Output is correct
72 Correct 2359 ms 235128 KB Output is correct
73 Correct 3710 ms 201820 KB Output is correct
74 Correct 3822 ms 199036 KB Output is correct
75 Correct 4033 ms 197668 KB Output is correct
76 Correct 1755 ms 192508 KB Output is correct
77 Correct 1740 ms 191108 KB Output is correct
78 Correct 1961 ms 194688 KB Output is correct
79 Correct 2284 ms 196908 KB Output is correct
80 Correct 2219 ms 193756 KB Output is correct
81 Correct 544 ms 78512 KB Output is correct
82 Correct 461 ms 76216 KB Output is correct
83 Correct 556 ms 73648 KB Output is correct
84 Correct 540 ms 74424 KB Output is correct
85 Correct 517 ms 75548 KB Output is correct
86 Correct 543 ms 72744 KB Output is correct
87 Correct 548 ms 73656 KB Output is correct
88 Correct 523 ms 74856 KB Output is correct
89 Correct 494 ms 72504 KB Output is correct
90 Correct 137 ms 64476 KB Output is correct
91 Correct 542 ms 78552 KB Output is correct
92 Correct 523 ms 75532 KB Output is correct
93 Correct 562 ms 74528 KB Output is correct
94 Correct 713 ms 73088 KB Output is correct
95 Correct 547 ms 72104 KB Output is correct
96 Correct 184 ms 50068 KB Output is correct
97 Correct 3701 ms 249132 KB Output is correct
98 Correct 757 ms 88800 KB Output is correct
99 Correct 4888 ms 211748 KB Output is correct
100 Correct 2873 ms 239168 KB Output is correct
101 Correct 3563 ms 226632 KB Output is correct
102 Correct 4613 ms 219148 KB Output is correct
103 Correct 3080 ms 224864 KB Output is correct
104 Correct 3371 ms 224356 KB Output is correct
105 Correct 2264 ms 224124 KB Output is correct
106 Correct 2371 ms 224200 KB Output is correct
107 Correct 3329 ms 242424 KB Output is correct
108 Correct 3207 ms 250584 KB Output is correct
109 Correct 3271 ms 234404 KB Output is correct
110 Correct 3295 ms 238924 KB Output is correct
111 Correct 3768 ms 248092 KB Output is correct
112 Correct 3268 ms 233112 KB Output is correct
113 Correct 620 ms 189904 KB Output is correct
114 Correct 3287 ms 264100 KB Output is correct
115 Correct 4429 ms 252136 KB Output is correct
116 Correct 4579 ms 243168 KB Output is correct
117 Correct 4471 ms 234948 KB Output is correct
118 Correct 4589 ms 231220 KB Output is correct
119 Correct 1004 ms 105396 KB Output is correct
120 Correct 1291 ms 207296 KB Output is correct
121 Correct 1455 ms 221232 KB Output is correct
122 Correct 1504 ms 220100 KB Output is correct
123 Correct 1869 ms 224860 KB Output is correct
124 Correct 2062 ms 227920 KB Output is correct
125 Correct 2031 ms 225584 KB Output is correct
126 Correct 2113 ms 226612 KB Output is correct