답안 #99866 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99866	2019-03-07T23:19:34 Z	TadijaSebez	새 집 (APIO18_new_home)	C++11	47 / 100	4056 ms	1049600 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,RST;
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, vector<tuple<int,int,int,int>> L, vector<tuple<int,int,int,int>> R)
{
	c=++tsz;int mid=ss+se>>1;
	vector<tuple<int,int,int,int>> PLL,PRL,PLR,PRR;
	LST.clear();RST.clear();
	for(int i=0;i<L.size();i++)
	{
		if(get<0>(L[i])<=ss && get<1>(L[i])>=se) LST.pb(mp(get<2>(L[i]),get<3>(L[i])));
		else
		{
			if(get<0>(L[i])<=mid) PLL.pb(L[i]);
			if(get<1>(L[i])>mid) PRL.pb(L[i]);
		}
	}
	for(int i=0;i<R.size();i++)
	{
		if(get<0>(R[i])<=ss && get<1>(R[i])>=se) RST.pb(mp(get<2>(R[i]),get<3>(R[i])));
		else
		{
			if(get<0>(R[i])<=mid) PLR.pb(R[i]);
			if(get<1>(R[i])>mid) PRR.pb(R[i]);
		}
	}
	STL[c].reserve(LST.size());
	int mx=-lim;
	for(int i=0;i<LST.size();i++)
	{
		if(LST[i].second>=mx)
		{
			STL[c].pb(mt(max(LST[i].first,mx),LST[i].second,LST[i].first));
			mx=LST[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.size());
	int mn=lim*2;
	for(int i=0;i<RST.size();i++)
	{
		if(RST[i].first<=mn)
		{
			STR[c].pb(mt(RST[i].first,min(RST[i].second,mn),RST[i].second));
			mn=RST[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());
	LST.clear();RST.clear();R.clear();L.clear();
	if(ss==se) return;
	Build(ls[c],ss,mid,PLL,PLR);
	PLL.clear();PLR.clear();
	Build(rs[c],mid+1,se,PRL,PRR);
	PRL.clear();PRR.clear();
}
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) tp=mt(Get(get<0>(tp)),Get(get<1>(tp)),get<2>(tp),get<3>(tp));
	for(auto &tp:R) tp=mt(Get(get<0>(tp)),Get(get<1>(tp)),get<2>(tp),get<3>(tp));
	//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(),L,R);
	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 Build(int&, int, int, std::vector<std::tuple<int, int, int, int> >, std::vector<std::tuple<int, int, int, int> >)':
new_home.cpp:51:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  c=++tsz;int mid=ss+se>>1;
                  ~~^~~
new_home.cpp:54:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<L.size();i++)
              ~^~~~~~~~~
new_home.cpp:63:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<R.size();i++)
              ~^~~~~~~~~
new_home.cpp:74:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<LST.size();i++)
              ~^~~~~~~~~~~
new_home.cpp:85:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<RST.size();i++)
              ~^~~~~~~~~~~
new_home.cpp: In function 'int Solve(int, int, int, int, int)':
new_home.cpp:110:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:117: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:121: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:127: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	79 ms	84984 KB	Output is correct
2	Correct	82 ms	84984 KB	Output is correct
3	Correct	81 ms	84984 KB	Output is correct
4	Correct	77 ms	84984 KB	Output is correct
5	Correct	80 ms	85252 KB	Output is correct
6	Correct	90 ms	85644 KB	Output is correct
7	Correct	86 ms	85240 KB	Output is correct
8	Correct	81 ms	85528 KB	Output is correct
9	Correct	79 ms	85368 KB	Output is correct
10	Correct	87 ms	85752 KB	Output is correct
11	Correct	81 ms	85364 KB	Output is correct
12	Correct	82 ms	85468 KB	Output is correct
13	Correct	80 ms	85112 KB	Output is correct
14	Correct	80 ms	85240 KB	Output is correct
15	Correct	81 ms	85368 KB	Output is correct
16	Correct	83 ms	85476 KB	Output is correct
17	Correct	85 ms	85496 KB	Output is correct
18	Correct	99 ms	85512 KB	Output is correct
19	Correct	94 ms	85564 KB	Output is correct
20	Correct	102 ms	85496 KB	Output is correct
21	Correct	96 ms	85112 KB	Output is correct
22	Correct	80 ms	85332 KB	Output is correct
23	Correct	91 ms	85496 KB	Output is correct
24	Correct	82 ms	85512 KB	Output is correct
25	Correct	82 ms	85624 KB	Output is correct
26	Correct	84 ms	85496 KB	Output is correct
27	Correct	81 ms	85368 KB	Output is correct
28	Correct	87 ms	85400 KB	Output is correct
29	Correct	78 ms	85372 KB	Output is correct
30	Correct	78 ms	85212 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	79 ms	84984 KB	Output is correct
2	Correct	82 ms	84984 KB	Output is correct
3	Correct	81 ms	84984 KB	Output is correct
4	Correct	77 ms	84984 KB	Output is correct
5	Correct	80 ms	85252 KB	Output is correct
6	Correct	90 ms	85644 KB	Output is correct
7	Correct	86 ms	85240 KB	Output is correct
8	Correct	81 ms	85528 KB	Output is correct
9	Correct	79 ms	85368 KB	Output is correct
10	Correct	87 ms	85752 KB	Output is correct
11	Correct	81 ms	85364 KB	Output is correct
12	Correct	82 ms	85468 KB	Output is correct
13	Correct	80 ms	85112 KB	Output is correct
14	Correct	80 ms	85240 KB	Output is correct
15	Correct	81 ms	85368 KB	Output is correct
16	Correct	83 ms	85476 KB	Output is correct
17	Correct	85 ms	85496 KB	Output is correct
18	Correct	99 ms	85512 KB	Output is correct
19	Correct	94 ms	85564 KB	Output is correct
20	Correct	102 ms	85496 KB	Output is correct
21	Correct	96 ms	85112 KB	Output is correct
22	Correct	80 ms	85332 KB	Output is correct
23	Correct	91 ms	85496 KB	Output is correct
24	Correct	82 ms	85512 KB	Output is correct
25	Correct	82 ms	85624 KB	Output is correct
26	Correct	84 ms	85496 KB	Output is correct
27	Correct	81 ms	85368 KB	Output is correct
28	Correct	87 ms	85400 KB	Output is correct
29	Correct	78 ms	85372 KB	Output is correct
30	Correct	78 ms	85212 KB	Output is correct
31	Correct	1655 ms	230452 KB	Output is correct
32	Correct	347 ms	123468 KB	Output is correct
33	Correct	1874 ms	225612 KB	Output is correct
34	Correct	1718 ms	220496 KB	Output is correct
35	Correct	1743 ms	231908 KB	Output is correct
36	Correct	1833 ms	232552 KB	Output is correct
37	Correct	1396 ms	208972 KB	Output is correct
38	Correct	1450 ms	209704 KB	Output is correct
39	Correct	1129 ms	191696 KB	Output is correct
40	Correct	1354 ms	195880 KB	Output is correct
41	Correct	1327 ms	177632 KB	Output is correct
42	Correct	1162 ms	176032 KB	Output is correct
43	Correct	196 ms	117060 KB	Output is correct
44	Correct	1367 ms	176868 KB	Output is correct
45	Correct	1251 ms	169600 KB	Output is correct
46	Correct	1058 ms	159252 KB	Output is correct
47	Correct	681 ms	149388 KB	Output is correct
48	Correct	731 ms	149348 KB	Output is correct
49	Correct	919 ms	159156 KB	Output is correct
50	Correct	931 ms	166704 KB	Output is correct
51	Correct	983 ms	157276 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	3030 ms	1049600 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	4056 ms	1049600 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	79 ms	84984 KB	Output is correct
2	Correct	82 ms	84984 KB	Output is correct
3	Correct	81 ms	84984 KB	Output is correct
4	Correct	77 ms	84984 KB	Output is correct
5	Correct	80 ms	85252 KB	Output is correct
6	Correct	90 ms	85644 KB	Output is correct
7	Correct	86 ms	85240 KB	Output is correct
8	Correct	81 ms	85528 KB	Output is correct
9	Correct	79 ms	85368 KB	Output is correct
10	Correct	87 ms	85752 KB	Output is correct
11	Correct	81 ms	85364 KB	Output is correct
12	Correct	82 ms	85468 KB	Output is correct
13	Correct	80 ms	85112 KB	Output is correct
14	Correct	80 ms	85240 KB	Output is correct
15	Correct	81 ms	85368 KB	Output is correct
16	Correct	83 ms	85476 KB	Output is correct
17	Correct	85 ms	85496 KB	Output is correct
18	Correct	99 ms	85512 KB	Output is correct
19	Correct	94 ms	85564 KB	Output is correct
20	Correct	102 ms	85496 KB	Output is correct
21	Correct	96 ms	85112 KB	Output is correct
22	Correct	80 ms	85332 KB	Output is correct
23	Correct	91 ms	85496 KB	Output is correct
24	Correct	82 ms	85512 KB	Output is correct
25	Correct	82 ms	85624 KB	Output is correct
26	Correct	84 ms	85496 KB	Output is correct
27	Correct	81 ms	85368 KB	Output is correct
28	Correct	87 ms	85400 KB	Output is correct
29	Correct	78 ms	85372 KB	Output is correct
30	Correct	78 ms	85212 KB	Output is correct
31	Correct	1655 ms	230452 KB	Output is correct
32	Correct	347 ms	123468 KB	Output is correct
33	Correct	1874 ms	225612 KB	Output is correct
34	Correct	1718 ms	220496 KB	Output is correct
35	Correct	1743 ms	231908 KB	Output is correct
36	Correct	1833 ms	232552 KB	Output is correct
37	Correct	1396 ms	208972 KB	Output is correct
38	Correct	1450 ms	209704 KB	Output is correct
39	Correct	1129 ms	191696 KB	Output is correct
40	Correct	1354 ms	195880 KB	Output is correct
41	Correct	1327 ms	177632 KB	Output is correct
42	Correct	1162 ms	176032 KB	Output is correct
43	Correct	196 ms	117060 KB	Output is correct
44	Correct	1367 ms	176868 KB	Output is correct
45	Correct	1251 ms	169600 KB	Output is correct
46	Correct	1058 ms	159252 KB	Output is correct
47	Correct	681 ms	149388 KB	Output is correct
48	Correct	731 ms	149348 KB	Output is correct
49	Correct	919 ms	159156 KB	Output is correct
50	Correct	931 ms	166704 KB	Output is correct
51	Correct	983 ms	157276 KB	Output is correct
52	Correct	644 ms	150012 KB	Output is correct
53	Correct	648 ms	146020 KB	Output is correct
54	Correct	1002 ms	187672 KB	Output is correct
55	Correct	990 ms	173024 KB	Output is correct
56	Correct	1008 ms	169048 KB	Output is correct
57	Correct	1157 ms	174512 KB	Output is correct
58	Correct	1035 ms	169724 KB	Output is correct
59	Correct	975 ms	166884 KB	Output is correct
60	Correct	1189 ms	174392 KB	Output is correct
61	Correct	176 ms	112304 KB	Output is correct
62	Correct	610 ms	155012 KB	Output is correct
63	Correct	874 ms	176844 KB	Output is correct
64	Correct	1004 ms	182392 KB	Output is correct
65	Correct	1327 ms	188916 KB	Output is correct
66	Correct	1386 ms	180360 KB	Output is correct
67	Correct	476 ms	138660 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	79 ms	84984 KB	Output is correct
2	Correct	82 ms	84984 KB	Output is correct
3	Correct	81 ms	84984 KB	Output is correct
4	Correct	77 ms	84984 KB	Output is correct
5	Correct	80 ms	85252 KB	Output is correct
6	Correct	90 ms	85644 KB	Output is correct
7	Correct	86 ms	85240 KB	Output is correct
8	Correct	81 ms	85528 KB	Output is correct
9	Correct	79 ms	85368 KB	Output is correct
10	Correct	87 ms	85752 KB	Output is correct
11	Correct	81 ms	85364 KB	Output is correct
12	Correct	82 ms	85468 KB	Output is correct
13	Correct	80 ms	85112 KB	Output is correct
14	Correct	80 ms	85240 KB	Output is correct
15	Correct	81 ms	85368 KB	Output is correct
16	Correct	83 ms	85476 KB	Output is correct
17	Correct	85 ms	85496 KB	Output is correct
18	Correct	99 ms	85512 KB	Output is correct
19	Correct	94 ms	85564 KB	Output is correct
20	Correct	102 ms	85496 KB	Output is correct
21	Correct	96 ms	85112 KB	Output is correct
22	Correct	80 ms	85332 KB	Output is correct
23	Correct	91 ms	85496 KB	Output is correct
24	Correct	82 ms	85512 KB	Output is correct
25	Correct	82 ms	85624 KB	Output is correct
26	Correct	84 ms	85496 KB	Output is correct
27	Correct	81 ms	85368 KB	Output is correct
28	Correct	87 ms	85400 KB	Output is correct
29	Correct	78 ms	85372 KB	Output is correct
30	Correct	78 ms	85212 KB	Output is correct
31	Correct	1655 ms	230452 KB	Output is correct
32	Correct	347 ms	123468 KB	Output is correct
33	Correct	1874 ms	225612 KB	Output is correct
34	Correct	1718 ms	220496 KB	Output is correct
35	Correct	1743 ms	231908 KB	Output is correct
36	Correct	1833 ms	232552 KB	Output is correct
37	Correct	1396 ms	208972 KB	Output is correct
38	Correct	1450 ms	209704 KB	Output is correct
39	Correct	1129 ms	191696 KB	Output is correct
40	Correct	1354 ms	195880 KB	Output is correct
41	Correct	1327 ms	177632 KB	Output is correct
42	Correct	1162 ms	176032 KB	Output is correct
43	Correct	196 ms	117060 KB	Output is correct
44	Correct	1367 ms	176868 KB	Output is correct
45	Correct	1251 ms	169600 KB	Output is correct
46	Correct	1058 ms	159252 KB	Output is correct
47	Correct	681 ms	149388 KB	Output is correct
48	Correct	731 ms	149348 KB	Output is correct
49	Correct	919 ms	159156 KB	Output is correct
50	Correct	931 ms	166704 KB	Output is correct
51	Correct	983 ms	157276 KB	Output is correct
52	Runtime error	3030 ms	1049600 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
53	Halted	0 ms	0 KB	-

답안 #99866

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