답안 #99863 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99863	2019-03-07T23:00:57 Z	TadijaSebez	새 집 (APIO18_new_home)	C++11	47 / 100	5000 ms	619752 KB

new_home

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define mt make_tuple
const int N=300050;
const int M=4*N;
const int lim=1e8;
int x[N],t[N],l[N],r[N],qx[N],qy[N],active,ans[N];
set<pair<int,int>> all[N];
map<pair<int,int>,int> T[N];
vector<tuple<int,int,int,int>> L,R;
void Put(int t, int l, int r, int ins, int tme)
{
	int mid=l+r>>1;
	if(l>r) return;
	if(ins==0)
	{
		if(l!=-2*lim) T[t][mp(l,mid)]=tme;
		if(r!=2*lim) T[t][mp(mid+1,r)]=tme;
	}
	else
	{
		if(l!=-2*lim) L.pb(mt(T[t][mp(l,mid)],tme-1,l,mid));
		if(r!=2*lim) R.pb(mt(T[t][mp(mid+1,r)],tme-1,mid+1,r));
	}
}
int root,ls[M],rs[M],tsz;
vector<pair<int,int>> LST[M],RST[M];
vector<tuple<int,int,int>> STL[M],STR[M];
void AddL(int &c, int ss, int se, int qs, int qe, int l, int r)
{
	if(qs>qe || qs>se || ss>qe) return;
	if(!c) c=++tsz;
	if(qs<=ss && qe>=se){ LST[c].pb(mp(l,r));return;}
	int mid=ss+se>>1;
	AddL(ls[c],ss,mid,qs,qe,l,r);
	AddL(rs[c],mid+1,se,qs,qe,l,r);
}
void AddR(int &c, int ss, int se, int qs, int qe, int l, int r)
{
	if(qs>qe || qs>se || ss>qe) return;
	if(!c) c=++tsz;
	if(qs<=ss && qe>=se){ RST[c].pb(mp(l,r));return;}
	int mid=ss+se>>1;
	AddR(ls[c],ss,mid,qs,qe,l,r);
	AddR(rs[c],mid+1,se,qs,qe,l,r);
}
void Build(int c, int ss, int se)
{
	if(!c) return;
	STL[c].reserve(LST[c].size());
	int mx=-lim;
	for(int i=0;i<LST[c].size();i++)
	{
		if(LST[c][i].second>=mx)
		{
			STL[c].pb(mt(max(LST[c][i].first,mx),LST[c][i].second,LST[c][i].first));
			mx=LST[c][i].second+1;
			//printf("%i %i %i\n",get<0>(STL[c].back()),get<1>(STL[c].back()),get<2>(STL[c].back()));
		}
	}
	STR[c].reserve(RST[c].size());
	int mn=lim*2;
	for(int i=0;i<RST[c].size();i++)
	{
		if(RST[c][i].first<=mn)
		{
			STR[c].pb(mt(RST[c][i].first,min(RST[c][i].second,mn),RST[c][i].second));
			mn=RST[c][i].first-1;
			//printf("%i %i %i\n",get<0>(STR[c].back()),get<1>(STR[c].back()),get<2>(STR[c].back()));
		}
	}
	reverse(STR[c].begin(),STR[c].end());
	if(ss==se) return;
	int mid=ss+se>>1;
	Build(ls[c],ss,mid);
	Build(rs[c],mid+1,se);
}
int Solve(int c, int ss, int se, int qi, int x)
{
	int ans=0;
	while(STL[c].size() && get<0>(STL[c].back())>x) STL[c].pop_back();
	while(STR[c].size() && get<0>(STR[c].back())>x) STR[c].pop_back();
	if(STL[c].size() && get<1>(STL[c].back())>=x) ans=max(ans,x-get<2>(STL[c].back()));
	if(STR[c].size() && get<1>(STR[c].back())>=x) ans=max(ans,get<2>(STR[c].back())-x);
	if(ss==se) return ans;
	int mid=ss+se>>1;
	if(qi<=mid) return max(ans,Solve(ls[c],ss,mid,qi,x));
	else return max(ans,Solve(rs[c],mid+1,se,qi,x));
}
int main()
{
	int n,k,q,i;
	scanf("%i %i %i",&n,&k,&q);
	vector<tuple<int,int,int>> events;
	for(i=1;i<=n;i++)
	{
		scanf("%i %i %i %i",&x[i],&t[i],&l[i],&r[i]);
		events.pb(mt(l[i],0,i));
		events.pb(mt(r[i]+1,1,i));
	}
	for(i=1;i<=q;i++)
	{
		scanf("%i %i",&qx[i],&qy[i]);
		events.pb(mt(qy[i],2,i));
	}
	for(i=1;i<=k;i++)
	{
		all[i].insert(mp(-2*lim,-1));
		all[i].insert(mp(2*lim,0));
		Put(i,-2*lim,2*lim,0,2*lim);
	}
	sort(events.begin(),events.end());
	vector<int> work;
	for(auto e:events)
	{
		int tme=get<0>(e);
		int type=get<1>(e);
		int i=get<2>(e);
		if(type!=2)
		{
			if(type==0) all[t[i]].insert(mp(x[i],i));
			auto it=all[t[i]].find(mp(x[i],i));
			int lid=0,rid=0;
			if(it!=all[t[i]].begin()) it--,lid=it->first,it++;
			it++;if(it!=all[t[i]].end()) rid=it->first;it--;
			if(type==0) Put(t[i],lid,rid,type^1,tme);
			Put(t[i],lid,x[i],type,tme);
			Put(t[i],x[i],rid,type,tme);
			if(type==1) Put(t[i],lid,rid,type^1,tme);
			if(all[t[i]].size()==3) active+=type==0?1:-1;
			if(type==1) all[t[i]].erase(mp(x[i],i));
		}
		else
		{
			if(active!=k) ans[i]=-1;
			else work.pb(i);
		}
		//printf("%i %i %i %i\n",tme,type,i,active);
	}
	sort(L.begin(),L.end(),[](tuple<int,int,int,int> a, tuple<int,int,int,int> b){ return get<2>(a)<get<2>(b);});
	sort(R.begin(),R.end(),[](tuple<int,int,int,int> a, tuple<int,int,int,int> b){ return get<3>(a)>get<3>(b);});
	sort(work.begin(),work.end(),[&](int a, int b){ return qx[a]>qx[b];});
	vector<int> id;
	for(auto tp:L) id.pb(get<0>(tp)),id.pb(get<1>(tp));
	for(auto tp:R) id.pb(get<0>(tp)),id.pb(get<1>(tp));
	for(int idx:work) id.pb(qy[idx]);
	sort(id.begin(),id.end());
	id.erase(unique(id.begin(),id.end()),id.end());
	auto Get=[&](int x){ return lower_bound(id.begin(),id.end(),x)-id.begin()+1;};
	for(auto tp:L) AddL(root,1,id.size(),Get(get<0>(tp)),Get(get<1>(tp)),get<2>(tp),get<3>(tp));
	for(auto tp:R) AddR(root,1,id.size(),Get(get<0>(tp)),Get(get<1>(tp)),get<2>(tp),get<3>(tp));
	Build(root,1,id.size());
	for(int idx:work) ans[idx]=Solve(root,1,id.size(),Get(qy[idx]),qx[idx]);
	for(int i=1;i<=q;i++) printf("%i\n",ans[i]);
	return 0;
}

Compilation message

new_home.cpp: In function 'void Put(int, int, int, int, int)':
new_home.cpp:15:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=l+r>>1;
          ~^~
new_home.cpp: In function 'void AddL(int&, int, int, int, int, int, int)':
new_home.cpp:36:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
new_home.cpp: In function 'void AddR(int&, int, int, int, int, int, int)':
new_home.cpp:45:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
new_home.cpp: In function 'void Build(int, int, int)':
new_home.cpp:54:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<LST[c].size();i++)
              ~^~~~~~~~~~~~~~
new_home.cpp:65:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<RST[c].size();i++)
              ~^~~~~~~~~~~~~~
new_home.cpp:76:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
new_home.cpp: In function 'int Solve(int, int, int, int, int)':
new_home.cpp:88:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&k,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
new_home.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i %i %i",&x[i],&t[i],&l[i],&r[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&qx[i],&qy[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	130 ms	141284 KB	Output is correct
2	Correct	130 ms	141304 KB	Output is correct
3	Correct	141 ms	141336 KB	Output is correct
4	Correct	143 ms	141304 KB	Output is correct
5	Correct	131 ms	141548 KB	Output is correct
6	Correct	149 ms	142056 KB	Output is correct
7	Correct	128 ms	141688 KB	Output is correct
8	Correct	129 ms	141820 KB	Output is correct
9	Correct	156 ms	141764 KB	Output is correct
10	Correct	135 ms	142160 KB	Output is correct
11	Correct	127 ms	141688 KB	Output is correct
12	Correct	178 ms	141820 KB	Output is correct
13	Correct	126 ms	141688 KB	Output is correct
14	Correct	127 ms	141764 KB	Output is correct
15	Correct	132 ms	141848 KB	Output is correct
16	Correct	137 ms	141816 KB	Output is correct
17	Correct	134 ms	142012 KB	Output is correct
18	Correct	139 ms	141816 KB	Output is correct
19	Correct	135 ms	141816 KB	Output is correct
20	Correct	133 ms	141816 KB	Output is correct
21	Correct	129 ms	141432 KB	Output is correct
22	Correct	132 ms	141604 KB	Output is correct
23	Correct	133 ms	141892 KB	Output is correct
24	Correct	144 ms	141788 KB	Output is correct
25	Correct	133 ms	141964 KB	Output is correct
26	Correct	129 ms	141716 KB	Output is correct
27	Correct	132 ms	141560 KB	Output is correct
28	Correct	134 ms	141688 KB	Output is correct
29	Correct	133 ms	141664 KB	Output is correct
30	Correct	158 ms	141536 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	130 ms	141284 KB	Output is correct
2	Correct	130 ms	141304 KB	Output is correct
3	Correct	141 ms	141336 KB	Output is correct
4	Correct	143 ms	141304 KB	Output is correct
5	Correct	131 ms	141548 KB	Output is correct
6	Correct	149 ms	142056 KB	Output is correct
7	Correct	128 ms	141688 KB	Output is correct
8	Correct	129 ms	141820 KB	Output is correct
9	Correct	156 ms	141764 KB	Output is correct
10	Correct	135 ms	142160 KB	Output is correct
11	Correct	127 ms	141688 KB	Output is correct
12	Correct	178 ms	141820 KB	Output is correct
13	Correct	126 ms	141688 KB	Output is correct
14	Correct	127 ms	141764 KB	Output is correct
15	Correct	132 ms	141848 KB	Output is correct
16	Correct	137 ms	141816 KB	Output is correct
17	Correct	134 ms	142012 KB	Output is correct
18	Correct	139 ms	141816 KB	Output is correct
19	Correct	135 ms	141816 KB	Output is correct
20	Correct	133 ms	141816 KB	Output is correct
21	Correct	129 ms	141432 KB	Output is correct
22	Correct	132 ms	141604 KB	Output is correct
23	Correct	133 ms	141892 KB	Output is correct
24	Correct	144 ms	141788 KB	Output is correct
25	Correct	133 ms	141964 KB	Output is correct
26	Correct	129 ms	141716 KB	Output is correct
27	Correct	132 ms	141560 KB	Output is correct
28	Correct	134 ms	141688 KB	Output is correct
29	Correct	133 ms	141664 KB	Output is correct
30	Correct	158 ms	141536 KB	Output is correct
31	Correct	2725 ms	296964 KB	Output is correct
32	Correct	327 ms	159704 KB	Output is correct
33	Correct	2620 ms	308500 KB	Output is correct
34	Correct	2870 ms	297108 KB	Output is correct
35	Correct	2920 ms	300760 KB	Output is correct
36	Correct	2636 ms	309380 KB	Output is correct
37	Correct	2095 ms	291340 KB	Output is correct
38	Correct	1786 ms	292576 KB	Output is correct
39	Correct	1274 ms	263336 KB	Output is correct
40	Correct	1306 ms	270680 KB	Output is correct
41	Correct	1965 ms	247864 KB	Output is correct
42	Correct	1871 ms	247260 KB	Output is correct
43	Correct	259 ms	158600 KB	Output is correct
44	Correct	1844 ms	245932 KB	Output is correct
45	Correct	1695 ms	236256 KB	Output is correct
46	Correct	1351 ms	218188 KB	Output is correct
47	Correct	617 ms	207712 KB	Output is correct
48	Correct	629 ms	206428 KB	Output is correct
49	Correct	817 ms	221020 KB	Output is correct
50	Correct	967 ms	236396 KB	Output is correct
51	Correct	840 ms	216872 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3030 ms	581952 KB	Output is correct
2	Execution timed out	5112 ms	619752 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5130 ms	421204 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	130 ms	141284 KB	Output is correct
2	Correct	130 ms	141304 KB	Output is correct
3	Correct	141 ms	141336 KB	Output is correct
4	Correct	143 ms	141304 KB	Output is correct
5	Correct	131 ms	141548 KB	Output is correct
6	Correct	149 ms	142056 KB	Output is correct
7	Correct	128 ms	141688 KB	Output is correct
8	Correct	129 ms	141820 KB	Output is correct
9	Correct	156 ms	141764 KB	Output is correct
10	Correct	135 ms	142160 KB	Output is correct
11	Correct	127 ms	141688 KB	Output is correct
12	Correct	178 ms	141820 KB	Output is correct
13	Correct	126 ms	141688 KB	Output is correct
14	Correct	127 ms	141764 KB	Output is correct
15	Correct	132 ms	141848 KB	Output is correct
16	Correct	137 ms	141816 KB	Output is correct
17	Correct	134 ms	142012 KB	Output is correct
18	Correct	139 ms	141816 KB	Output is correct
19	Correct	135 ms	141816 KB	Output is correct
20	Correct	133 ms	141816 KB	Output is correct
21	Correct	129 ms	141432 KB	Output is correct
22	Correct	132 ms	141604 KB	Output is correct
23	Correct	133 ms	141892 KB	Output is correct
24	Correct	144 ms	141788 KB	Output is correct
25	Correct	133 ms	141964 KB	Output is correct
26	Correct	129 ms	141716 KB	Output is correct
27	Correct	132 ms	141560 KB	Output is correct
28	Correct	134 ms	141688 KB	Output is correct
29	Correct	133 ms	141664 KB	Output is correct
30	Correct	158 ms	141536 KB	Output is correct
31	Correct	2725 ms	296964 KB	Output is correct
32	Correct	327 ms	159704 KB	Output is correct
33	Correct	2620 ms	308500 KB	Output is correct
34	Correct	2870 ms	297108 KB	Output is correct
35	Correct	2920 ms	300760 KB	Output is correct
36	Correct	2636 ms	309380 KB	Output is correct
37	Correct	2095 ms	291340 KB	Output is correct
38	Correct	1786 ms	292576 KB	Output is correct
39	Correct	1274 ms	263336 KB	Output is correct
40	Correct	1306 ms	270680 KB	Output is correct
41	Correct	1965 ms	247864 KB	Output is correct
42	Correct	1871 ms	247260 KB	Output is correct
43	Correct	259 ms	158600 KB	Output is correct
44	Correct	1844 ms	245932 KB	Output is correct
45	Correct	1695 ms	236256 KB	Output is correct
46	Correct	1351 ms	218188 KB	Output is correct
47	Correct	617 ms	207712 KB	Output is correct
48	Correct	629 ms	206428 KB	Output is correct
49	Correct	817 ms	221020 KB	Output is correct
50	Correct	967 ms	236396 KB	Output is correct
51	Correct	840 ms	216872 KB	Output is correct
52	Correct	832 ms	210252 KB	Output is correct
53	Correct	981 ms	211536 KB	Output is correct
54	Correct	1752 ms	254720 KB	Output is correct
55	Correct	1557 ms	239688 KB	Output is correct
56	Correct	1285 ms	233212 KB	Output is correct
57	Correct	1745 ms	245640 KB	Output is correct
58	Correct	1545 ms	239896 KB	Output is correct
59	Correct	1379 ms	234608 KB	Output is correct
60	Correct	1829 ms	245600 KB	Output is correct
61	Correct	288 ms	167396 KB	Output is correct
62	Correct	912 ms	219104 KB	Output is correct
63	Correct	1305 ms	243260 KB	Output is correct
64	Correct	1503 ms	251364 KB	Output is correct
65	Correct	1809 ms	260688 KB	Output is correct
66	Correct	1964 ms	254556 KB	Output is correct
67	Correct	476 ms	173760 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	130 ms	141284 KB	Output is correct
2	Correct	130 ms	141304 KB	Output is correct
3	Correct	141 ms	141336 KB	Output is correct
4	Correct	143 ms	141304 KB	Output is correct
5	Correct	131 ms	141548 KB	Output is correct
6	Correct	149 ms	142056 KB	Output is correct
7	Correct	128 ms	141688 KB	Output is correct
8	Correct	129 ms	141820 KB	Output is correct
9	Correct	156 ms	141764 KB	Output is correct
10	Correct	135 ms	142160 KB	Output is correct
11	Correct	127 ms	141688 KB	Output is correct
12	Correct	178 ms	141820 KB	Output is correct
13	Correct	126 ms	141688 KB	Output is correct
14	Correct	127 ms	141764 KB	Output is correct
15	Correct	132 ms	141848 KB	Output is correct
16	Correct	137 ms	141816 KB	Output is correct
17	Correct	134 ms	142012 KB	Output is correct
18	Correct	139 ms	141816 KB	Output is correct
19	Correct	135 ms	141816 KB	Output is correct
20	Correct	133 ms	141816 KB	Output is correct
21	Correct	129 ms	141432 KB	Output is correct
22	Correct	132 ms	141604 KB	Output is correct
23	Correct	133 ms	141892 KB	Output is correct
24	Correct	144 ms	141788 KB	Output is correct
25	Correct	133 ms	141964 KB	Output is correct
26	Correct	129 ms	141716 KB	Output is correct
27	Correct	132 ms	141560 KB	Output is correct
28	Correct	134 ms	141688 KB	Output is correct
29	Correct	133 ms	141664 KB	Output is correct
30	Correct	158 ms	141536 KB	Output is correct
31	Correct	2725 ms	296964 KB	Output is correct
32	Correct	327 ms	159704 KB	Output is correct
33	Correct	2620 ms	308500 KB	Output is correct
34	Correct	2870 ms	297108 KB	Output is correct
35	Correct	2920 ms	300760 KB	Output is correct
36	Correct	2636 ms	309380 KB	Output is correct
37	Correct	2095 ms	291340 KB	Output is correct
38	Correct	1786 ms	292576 KB	Output is correct
39	Correct	1274 ms	263336 KB	Output is correct
40	Correct	1306 ms	270680 KB	Output is correct
41	Correct	1965 ms	247864 KB	Output is correct
42	Correct	1871 ms	247260 KB	Output is correct
43	Correct	259 ms	158600 KB	Output is correct
44	Correct	1844 ms	245932 KB	Output is correct
45	Correct	1695 ms	236256 KB	Output is correct
46	Correct	1351 ms	218188 KB	Output is correct
47	Correct	617 ms	207712 KB	Output is correct
48	Correct	629 ms	206428 KB	Output is correct
49	Correct	817 ms	221020 KB	Output is correct
50	Correct	967 ms	236396 KB	Output is correct
51	Correct	840 ms	216872 KB	Output is correct
52	Correct	3030 ms	581952 KB	Output is correct
53	Execution timed out	5112 ms	619752 KB	Time limit exceeded
54	Halted	0 ms	0 KB	-

답안 #99863

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 0 / 10.0

Subtask #4 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
0 / 10.0

Subtask #4
0 / 23.0

Subtask #5
35.0 / 35.0

Subtask #6
0 / 20.0