oj.uz

Submission #99861

# Submission time Handle Problem Language Result Execution time Memory
99861 2019-03-07T22:51:54 Z TadijaSebez New Home (APIO18_new_home) C++11
47 / 100
 5000 ms 616592 KB 
#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: 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:53:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<LST[c].size();i++)
              ~^~~~~~~~~~~~~~
new_home.cpp:63:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<RST[c].size();i++)
              ~^~~~~~~~~~~~~~
new_home.cpp:74: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:86:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:93: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:97: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:103: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

# Verdict Execution time Memory Grader output
1 Correct 128 ms 141304 KB Output is correct
2 Correct 127 ms 141360 KB Output is correct
3 Correct 128 ms 141304 KB Output is correct
4 Correct 134 ms 141356 KB Output is correct
5 Correct 148 ms 141532 KB Output is correct
6 Correct 136 ms 142000 KB Output is correct
7 Correct 129 ms 141688 KB Output is correct
8 Correct 129 ms 141816 KB Output is correct
9 Correct 138 ms 141676 KB Output is correct
10 Correct 135 ms 142072 KB Output is correct
11 Correct 133 ms 141756 KB Output is correct
12 Correct 137 ms 141944 KB Output is correct
13 Correct 140 ms 141560 KB Output is correct
14 Correct 141 ms 141688 KB Output is correct
15 Correct 139 ms 141936 KB Output is correct
16 Correct 160 ms 141772 KB Output is correct
17 Correct 145 ms 141944 KB Output is correct
18 Correct 137 ms 141816 KB Output is correct
19 Correct 131 ms 141816 KB Output is correct
20 Correct 136 ms 141796 KB Output is correct
21 Correct 138 ms 141512 KB Output is correct
22 Correct 136 ms 141688 KB Output is correct
23 Correct 150 ms 141932 KB Output is correct
24 Correct 131 ms 141816 KB Output is correct
25 Correct 161 ms 141916 KB Output is correct
26 Correct 137 ms 141916 KB Output is correct
27 Correct 126 ms 141612 KB Output is correct
28 Correct 127 ms 141792 KB Output is correct
29 Correct 131 ms 141816 KB Output is correct
30 Correct 131 ms 141632 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 141304 KB Output is correct
2 Correct 127 ms 141360 KB Output is correct
3 Correct 128 ms 141304 KB Output is correct
4 Correct 134 ms 141356 KB Output is correct
5 Correct 148 ms 141532 KB Output is correct
6 Correct 136 ms 142000 KB Output is correct
7 Correct 129 ms 141688 KB Output is correct
8 Correct 129 ms 141816 KB Output is correct
9 Correct 138 ms 141676 KB Output is correct
10 Correct 135 ms 142072 KB Output is correct
11 Correct 133 ms 141756 KB Output is correct
12 Correct 137 ms 141944 KB Output is correct
13 Correct 140 ms 141560 KB Output is correct
14 Correct 141 ms 141688 KB Output is correct
15 Correct 139 ms 141936 KB Output is correct
16 Correct 160 ms 141772 KB Output is correct
17 Correct 145 ms 141944 KB Output is correct
18 Correct 137 ms 141816 KB Output is correct
19 Correct 131 ms 141816 KB Output is correct
20 Correct 136 ms 141796 KB Output is correct
21 Correct 138 ms 141512 KB Output is correct
22 Correct 136 ms 141688 KB Output is correct
23 Correct 150 ms 141932 KB Output is correct
24 Correct 131 ms 141816 KB Output is correct
25 Correct 161 ms 141916 KB Output is correct
26 Correct 137 ms 141916 KB Output is correct
27 Correct 126 ms 141612 KB Output is correct
28 Correct 127 ms 141792 KB Output is correct
29 Correct 131 ms 141816 KB Output is correct
30 Correct 131 ms 141632 KB Output is correct
31 Correct 2828 ms 295804 KB Output is correct
32 Correct 397 ms 160464 KB Output is correct
33 Correct 2890 ms 324140 KB Output is correct
34 Correct 2979 ms 294600 KB Output is correct
35 Correct 2652 ms 304144 KB Output is correct
36 Correct 2765 ms 317652 KB Output is correct
37 Correct 2073 ms 299672 KB Output is correct
38 Correct 1956 ms 308492 KB Output is correct
39 Correct 1228 ms 272240 KB Output is correct
40 Correct 1280 ms 282364 KB Output is correct
41 Correct 2190 ms 245636 KB Output is correct
42 Correct 2050 ms 244648 KB Output is correct
43 Correct 231 ms 160612 KB Output is correct
44 Correct 1949 ms 243808 KB Output is correct
45 Correct 1692 ms 236568 KB Output is correct
46 Correct 1398 ms 220892 KB Output is correct
47 Correct 635 ms 210400 KB Output is correct
48 Correct 644 ms 209032 KB Output is correct
49 Correct 876 ms 223112 KB Output is correct
50 Correct 967 ms 235308 KB Output is correct
51 Correct 922 ms 219616 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3169 ms 565632 KB Output is correct
2 Execution timed out 5076 ms 616592 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5074 ms 439988 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 141304 KB Output is correct
2 Correct 127 ms 141360 KB Output is correct
3 Correct 128 ms 141304 KB Output is correct
4 Correct 134 ms 141356 KB Output is correct
5 Correct 148 ms 141532 KB Output is correct
6 Correct 136 ms 142000 KB Output is correct
7 Correct 129 ms 141688 KB Output is correct
8 Correct 129 ms 141816 KB Output is correct
9 Correct 138 ms 141676 KB Output is correct
10 Correct 135 ms 142072 KB Output is correct
11 Correct 133 ms 141756 KB Output is correct
12 Correct 137 ms 141944 KB Output is correct
13 Correct 140 ms 141560 KB Output is correct
14 Correct 141 ms 141688 KB Output is correct
15 Correct 139 ms 141936 KB Output is correct
16 Correct 160 ms 141772 KB Output is correct
17 Correct 145 ms 141944 KB Output is correct
18 Correct 137 ms 141816 KB Output is correct
19 Correct 131 ms 141816 KB Output is correct
20 Correct 136 ms 141796 KB Output is correct
21 Correct 138 ms 141512 KB Output is correct
22 Correct 136 ms 141688 KB Output is correct
23 Correct 150 ms 141932 KB Output is correct
24 Correct 131 ms 141816 KB Output is correct
25 Correct 161 ms 141916 KB Output is correct
26 Correct 137 ms 141916 KB Output is correct
27 Correct 126 ms 141612 KB Output is correct
28 Correct 127 ms 141792 KB Output is correct
29 Correct 131 ms 141816 KB Output is correct
30 Correct 131 ms 141632 KB Output is correct
31 Correct 2828 ms 295804 KB Output is correct
32 Correct 397 ms 160464 KB Output is correct
33 Correct 2890 ms 324140 KB Output is correct
34 Correct 2979 ms 294600 KB Output is correct
35 Correct 2652 ms 304144 KB Output is correct
36 Correct 2765 ms 317652 KB Output is correct
37 Correct 2073 ms 299672 KB Output is correct
38 Correct 1956 ms 308492 KB Output is correct
39 Correct 1228 ms 272240 KB Output is correct
40 Correct 1280 ms 282364 KB Output is correct
41 Correct 2190 ms 245636 KB Output is correct
42 Correct 2050 ms 244648 KB Output is correct
43 Correct 231 ms 160612 KB Output is correct
44 Correct 1949 ms 243808 KB Output is correct
45 Correct 1692 ms 236568 KB Output is correct
46 Correct 1398 ms 220892 KB Output is correct
47 Correct 635 ms 210400 KB Output is correct
48 Correct 644 ms 209032 KB Output is correct
49 Correct 876 ms 223112 KB Output is correct
50 Correct 967 ms 235308 KB Output is correct
51 Correct 922 ms 219616 KB Output is correct
52 Correct 895 ms 215160 KB Output is correct
53 Correct 1014 ms 220436 KB Output is correct
54 Correct 1710 ms 252900 KB Output is correct
55 Correct 1639 ms 241636 KB Output is correct
56 Correct 1543 ms 234852 KB Output is correct
57 Correct 1973 ms 245340 KB Output is correct
58 Correct 1821 ms 241376 KB Output is correct
59 Correct 1537 ms 238944 KB Output is correct
60 Correct 1899 ms 244660 KB Output is correct
61 Correct 241 ms 169824 KB Output is correct
62 Correct 984 ms 231908 KB Output is correct
63 Correct 1478 ms 247208 KB Output is correct
64 Correct 1764 ms 251720 KB Output is correct
65 Correct 1963 ms 257292 KB Output is correct
66 Correct 2108 ms 250808 KB Output is correct
67 Correct 482 ms 174432 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 141304 KB Output is correct
2 Correct 127 ms 141360 KB Output is correct
3 Correct 128 ms 141304 KB Output is correct
4 Correct 134 ms 141356 KB Output is correct
5 Correct 148 ms 141532 KB Output is correct
6 Correct 136 ms 142000 KB Output is correct
7 Correct 129 ms 141688 KB Output is correct
8 Correct 129 ms 141816 KB Output is correct
9 Correct 138 ms 141676 KB Output is correct
10 Correct 135 ms 142072 KB Output is correct
11 Correct 133 ms 141756 KB Output is correct
12 Correct 137 ms 141944 KB Output is correct
13 Correct 140 ms 141560 KB Output is correct
14 Correct 141 ms 141688 KB Output is correct
15 Correct 139 ms 141936 KB Output is correct
16 Correct 160 ms 141772 KB Output is correct
17 Correct 145 ms 141944 KB Output is correct
18 Correct 137 ms 141816 KB Output is correct
19 Correct 131 ms 141816 KB Output is correct
20 Correct 136 ms 141796 KB Output is correct
21 Correct 138 ms 141512 KB Output is correct
22 Correct 136 ms 141688 KB Output is correct
23 Correct 150 ms 141932 KB Output is correct
24 Correct 131 ms 141816 KB Output is correct
25 Correct 161 ms 141916 KB Output is correct
26 Correct 137 ms 141916 KB Output is correct
27 Correct 126 ms 141612 KB Output is correct
28 Correct 127 ms 141792 KB Output is correct
29 Correct 131 ms 141816 KB Output is correct
30 Correct 131 ms 141632 KB Output is correct
31 Correct 2828 ms 295804 KB Output is correct
32 Correct 397 ms 160464 KB Output is correct
33 Correct 2890 ms 324140 KB Output is correct
34 Correct 2979 ms 294600 KB Output is correct
35 Correct 2652 ms 304144 KB Output is correct
36 Correct 2765 ms 317652 KB Output is correct
37 Correct 2073 ms 299672 KB Output is correct
38 Correct 1956 ms 308492 KB Output is correct
39 Correct 1228 ms 272240 KB Output is correct
40 Correct 1280 ms 282364 KB Output is correct
41 Correct 2190 ms 245636 KB Output is correct
42 Correct 2050 ms 244648 KB Output is correct
43 Correct 231 ms 160612 KB Output is correct
44 Correct 1949 ms 243808 KB Output is correct
45 Correct 1692 ms 236568 KB Output is correct
46 Correct 1398 ms 220892 KB Output is correct
47 Correct 635 ms 210400 KB Output is correct
48 Correct 644 ms 209032 KB Output is correct
49 Correct 876 ms 223112 KB Output is correct
50 Correct 967 ms 235308 KB Output is correct
51 Correct 922 ms 219616 KB Output is correct
52 Correct 3169 ms 565632 KB Output is correct
53 Execution timed out 5076 ms 616592 KB Time limit exceeded
54 Halted 0 ms 0 KB -