oj.uz

Submission #497303

# Submission time Handle Problem Language Result Execution time Memory
497303 2021-12-23T02:03:45 Z jamezzz New Home (APIO18_new_home) C++17
100 / 100
 2690 ms 581232 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));

inline int rd(){
    int x=0;
    char ch=getchar_unlocked();
    while(ch<'0'||ch>'9')ch=getchar_unlocked();
    while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar_unlocked();
	}
    return x;
}

struct upd{
	int s,e,p,x;
};

struct qry{
	int l,y,i;
};

#define maxn 300005

int n,k,m,q,x[maxn],t[maxn],a[maxn],b[maxn],l[maxn],y[maxn],ltime[maxn],rtime[maxn],ans[maxn];
bool impos[2*maxn];
vi add[2*maxn],rem[2*maxn];
set<ii> s[2*maxn];
vector<upd> pupd,nupd;

void add_upd(ii ss,ii ee,int t){
	//pf("add_upd: %d %d %d %d %d\n",ss.fi,ss.se,ee.fi,ee.se,t);
	if(ss.se!=0&&rtime[ss.se]<t){
		pupd.pb({rtime[ss.se],t-1,(ss.fi+ee.fi)/2,x[ss.se]});
		rtime[ss.se]=t;
	}
	if(ee.se!=0&&ltime[ee.se]<t){
		nupd.pb({ltime[ee.se],t-1,(ss.fi+ee.fi+1)/2,x[ee.se]});
		ltime[ee.se]=t;
	}
}

void dnc(int s,int e,vector<qry> &qrys,vector<upd> &pupd,vector<upd> &nupd){
	if(s>e||qrys.empty()||(pupd.empty()&&nupd.empty()))return;
	
	int m=(s+e)/2;
	vector<qry> lqrys,rqrys;
	vector<upd> lpupd,lnupd,rpupd,rnupd;
	
	#ifdef DEBUG
	pf("dnc: %d %d\n",s,e);
	for(qry &q:qrys)pf("(%d %d %d) ",q.l,q.y,q.i);pf("\n");
	pf("pupd: ");for(upd &u:pupd)pf("(%d %d %d %d) ",u.s,u.e,u.p,u.x);pf("\n");
	pf("nupd: ");for(upd &u:nupd)pf("(%d %d %d %d) ",u.s,u.e,u.p,u.x);pf("\n");
	pf("\n");
	#endif //DEBUG
	
	int ptr=0,cur=0;
	for(qry &q:qrys){
		while(ptr!=sz(nupd)&&nupd[ptr].p<=q.l){
			if(nupd[ptr].s<=s&&e<=nupd[ptr].e)cur=max(cur,nupd[ptr].x);
			else{
				if(nupd[ptr].s<=m)lnupd.pb(nupd[ptr]);
				if(m+1<=nupd[ptr].e)rnupd.pb(nupd[ptr]);
			}
			++ptr;
		}
		mxto(ans[q.i],cur-q.l);
		if(q.y<=m)lqrys.pb(q);
		else rqrys.pb(q);
	}
	ptr=0,cur=2e8;
	reverse(all(qrys));
	for(qry &q:qrys){
		while(ptr!=sz(pupd)&&pupd[ptr].p>=q.l){
			if(pupd[ptr].s<=s&&e<=pupd[ptr].e)cur=min(cur,pupd[ptr].x);
			else{
				if(pupd[ptr].s<=m)lpupd.pb(pupd[ptr]);
				if(m+1<=pupd[ptr].e)rpupd.pb(pupd[ptr]);
			}
			++ptr;
		}
		mxto(ans[q.i],q.l-cur);
	}
	
	dnc(s,m,lqrys,lpupd,lnupd);
	dnc(m+1,e,rqrys,rpupd,rnupd);
}

int main(){
	//read input and discretise
	n=rd();k=rd();q=rd();
	vector<int> d;
	for(int i=1;i<=n;++i){
		x[i]=rd();t[i]=rd();a[i]=rd();b[i]=rd();
		d.pb(a[i]);d.pb(b[i]+1);
	}
	d.pb(0);
	disc(d);m=sz(d);
	for(int i=1;i<=n;++i){
		a[i]=upper_bound(all(d),a[i])-d.begin()-1;
		b[i]=upper_bound(all(d),b[i])-d.begin()-1;
		add[a[i]].pb(i);
		rem[b[i]+1].pb(i);
	}
	vector<qry> qrys;
	for(int i=0;i<q;++i){
		l[i]=rd();y[i]=rd();
		y[i]=upper_bound(all(d),y[i])-d.begin()-1;
		qrys.pb({l[i],y[i],i});
	}
	sort(all(qrys),[](qry &a,qry &b){return a.l<b.l;});
	
	int zero=k;
	//preprocess lines
	for(int i=0;i<m;++i){
		for(int j:rem[i]){
			//pf("rem %d\n",j);
			ii ss={-2e8,0},ee={2e8,0},mm={x[j],j};
			auto it=s[t[j]].upper_bound({x[j],j});
			if(it!=s[t[j]].end())ee=*it;
			it=s[t[j]].lower_bound({x[j],j});
			if(it!=s[t[j]].begin())ss=*--it;
			add_upd(ss,mm,i);add_upd(mm,ee,i);
			s[t[j]].erase(s[t[j]].find({x[j],j}));
			if(s[t[j]].empty())++zero;
		}
		for(int j:add[i]){
			//pf("add %d\n",j);
			ii ss={-2e8,0},ee={2e8,0};
			auto it=s[t[j]].upper_bound({x[j],j});
			if(it!=s[t[j]].end())ee=*it;
			if(it!=s[t[j]].begin())ss=*--it;
			add_upd(ss,ee,i);
			rtime[j]=ltime[j]=i;
			if(s[t[j]].empty())--zero;
			s[t[j]].insert({x[j],j});
		}
		if(zero>0)impos[i]=true;
	}
	
	sort(all(pupd),[](upd &a,upd &b){return a.p>b.p;});
	sort(all(nupd),[](upd &a,upd &b){return a.p<b.p;});
	
	dnc(0,m-1,qrys,pupd,nupd);
	
	for(int i=0;i<q;++i){
		if(impos[y[i]])pf("-1\n");
		else pf("%d\n",ans[i]);
	}
}

/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10

3 1 3
1 1 1 5
3 1 2 3
3 1 3 4
1 1
3 3
2 5
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 56656 KB Output is correct
2 Correct 33 ms 56652 KB Output is correct
3 Correct 34 ms 56652 KB Output is correct
4 Correct 29 ms 56652 KB Output is correct
5 Correct 30 ms 56948 KB Output is correct
6 Correct 32 ms 56872 KB Output is correct
7 Correct 30 ms 56808 KB Output is correct
8 Correct 30 ms 56904 KB Output is correct
9 Correct 30 ms 56800 KB Output is correct
10 Correct 31 ms 56916 KB Output is correct
11 Correct 36 ms 56840 KB Output is correct
12 Correct 29 ms 56936 KB Output is correct
13 Correct 29 ms 56880 KB Output is correct
14 Correct 31 ms 56836 KB Output is correct
15 Correct 29 ms 56840 KB Output is correct
16 Correct 29 ms 56904 KB Output is correct
17 Correct 29 ms 56856 KB Output is correct
18 Correct 30 ms 56832 KB Output is correct
19 Correct 30 ms 56884 KB Output is correct
20 Correct 31 ms 56816 KB Output is correct
21 Correct 28 ms 56744 KB Output is correct
22 Correct 30 ms 56792 KB Output is correct
23 Correct 30 ms 56836 KB Output is correct
24 Correct 30 ms 56840 KB Output is correct
25 Correct 30 ms 56912 KB Output is correct
26 Correct 33 ms 56920 KB Output is correct
27 Correct 31 ms 56784 KB Output is correct
28 Correct 30 ms 56868 KB Output is correct
29 Correct 32 ms 56824 KB Output is correct
30 Correct 37 ms 56712 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 56656 KB Output is correct
2 Correct 33 ms 56652 KB Output is correct
3 Correct 34 ms 56652 KB Output is correct
4 Correct 29 ms 56652 KB Output is correct
5 Correct 30 ms 56948 KB Output is correct
6 Correct 32 ms 56872 KB Output is correct
7 Correct 30 ms 56808 KB Output is correct
8 Correct 30 ms 56904 KB Output is correct
9 Correct 30 ms 56800 KB Output is correct
10 Correct 31 ms 56916 KB Output is correct
11 Correct 36 ms 56840 KB Output is correct
12 Correct 29 ms 56936 KB Output is correct
13 Correct 29 ms 56880 KB Output is correct
14 Correct 31 ms 56836 KB Output is correct
15 Correct 29 ms 56840 KB Output is correct
16 Correct 29 ms 56904 KB Output is correct
17 Correct 29 ms 56856 KB Output is correct
18 Correct 30 ms 56832 KB Output is correct
19 Correct 30 ms 56884 KB Output is correct
20 Correct 31 ms 56816 KB Output is correct
21 Correct 28 ms 56744 KB Output is correct
22 Correct 30 ms 56792 KB Output is correct
23 Correct 30 ms 56836 KB Output is correct
24 Correct 30 ms 56840 KB Output is correct
25 Correct 30 ms 56912 KB Output is correct
26 Correct 33 ms 56920 KB Output is correct
27 Correct 31 ms 56784 KB Output is correct
28 Correct 30 ms 56868 KB Output is correct
29 Correct 32 ms 56824 KB Output is correct
30 Correct 37 ms 56712 KB Output is correct
31 Correct 441 ms 95684 KB Output is correct
32 Correct 117 ms 78436 KB Output is correct
33 Correct 423 ms 94704 KB Output is correct
34 Correct 426 ms 92344 KB Output is correct
35 Correct 464 ms 95256 KB Output is correct
36 Correct 438 ms 94896 KB Output is correct
37 Correct 387 ms 88668 KB Output is correct
38 Correct 370 ms 88724 KB Output is correct
39 Correct 329 ms 86044 KB Output is correct
40 Correct 339 ms 86624 KB Output is correct
41 Correct 314 ms 81776 KB Output is correct
42 Correct 324 ms 82604 KB Output is correct
43 Correct 64 ms 70396 KB Output is correct
44 Correct 309 ms 82052 KB Output is correct
45 Correct 316 ms 82408 KB Output is correct
46 Correct 248 ms 81296 KB Output is correct
47 Correct 234 ms 79108 KB Output is correct
48 Correct 227 ms 79380 KB Output is correct
49 Correct 278 ms 80336 KB Output is correct
50 Correct 278 ms 80844 KB Output is correct
51 Correct 243 ms 80336 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 146304 KB Output is correct
2 Correct 615 ms 143748 KB Output is correct
3 Correct 308 ms 142484 KB Output is correct
4 Correct 418 ms 146328 KB Output is correct
5 Correct 683 ms 143696 KB Output is correct
6 Correct 609 ms 143644 KB Output is correct
7 Correct 257 ms 142444 KB Output is correct
8 Correct 292 ms 143724 KB Output is correct
9 Correct 333 ms 143716 KB Output is correct
10 Correct 392 ms 141428 KB Output is correct
11 Correct 350 ms 141084 KB Output is correct
12 Correct 338 ms 142020 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2061 ms 478328 KB Output is correct
2 Correct 557 ms 182844 KB Output is correct
3 Correct 2045 ms 471432 KB Output is correct
4 Correct 1285 ms 547476 KB Output is correct
5 Correct 1862 ms 473500 KB Output is correct
6 Correct 1626 ms 459188 KB Output is correct
7 Correct 2136 ms 481704 KB Output is correct
8 Correct 2023 ms 458964 KB Output is correct
9 Correct 1245 ms 511604 KB Output is correct
10 Correct 1705 ms 581232 KB Output is correct
11 Correct 1821 ms 501272 KB Output is correct
12 Correct 1893 ms 502136 KB Output is correct
13 Correct 1143 ms 341972 KB Output is correct
14 Correct 1140 ms 335048 KB Output is correct
15 Correct 1323 ms 348552 KB Output is correct
16 Correct 1353 ms 356984 KB Output is correct
17 Correct 1362 ms 359960 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 56656 KB Output is correct
2 Correct 33 ms 56652 KB Output is correct
3 Correct 34 ms 56652 KB Output is correct
4 Correct 29 ms 56652 KB Output is correct
5 Correct 30 ms 56948 KB Output is correct
6 Correct 32 ms 56872 KB Output is correct
7 Correct 30 ms 56808 KB Output is correct
8 Correct 30 ms 56904 KB Output is correct
9 Correct 30 ms 56800 KB Output is correct
10 Correct 31 ms 56916 KB Output is correct
11 Correct 36 ms 56840 KB Output is correct
12 Correct 29 ms 56936 KB Output is correct
13 Correct 29 ms 56880 KB Output is correct
14 Correct 31 ms 56836 KB Output is correct
15 Correct 29 ms 56840 KB Output is correct
16 Correct 29 ms 56904 KB Output is correct
17 Correct 29 ms 56856 KB Output is correct
18 Correct 30 ms 56832 KB Output is correct
19 Correct 30 ms 56884 KB Output is correct
20 Correct 31 ms 56816 KB Output is correct
21 Correct 28 ms 56744 KB Output is correct
22 Correct 30 ms 56792 KB Output is correct
23 Correct 30 ms 56836 KB Output is correct
24 Correct 30 ms 56840 KB Output is correct
25 Correct 30 ms 56912 KB Output is correct
26 Correct 33 ms 56920 KB Output is correct
27 Correct 31 ms 56784 KB Output is correct
28 Correct 30 ms 56868 KB Output is correct
29 Correct 32 ms 56824 KB Output is correct
30 Correct 37 ms 56712 KB Output is correct
31 Correct 441 ms 95684 KB Output is correct
32 Correct 117 ms 78436 KB Output is correct
33 Correct 423 ms 94704 KB Output is correct
34 Correct 426 ms 92344 KB Output is correct
35 Correct 464 ms 95256 KB Output is correct
36 Correct 438 ms 94896 KB Output is correct
37 Correct 387 ms 88668 KB Output is correct
38 Correct 370 ms 88724 KB Output is correct
39 Correct 329 ms 86044 KB Output is correct
40 Correct 339 ms 86624 KB Output is correct
41 Correct 314 ms 81776 KB Output is correct
42 Correct 324 ms 82604 KB Output is correct
43 Correct 64 ms 70396 KB Output is correct
44 Correct 309 ms 82052 KB Output is correct
45 Correct 316 ms 82408 KB Output is correct
46 Correct 248 ms 81296 KB Output is correct
47 Correct 234 ms 79108 KB Output is correct
48 Correct 227 ms 79380 KB Output is correct
49 Correct 278 ms 80336 KB Output is correct
50 Correct 278 ms 80844 KB Output is correct
51 Correct 243 ms 80336 KB Output is correct
52 Correct 247 ms 80188 KB Output is correct
53 Correct 277 ms 79168 KB Output is correct
54 Correct 348 ms 88444 KB Output is correct
55 Correct 298 ms 82484 KB Output is correct
56 Correct 287 ms 81516 KB Output is correct
57 Correct 311 ms 83028 KB Output is correct
58 Correct 307 ms 82164 KB Output is correct
59 Correct 299 ms 82108 KB Output is correct
60 Correct 332 ms 82160 KB Output is correct
61 Correct 59 ms 72284 KB Output is correct
62 Correct 244 ms 84956 KB Output is correct
63 Correct 375 ms 86416 KB Output is correct
64 Correct 364 ms 87380 KB Output is correct
65 Correct 381 ms 84156 KB Output is correct
66 Correct 367 ms 82356 KB Output is correct
67 Correct 102 ms 79656 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 56656 KB Output is correct
2 Correct 33 ms 56652 KB Output is correct
3 Correct 34 ms 56652 KB Output is correct
4 Correct 29 ms 56652 KB Output is correct
5 Correct 30 ms 56948 KB Output is correct
6 Correct 32 ms 56872 KB Output is correct
7 Correct 30 ms 56808 KB Output is correct
8 Correct 30 ms 56904 KB Output is correct
9 Correct 30 ms 56800 KB Output is correct
10 Correct 31 ms 56916 KB Output is correct
11 Correct 36 ms 56840 KB Output is correct
12 Correct 29 ms 56936 KB Output is correct
13 Correct 29 ms 56880 KB Output is correct
14 Correct 31 ms 56836 KB Output is correct
15 Correct 29 ms 56840 KB Output is correct
16 Correct 29 ms 56904 KB Output is correct
17 Correct 29 ms 56856 KB Output is correct
18 Correct 30 ms 56832 KB Output is correct
19 Correct 30 ms 56884 KB Output is correct
20 Correct 31 ms 56816 KB Output is correct
21 Correct 28 ms 56744 KB Output is correct
22 Correct 30 ms 56792 KB Output is correct
23 Correct 30 ms 56836 KB Output is correct
24 Correct 30 ms 56840 KB Output is correct
25 Correct 30 ms 56912 KB Output is correct
26 Correct 33 ms 56920 KB Output is correct
27 Correct 31 ms 56784 KB Output is correct
28 Correct 30 ms 56868 KB Output is correct
29 Correct 32 ms 56824 KB Output is correct
30 Correct 37 ms 56712 KB Output is correct
31 Correct 441 ms 95684 KB Output is correct
32 Correct 117 ms 78436 KB Output is correct
33 Correct 423 ms 94704 KB Output is correct
34 Correct 426 ms 92344 KB Output is correct
35 Correct 464 ms 95256 KB Output is correct
36 Correct 438 ms 94896 KB Output is correct
37 Correct 387 ms 88668 KB Output is correct
38 Correct 370 ms 88724 KB Output is correct
39 Correct 329 ms 86044 KB Output is correct
40 Correct 339 ms 86624 KB Output is correct
41 Correct 314 ms 81776 KB Output is correct
42 Correct 324 ms 82604 KB Output is correct
43 Correct 64 ms 70396 KB Output is correct
44 Correct 309 ms 82052 KB Output is correct
45 Correct 316 ms 82408 KB Output is correct
46 Correct 248 ms 81296 KB Output is correct
47 Correct 234 ms 79108 KB Output is correct
48 Correct 227 ms 79380 KB Output is correct
49 Correct 278 ms 80336 KB Output is correct
50 Correct 278 ms 80844 KB Output is correct
51 Correct 243 ms 80336 KB Output is correct
52 Correct 426 ms 146304 KB Output is correct
53 Correct 615 ms 143748 KB Output is correct
54 Correct 308 ms 142484 KB Output is correct
55 Correct 418 ms 146328 KB Output is correct
56 Correct 683 ms 143696 KB Output is correct
57 Correct 609 ms 143644 KB Output is correct
58 Correct 257 ms 142444 KB Output is correct
59 Correct 292 ms 143724 KB Output is correct
60 Correct 333 ms 143716 KB Output is correct
61 Correct 392 ms 141428 KB Output is correct
62 Correct 350 ms 141084 KB Output is correct
63 Correct 338 ms 142020 KB Output is correct
64 Correct 2061 ms 478328 KB Output is correct
65 Correct 557 ms 182844 KB Output is correct
66 Correct 2045 ms 471432 KB Output is correct
67 Correct 1285 ms 547476 KB Output is correct
68 Correct 1862 ms 473500 KB Output is correct
69 Correct 1626 ms 459188 KB Output is correct
70 Correct 2136 ms 481704 KB Output is correct
71 Correct 2023 ms 458964 KB Output is correct
72 Correct 1245 ms 511604 KB Output is correct
73 Correct 1705 ms 581232 KB Output is correct
74 Correct 1821 ms 501272 KB Output is correct
75 Correct 1893 ms 502136 KB Output is correct
76 Correct 1143 ms 341972 KB Output is correct
77 Correct 1140 ms 335048 KB Output is correct
78 Correct 1323 ms 348552 KB Output is correct
79 Correct 1353 ms 356984 KB Output is correct
80 Correct 1362 ms 359960 KB Output is correct
81 Correct 247 ms 80188 KB Output is correct
82 Correct 277 ms 79168 KB Output is correct
83 Correct 348 ms 88444 KB Output is correct
84 Correct 298 ms 82484 KB Output is correct
85 Correct 287 ms 81516 KB Output is correct
86 Correct 311 ms 83028 KB Output is correct
87 Correct 307 ms 82164 KB Output is correct
88 Correct 299 ms 82108 KB Output is correct
89 Correct 332 ms 82160 KB Output is correct
90 Correct 59 ms 72284 KB Output is correct
91 Correct 244 ms 84956 KB Output is correct
92 Correct 375 ms 86416 KB Output is correct
93 Correct 364 ms 87380 KB Output is correct
94 Correct 381 ms 84156 KB Output is correct
95 Correct 367 ms 82356 KB Output is correct
96 Correct 102 ms 79656 KB Output is correct
97 Correct 1424 ms 187908 KB Output is correct
98 Correct 630 ms 173680 KB Output is correct
99 Correct 2590 ms 231144 KB Output is correct
100 Correct 1454 ms 167044 KB Output is correct
101 Correct 2172 ms 221920 KB Output is correct
102 Correct 2690 ms 257848 KB Output is correct
103 Correct 2084 ms 219172 KB Output is correct
104 Correct 2056 ms 216400 KB Output is correct
105 Correct 1813 ms 206116 KB Output is correct
106 Correct 1799 ms 207376 KB Output is correct
107 Correct 1442 ms 195644 KB Output is correct
108 Correct 1374 ms 188896 KB Output is correct
109 Correct 1541 ms 192904 KB Output is correct
110 Correct 1587 ms 187400 KB Output is correct
111 Correct 1552 ms 185276 KB Output is correct
112 Correct 1629 ms 189292 KB Output is correct
113 Correct 207 ms 141016 KB Output is correct
114 Correct 1386 ms 204388 KB Output is correct
115 Correct 1811 ms 201992 KB Output is correct
116 Correct 1943 ms 203972 KB Output is correct
117 Correct 2009 ms 198860 KB Output is correct
118 Correct 1775 ms 189168 KB Output is correct
119 Correct 467 ms 179792 KB Output is correct
120 Correct 914 ms 161960 KB Output is correct
121 Correct 1116 ms 183848 KB Output is correct
122 Correct 1060 ms 182824 KB Output is correct
123 Correct 1216 ms 183400 KB Output is correct
124 Correct 1420 ms 190776 KB Output is correct
125 Correct 1174 ms 185740 KB Output is correct
126 Correct 1460 ms 182900 KB Output is correct