답안 #99862 :: oj.uz

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

new_home

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#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;
	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()));
		}
	}
	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:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
new_home.cpp: In function 'void Put(int, int, int, int, int)':
new_home.cpp:18: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:39: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:48: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:56:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<LST[c].size();i++)
              ~^~~~~~~~~~~~~~
new_home.cpp:66:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<RST[c].size();i++)
              ~^~~~~~~~~~~~~~
new_home.cpp:77: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:89:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:96: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:100: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:106: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	134 ms	141304 KB	Output is correct
2	Correct	134 ms	141304 KB	Output is correct
3	Correct	131 ms	141304 KB	Output is correct
4	Correct	130 ms	141304 KB	Output is correct
5	Correct	134 ms	141408 KB	Output is correct
6	Correct	142 ms	142072 KB	Output is correct
7	Correct	142 ms	141708 KB	Output is correct
8	Correct	137 ms	141944 KB	Output is correct
9	Correct	140 ms	141716 KB	Output is correct
10	Correct	158 ms	142172 KB	Output is correct
11	Correct	142 ms	141776 KB	Output is correct
12	Correct	133 ms	141820 KB	Output is correct
13	Correct	138 ms	141484 KB	Output is correct
14	Correct	131 ms	141668 KB	Output is correct
15	Correct	133 ms	141788 KB	Output is correct
16	Correct	134 ms	141816 KB	Output is correct
17	Correct	145 ms	141944 KB	Output is correct
18	Correct	148 ms	141852 KB	Output is correct
19	Correct	135 ms	141816 KB	Output is correct
20	Correct	142 ms	141816 KB	Output is correct
21	Correct	148 ms	141532 KB	Output is correct
22	Correct	146 ms	141740 KB	Output is correct
23	Correct	138 ms	141816 KB	Output is correct
24	Correct	142 ms	141900 KB	Output is correct
25	Correct	144 ms	142072 KB	Output is correct
26	Correct	138 ms	141716 KB	Output is correct
27	Correct	148 ms	141532 KB	Output is correct
28	Correct	150 ms	141716 KB	Output is correct
29	Correct	134 ms	141696 KB	Output is correct
30	Correct	135 ms	141560 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	134 ms	141304 KB	Output is correct
2	Correct	134 ms	141304 KB	Output is correct
3	Correct	131 ms	141304 KB	Output is correct
4	Correct	130 ms	141304 KB	Output is correct
5	Correct	134 ms	141408 KB	Output is correct
6	Correct	142 ms	142072 KB	Output is correct
7	Correct	142 ms	141708 KB	Output is correct
8	Correct	137 ms	141944 KB	Output is correct
9	Correct	140 ms	141716 KB	Output is correct
10	Correct	158 ms	142172 KB	Output is correct
11	Correct	142 ms	141776 KB	Output is correct
12	Correct	133 ms	141820 KB	Output is correct
13	Correct	138 ms	141484 KB	Output is correct
14	Correct	131 ms	141668 KB	Output is correct
15	Correct	133 ms	141788 KB	Output is correct
16	Correct	134 ms	141816 KB	Output is correct
17	Correct	145 ms	141944 KB	Output is correct
18	Correct	148 ms	141852 KB	Output is correct
19	Correct	135 ms	141816 KB	Output is correct
20	Correct	142 ms	141816 KB	Output is correct
21	Correct	148 ms	141532 KB	Output is correct
22	Correct	146 ms	141740 KB	Output is correct
23	Correct	138 ms	141816 KB	Output is correct
24	Correct	142 ms	141900 KB	Output is correct
25	Correct	144 ms	142072 KB	Output is correct
26	Correct	138 ms	141716 KB	Output is correct
27	Correct	148 ms	141532 KB	Output is correct
28	Correct	150 ms	141716 KB	Output is correct
29	Correct	134 ms	141696 KB	Output is correct
30	Correct	135 ms	141560 KB	Output is correct
31	Correct	2856 ms	293284 KB	Output is correct
32	Correct	477 ms	159820 KB	Output is correct
33	Correct	2721 ms	321612 KB	Output is correct
34	Correct	2762 ms	291840 KB	Output is correct
35	Correct	2688 ms	301716 KB	Output is correct
36	Correct	2558 ms	315188 KB	Output is correct
37	Correct	1884 ms	297296 KB	Output is correct
38	Correct	2029 ms	305948 KB	Output is correct
39	Correct	1330 ms	269608 KB	Output is correct
40	Correct	1460 ms	279776 KB	Output is correct
41	Correct	1899 ms	243068 KB	Output is correct
42	Correct	2076 ms	241992 KB	Output is correct
43	Correct	376 ms	158664 KB	Output is correct
44	Correct	1779 ms	241120 KB	Output is correct
45	Correct	1764 ms	234076 KB	Output is correct
46	Correct	1530 ms	218500 KB	Output is correct
47	Correct	718 ms	208076 KB	Output is correct
48	Correct	707 ms	206712 KB	Output is correct
49	Correct	910 ms	220812 KB	Output is correct
50	Correct	967 ms	232536 KB	Output is correct
51	Correct	936 ms	217164 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3188 ms	566176 KB	Output is correct
2	Execution timed out	5071 ms	602600 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

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

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	134 ms	141304 KB	Output is correct
2	Correct	134 ms	141304 KB	Output is correct
3	Correct	131 ms	141304 KB	Output is correct
4	Correct	130 ms	141304 KB	Output is correct
5	Correct	134 ms	141408 KB	Output is correct
6	Correct	142 ms	142072 KB	Output is correct
7	Correct	142 ms	141708 KB	Output is correct
8	Correct	137 ms	141944 KB	Output is correct
9	Correct	140 ms	141716 KB	Output is correct
10	Correct	158 ms	142172 KB	Output is correct
11	Correct	142 ms	141776 KB	Output is correct
12	Correct	133 ms	141820 KB	Output is correct
13	Correct	138 ms	141484 KB	Output is correct
14	Correct	131 ms	141668 KB	Output is correct
15	Correct	133 ms	141788 KB	Output is correct
16	Correct	134 ms	141816 KB	Output is correct
17	Correct	145 ms	141944 KB	Output is correct
18	Correct	148 ms	141852 KB	Output is correct
19	Correct	135 ms	141816 KB	Output is correct
20	Correct	142 ms	141816 KB	Output is correct
21	Correct	148 ms	141532 KB	Output is correct
22	Correct	146 ms	141740 KB	Output is correct
23	Correct	138 ms	141816 KB	Output is correct
24	Correct	142 ms	141900 KB	Output is correct
25	Correct	144 ms	142072 KB	Output is correct
26	Correct	138 ms	141716 KB	Output is correct
27	Correct	148 ms	141532 KB	Output is correct
28	Correct	150 ms	141716 KB	Output is correct
29	Correct	134 ms	141696 KB	Output is correct
30	Correct	135 ms	141560 KB	Output is correct
31	Correct	2856 ms	293284 KB	Output is correct
32	Correct	477 ms	159820 KB	Output is correct
33	Correct	2721 ms	321612 KB	Output is correct
34	Correct	2762 ms	291840 KB	Output is correct
35	Correct	2688 ms	301716 KB	Output is correct
36	Correct	2558 ms	315188 KB	Output is correct
37	Correct	1884 ms	297296 KB	Output is correct
38	Correct	2029 ms	305948 KB	Output is correct
39	Correct	1330 ms	269608 KB	Output is correct
40	Correct	1460 ms	279776 KB	Output is correct
41	Correct	1899 ms	243068 KB	Output is correct
42	Correct	2076 ms	241992 KB	Output is correct
43	Correct	376 ms	158664 KB	Output is correct
44	Correct	1779 ms	241120 KB	Output is correct
45	Correct	1764 ms	234076 KB	Output is correct
46	Correct	1530 ms	218500 KB	Output is correct
47	Correct	718 ms	208076 KB	Output is correct
48	Correct	707 ms	206712 KB	Output is correct
49	Correct	910 ms	220812 KB	Output is correct
50	Correct	967 ms	232536 KB	Output is correct
51	Correct	936 ms	217164 KB	Output is correct
52	Correct	962 ms	212224 KB	Output is correct
53	Correct	1181 ms	217568 KB	Output is correct
54	Correct	1763 ms	249840 KB	Output is correct
55	Correct	1706 ms	238992 KB	Output is correct
56	Correct	1475 ms	232032 KB	Output is correct
57	Correct	1947 ms	242532 KB	Output is correct
58	Correct	1648 ms	238384 KB	Output is correct
59	Correct	1396 ms	236080 KB	Output is correct
60	Correct	1810 ms	241848 KB	Output is correct
61	Correct	290 ms	167780 KB	Output is correct
62	Correct	945 ms	229000 KB	Output is correct
63	Correct	1460 ms	244260 KB	Output is correct
64	Correct	1710 ms	248828 KB	Output is correct
65	Correct	1910 ms	254424 KB	Output is correct
66	Correct	2033 ms	248276 KB	Output is correct
67	Correct	587 ms	173384 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	134 ms	141304 KB	Output is correct
2	Correct	134 ms	141304 KB	Output is correct
3	Correct	131 ms	141304 KB	Output is correct
4	Correct	130 ms	141304 KB	Output is correct
5	Correct	134 ms	141408 KB	Output is correct
6	Correct	142 ms	142072 KB	Output is correct
7	Correct	142 ms	141708 KB	Output is correct
8	Correct	137 ms	141944 KB	Output is correct
9	Correct	140 ms	141716 KB	Output is correct
10	Correct	158 ms	142172 KB	Output is correct
11	Correct	142 ms	141776 KB	Output is correct
12	Correct	133 ms	141820 KB	Output is correct
13	Correct	138 ms	141484 KB	Output is correct
14	Correct	131 ms	141668 KB	Output is correct
15	Correct	133 ms	141788 KB	Output is correct
16	Correct	134 ms	141816 KB	Output is correct
17	Correct	145 ms	141944 KB	Output is correct
18	Correct	148 ms	141852 KB	Output is correct
19	Correct	135 ms	141816 KB	Output is correct
20	Correct	142 ms	141816 KB	Output is correct
21	Correct	148 ms	141532 KB	Output is correct
22	Correct	146 ms	141740 KB	Output is correct
23	Correct	138 ms	141816 KB	Output is correct
24	Correct	142 ms	141900 KB	Output is correct
25	Correct	144 ms	142072 KB	Output is correct
26	Correct	138 ms	141716 KB	Output is correct
27	Correct	148 ms	141532 KB	Output is correct
28	Correct	150 ms	141716 KB	Output is correct
29	Correct	134 ms	141696 KB	Output is correct
30	Correct	135 ms	141560 KB	Output is correct
31	Correct	2856 ms	293284 KB	Output is correct
32	Correct	477 ms	159820 KB	Output is correct
33	Correct	2721 ms	321612 KB	Output is correct
34	Correct	2762 ms	291840 KB	Output is correct
35	Correct	2688 ms	301716 KB	Output is correct
36	Correct	2558 ms	315188 KB	Output is correct
37	Correct	1884 ms	297296 KB	Output is correct
38	Correct	2029 ms	305948 KB	Output is correct
39	Correct	1330 ms	269608 KB	Output is correct
40	Correct	1460 ms	279776 KB	Output is correct
41	Correct	1899 ms	243068 KB	Output is correct
42	Correct	2076 ms	241992 KB	Output is correct
43	Correct	376 ms	158664 KB	Output is correct
44	Correct	1779 ms	241120 KB	Output is correct
45	Correct	1764 ms	234076 KB	Output is correct
46	Correct	1530 ms	218500 KB	Output is correct
47	Correct	718 ms	208076 KB	Output is correct
48	Correct	707 ms	206712 KB	Output is correct
49	Correct	910 ms	220812 KB	Output is correct
50	Correct	967 ms	232536 KB	Output is correct
51	Correct	936 ms	217164 KB	Output is correct
52	Correct	3188 ms	566176 KB	Output is correct
53	Execution timed out	5071 ms	602600 KB	Time limit exceeded
54	Halted	0 ms	0 KB	-

답안 #99862

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