답안 #94797 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
94797	2019-01-24T05:25:24 Z	jangwonyoung	새 집 (APIO18_new_home)	C++14	80 / 100	5000 ms	272844 KB

new_home

#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(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));
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> k >> 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;cin >> x >> tp >> u >> 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++){
		cin >> b[i].fi.fi >> 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:130: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:143: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

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	35576 KB	Output is correct
2	Correct	28 ms	35576 KB	Output is correct
3	Correct	29 ms	35576 KB	Output is correct
4	Correct	28 ms	35576 KB	Output is correct
5	Correct	29 ms	35704 KB	Output is correct
6	Correct	31 ms	35888 KB	Output is correct
7	Correct	30 ms	35960 KB	Output is correct
8	Correct	30 ms	35960 KB	Output is correct
9	Correct	31 ms	36088 KB	Output is correct
10	Correct	78 ms	35960 KB	Output is correct
11	Correct	30 ms	35960 KB	Output is correct
12	Correct	88 ms	36052 KB	Output is correct
13	Correct	32 ms	35960 KB	Output is correct
14	Correct	30 ms	35960 KB	Output is correct
15	Correct	31 ms	35960 KB	Output is correct
16	Correct	31 ms	35940 KB	Output is correct
17	Correct	31 ms	35960 KB	Output is correct
18	Correct	31 ms	35960 KB	Output is correct
19	Correct	72 ms	35960 KB	Output is correct
20	Correct	30 ms	35960 KB	Output is correct
21	Correct	30 ms	35960 KB	Output is correct
22	Correct	38 ms	36088 KB	Output is correct
23	Correct	35 ms	36040 KB	Output is correct
24	Correct	36 ms	35960 KB	Output is correct
25	Correct	37 ms	35960 KB	Output is correct
26	Correct	36 ms	35928 KB	Output is correct
27	Correct	37 ms	35832 KB	Output is correct
28	Correct	35 ms	35960 KB	Output is correct
29	Correct	35 ms	35876 KB	Output is correct
30	Correct	35 ms	35836 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	35576 KB	Output is correct
2	Correct	28 ms	35576 KB	Output is correct
3	Correct	29 ms	35576 KB	Output is correct
4	Correct	28 ms	35576 KB	Output is correct
5	Correct	29 ms	35704 KB	Output is correct
6	Correct	31 ms	35888 KB	Output is correct
7	Correct	30 ms	35960 KB	Output is correct
8	Correct	30 ms	35960 KB	Output is correct
9	Correct	31 ms	36088 KB	Output is correct
10	Correct	78 ms	35960 KB	Output is correct
11	Correct	30 ms	35960 KB	Output is correct
12	Correct	88 ms	36052 KB	Output is correct
13	Correct	32 ms	35960 KB	Output is correct
14	Correct	30 ms	35960 KB	Output is correct
15	Correct	31 ms	35960 KB	Output is correct
16	Correct	31 ms	35940 KB	Output is correct
17	Correct	31 ms	35960 KB	Output is correct
18	Correct	31 ms	35960 KB	Output is correct
19	Correct	72 ms	35960 KB	Output is correct
20	Correct	30 ms	35960 KB	Output is correct
21	Correct	30 ms	35960 KB	Output is correct
22	Correct	38 ms	36088 KB	Output is correct
23	Correct	35 ms	36040 KB	Output is correct
24	Correct	36 ms	35960 KB	Output is correct
25	Correct	37 ms	35960 KB	Output is correct
26	Correct	36 ms	35928 KB	Output is correct
27	Correct	37 ms	35832 KB	Output is correct
28	Correct	35 ms	35960 KB	Output is correct
29	Correct	35 ms	35876 KB	Output is correct
30	Correct	35 ms	35836 KB	Output is correct
31	Correct	767 ms	75116 KB	Output is correct
32	Correct	154 ms	52004 KB	Output is correct
33	Correct	742 ms	73236 KB	Output is correct
34	Correct	771 ms	73080 KB	Output is correct
35	Correct	774 ms	74996 KB	Output is correct
36	Correct	740 ms	75176 KB	Output is correct
37	Correct	564 ms	72308 KB	Output is correct
38	Correct	485 ms	72104 KB	Output is correct
39	Correct	381 ms	71992 KB	Output is correct
40	Correct	400 ms	71980 KB	Output is correct
41	Correct	507 ms	72732 KB	Output is correct
42	Correct	512 ms	72940 KB	Output is correct
43	Correct	128 ms	57476 KB	Output is correct
44	Correct	506 ms	72840 KB	Output is correct
45	Correct	556 ms	72960 KB	Output is correct
46	Correct	525 ms	72964 KB	Output is correct
47	Correct	286 ms	70680 KB	Output is correct
48	Correct	306 ms	70784 KB	Output is correct
49	Correct	311 ms	71592 KB	Output is correct
50	Correct	393 ms	72212 KB	Output is correct
51	Correct	358 ms	71600 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3513 ms	195668 KB	Output is correct
2	Correct	2998 ms	187240 KB	Output is correct
3	Correct	2414 ms	245908 KB	Output is correct
4	Correct	2754 ms	203588 KB	Output is correct
5	Correct	2775 ms	187064 KB	Output is correct
6	Correct	3174 ms	187484 KB	Output is correct
7	Correct	2729 ms	245464 KB	Output is correct
8	Correct	2193 ms	206440 KB	Output is correct
9	Correct	2482 ms	194888 KB	Output is correct
10	Correct	2716 ms	189948 KB	Output is correct
11	Correct	1669 ms	187112 KB	Output is correct
12	Correct	1880 ms	189144 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4122 ms	210172 KB	Output is correct
2	Correct	900 ms	137172 KB	Output is correct
3	Correct	3977 ms	208676 KB	Output is correct
4	Correct	2884 ms	243596 KB	Output is correct
5	Correct	3582 ms	212172 KB	Output is correct
6	Correct	3470 ms	216040 KB	Output is correct
7	Correct	3704 ms	208296 KB	Output is correct
8	Correct	4594 ms	208568 KB	Output is correct
9	Correct	2941 ms	244388 KB	Output is correct
10	Correct	3947 ms	210988 KB	Output is correct
11	Correct	4608 ms	208548 KB	Output is correct
12	Correct	3906 ms	207104 KB	Output is correct
13	Correct	1703 ms	201532 KB	Output is correct
14	Correct	1639 ms	199808 KB	Output is correct
15	Correct	2132 ms	203760 KB	Output is correct
16	Correct	2390 ms	205952 KB	Output is correct
17	Correct	2335 ms	202712 KB	Output is correct

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	35576 KB	Output is correct
2	Correct	28 ms	35576 KB	Output is correct
3	Correct	29 ms	35576 KB	Output is correct
4	Correct	28 ms	35576 KB	Output is correct
5	Correct	29 ms	35704 KB	Output is correct
6	Correct	31 ms	35888 KB	Output is correct
7	Correct	30 ms	35960 KB	Output is correct
8	Correct	30 ms	35960 KB	Output is correct
9	Correct	31 ms	36088 KB	Output is correct
10	Correct	78 ms	35960 KB	Output is correct
11	Correct	30 ms	35960 KB	Output is correct
12	Correct	88 ms	36052 KB	Output is correct
13	Correct	32 ms	35960 KB	Output is correct
14	Correct	30 ms	35960 KB	Output is correct
15	Correct	31 ms	35960 KB	Output is correct
16	Correct	31 ms	35940 KB	Output is correct
17	Correct	31 ms	35960 KB	Output is correct
18	Correct	31 ms	35960 KB	Output is correct
19	Correct	72 ms	35960 KB	Output is correct
20	Correct	30 ms	35960 KB	Output is correct
21	Correct	30 ms	35960 KB	Output is correct
22	Correct	38 ms	36088 KB	Output is correct
23	Correct	35 ms	36040 KB	Output is correct
24	Correct	36 ms	35960 KB	Output is correct
25	Correct	37 ms	35960 KB	Output is correct
26	Correct	36 ms	35928 KB	Output is correct
27	Correct	37 ms	35832 KB	Output is correct
28	Correct	35 ms	35960 KB	Output is correct
29	Correct	35 ms	35876 KB	Output is correct
30	Correct	35 ms	35836 KB	Output is correct
31	Correct	767 ms	75116 KB	Output is correct
32	Correct	154 ms	52004 KB	Output is correct
33	Correct	742 ms	73236 KB	Output is correct
34	Correct	771 ms	73080 KB	Output is correct
35	Correct	774 ms	74996 KB	Output is correct
36	Correct	740 ms	75176 KB	Output is correct
37	Correct	564 ms	72308 KB	Output is correct
38	Correct	485 ms	72104 KB	Output is correct
39	Correct	381 ms	71992 KB	Output is correct
40	Correct	400 ms	71980 KB	Output is correct
41	Correct	507 ms	72732 KB	Output is correct
42	Correct	512 ms	72940 KB	Output is correct
43	Correct	128 ms	57476 KB	Output is correct
44	Correct	506 ms	72840 KB	Output is correct
45	Correct	556 ms	72960 KB	Output is correct
46	Correct	525 ms	72964 KB	Output is correct
47	Correct	286 ms	70680 KB	Output is correct
48	Correct	306 ms	70784 KB	Output is correct
49	Correct	311 ms	71592 KB	Output is correct
50	Correct	393 ms	72212 KB	Output is correct
51	Correct	358 ms	71600 KB	Output is correct
52	Correct	534 ms	82284 KB	Output is correct
53	Correct	524 ms	80452 KB	Output is correct
54	Correct	614 ms	77532 KB	Output is correct
55	Correct	500 ms	76892 KB	Output is correct
56	Correct	493 ms	78392 KB	Output is correct
57	Correct	554 ms	74664 KB	Output is correct
58	Correct	501 ms	76640 KB	Output is correct
59	Correct	484 ms	78136 KB	Output is correct
60	Correct	593 ms	74920 KB	Output is correct
61	Correct	192 ms	71652 KB	Output is correct
62	Correct	494 ms	82416 KB	Output is correct
63	Correct	682 ms	78980 KB	Output is correct
64	Correct	676 ms	77880 KB	Output is correct
65	Correct	642 ms	75048 KB	Output is correct
66	Correct	540 ms	74148 KB	Output is correct
67	Correct	205 ms	56308 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	35576 KB	Output is correct
2	Correct	28 ms	35576 KB	Output is correct
3	Correct	29 ms	35576 KB	Output is correct
4	Correct	28 ms	35576 KB	Output is correct
5	Correct	29 ms	35704 KB	Output is correct
6	Correct	31 ms	35888 KB	Output is correct
7	Correct	30 ms	35960 KB	Output is correct
8	Correct	30 ms	35960 KB	Output is correct
9	Correct	31 ms	36088 KB	Output is correct
10	Correct	78 ms	35960 KB	Output is correct
11	Correct	30 ms	35960 KB	Output is correct
12	Correct	88 ms	36052 KB	Output is correct
13	Correct	32 ms	35960 KB	Output is correct
14	Correct	30 ms	35960 KB	Output is correct
15	Correct	31 ms	35960 KB	Output is correct
16	Correct	31 ms	35940 KB	Output is correct
17	Correct	31 ms	35960 KB	Output is correct
18	Correct	31 ms	35960 KB	Output is correct
19	Correct	72 ms	35960 KB	Output is correct
20	Correct	30 ms	35960 KB	Output is correct
21	Correct	30 ms	35960 KB	Output is correct
22	Correct	38 ms	36088 KB	Output is correct
23	Correct	35 ms	36040 KB	Output is correct
24	Correct	36 ms	35960 KB	Output is correct
25	Correct	37 ms	35960 KB	Output is correct
26	Correct	36 ms	35928 KB	Output is correct
27	Correct	37 ms	35832 KB	Output is correct
28	Correct	35 ms	35960 KB	Output is correct
29	Correct	35 ms	35876 KB	Output is correct
30	Correct	35 ms	35836 KB	Output is correct
31	Correct	767 ms	75116 KB	Output is correct
32	Correct	154 ms	52004 KB	Output is correct
33	Correct	742 ms	73236 KB	Output is correct
34	Correct	771 ms	73080 KB	Output is correct
35	Correct	774 ms	74996 KB	Output is correct
36	Correct	740 ms	75176 KB	Output is correct
37	Correct	564 ms	72308 KB	Output is correct
38	Correct	485 ms	72104 KB	Output is correct
39	Correct	381 ms	71992 KB	Output is correct
40	Correct	400 ms	71980 KB	Output is correct
41	Correct	507 ms	72732 KB	Output is correct
42	Correct	512 ms	72940 KB	Output is correct
43	Correct	128 ms	57476 KB	Output is correct
44	Correct	506 ms	72840 KB	Output is correct
45	Correct	556 ms	72960 KB	Output is correct
46	Correct	525 ms	72964 KB	Output is correct
47	Correct	286 ms	70680 KB	Output is correct
48	Correct	306 ms	70784 KB	Output is correct
49	Correct	311 ms	71592 KB	Output is correct
50	Correct	393 ms	72212 KB	Output is correct
51	Correct	358 ms	71600 KB	Output is correct
52	Correct	3513 ms	195668 KB	Output is correct
53	Correct	2998 ms	187240 KB	Output is correct
54	Correct	2414 ms	245908 KB	Output is correct
55	Correct	2754 ms	203588 KB	Output is correct
56	Correct	2775 ms	187064 KB	Output is correct
57	Correct	3174 ms	187484 KB	Output is correct
58	Correct	2729 ms	245464 KB	Output is correct
59	Correct	2193 ms	206440 KB	Output is correct
60	Correct	2482 ms	194888 KB	Output is correct
61	Correct	2716 ms	189948 KB	Output is correct
62	Correct	1669 ms	187112 KB	Output is correct
63	Correct	1880 ms	189144 KB	Output is correct
64	Correct	4122 ms	210172 KB	Output is correct
65	Correct	900 ms	137172 KB	Output is correct
66	Correct	3977 ms	208676 KB	Output is correct
67	Correct	2884 ms	243596 KB	Output is correct
68	Correct	3582 ms	212172 KB	Output is correct
69	Correct	3470 ms	216040 KB	Output is correct
70	Correct	3704 ms	208296 KB	Output is correct
71	Correct	4594 ms	208568 KB	Output is correct
72	Correct	2941 ms	244388 KB	Output is correct
73	Correct	3947 ms	210988 KB	Output is correct
74	Correct	4608 ms	208548 KB	Output is correct
75	Correct	3906 ms	207104 KB	Output is correct
76	Correct	1703 ms	201532 KB	Output is correct
77	Correct	1639 ms	199808 KB	Output is correct
78	Correct	2132 ms	203760 KB	Output is correct
79	Correct	2390 ms	205952 KB	Output is correct
80	Correct	2335 ms	202712 KB	Output is correct
81	Correct	534 ms	82284 KB	Output is correct
82	Correct	524 ms	80452 KB	Output is correct
83	Correct	614 ms	77532 KB	Output is correct
84	Correct	500 ms	76892 KB	Output is correct
85	Correct	493 ms	78392 KB	Output is correct
86	Correct	554 ms	74664 KB	Output is correct
87	Correct	501 ms	76640 KB	Output is correct
88	Correct	484 ms	78136 KB	Output is correct
89	Correct	593 ms	74920 KB	Output is correct
90	Correct	192 ms	71652 KB	Output is correct
91	Correct	494 ms	82416 KB	Output is correct
92	Correct	682 ms	78980 KB	Output is correct
93	Correct	676 ms	77880 KB	Output is correct
94	Correct	642 ms	75048 KB	Output is correct
95	Correct	540 ms	74148 KB	Output is correct
96	Correct	205 ms	56308 KB	Output is correct
97	Correct	3934 ms	272844 KB	Output is correct
98	Correct	855 ms	120296 KB	Output is correct
99	Correct	4983 ms	230160 KB	Output is correct
100	Correct	3119 ms	264120 KB	Output is correct
101	Correct	4041 ms	248508 KB	Output is correct
102	Execution timed out	5057 ms	238372 KB	Time limit exceeded
103	Halted	0 ms	0 KB	-

답안 #94797

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 10.0 / 10.0

Subtask #4 23.0 / 23.0

Subtask #5 35.0 / 35.0

Subtask #6 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
10.0 / 10.0

Subtask #4
23.0 / 23.0

Subtask #5
35.0 / 35.0

Subtask #6
0 / 20.0