oj.uz

Submission #173251

# Submission time Handle Problem Language Result Execution time Memory
173251 2020-01-03T16:25:24 Z kig9981 New Home (APIO18_new_home) C++17
5 / 100
 5000 ms 512468 KB 
#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;

struct Seg
{
	int l, r, v;
	Seg() : l(0), r(0), v(0) {}
} tree[40000000];

const int SZ=1<<19;
multiset<int> P[300000];
tuple<int,int,int> Q[300000], L[300000], R[300000];
int node_cnt, xsz, ans[300000], X[300000];

void add_tree2(int n, int v, int p, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	if(s==e) {
		tree[p].v+=v;
		return;
	}
	if(n<=m) {
		if(tree[p].l==0) tree[p].l=node_cnt++;
		add_tree2(n,v,tree[p].l,s,m);
	}
	else {
		if(tree[p].r==0) tree[p].r=node_cnt++;
		add_tree2(n,v,tree[p].r,m+1,e);
	}
	tree[p].v=tree[tree[p].l].v+tree[tree[p].r].v;
}

void add_tree(int x, int y, int v)
{
	for(++x;x<=xsz;x+=x&-x) add_tree2(y,v,x);
}

int get_cnt2(int n1, int n2, int p, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	if(p==0 || n2<n1 || n2<s || e<n1) return 0;
	if(n1<=s && e<=n2) return tree[p].v;
	return get_cnt2(n1,n2,tree[p].l,s,m)+get_cnt2(n1,n2,tree[p].r,m+1,e);
}

int get_cnt(int n1, int n2, int p)
{
	int ret=0;
	for(++p;p;p-=p&-p) ret+=get_cnt2(n1,n2,p);
	return ret;
}

int get_cnt(int x1, int y1, int x2, int y2)
{
	return get_cnt(y1,y2,x2)-get_cnt(y1,y2,x1-1);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, K, M, p1=0, p2=0;
	cin>>N>>K>>M;
	for(int i=0;i<N;i++) {
		int p, t, a, b;
		cin>>p>>t>>a>>b; --t;
		X[i]=p;
		L[i]={a,t,p};
		R[i]={b,t,p};
	}
	sort(X,X+N);
	xsz=unique(X,X+N)-X;
	for(int i=0;i<N;i++) get<2>(L[i])=get<2>(R[i])=lower_bound(X,X+xsz,get<2>(L[i]))-X;
	sort(L,L+N);
	sort(R,R+N);
	for(int i=0;i<M;i++) {
		auto &[t,p,idx]=Q[i];
		cin>>p>>t; idx=i;
	}
	sort(Q,Q+M);
	node_cnt=xsz+1;
	for(int c=0;c<M;c++) {
		auto[t,p,i]=Q[c];
		int s=0, e=1e8;
		while(p1<N && get<0>(L[p1])<=t) {
			auto[t,v,p]=L[p1++];
			auto r=P[v].lower_bound(p), l=r;
			if(r!=P[v].end() && *r==p) {
				P[v].insert(p);
				continue;
			}
			if(r!=P[v].begin()) l=r,--l;
			else l=P[v].end();
			if(l!=P[v].end() && r!=P[v].end()) add_tree(*l,*r,1);
			if(l!=P[v].end()) add_tree(*l,p,-1);
			if(r!=P[v].end()) add_tree(p,*r,-1);
			add_tree(p,p,1);
			P[v].insert(p);
		}
		while(p2<N && get<0>(R[p2])<t) {
			auto[t,v,p]=R[p2++];
			P[v].erase(P[v].find(p));
			auto r=P[v].lower_bound(p), l=r;
			if(r!=P[v].end() && *r==p) continue;
			if(r!=P[v].begin()) l=r,--l;
			else l=P[v].end();
			if(l!=P[v].end() && r!=P[v].end()) add_tree(*l,*r,-1);
			if(l!=P[v].end()) add_tree(*l,p,1);
			if(r!=P[v].end()) add_tree(p,*r,1);
			add_tree(p,p,-1);
		}
		if(get_cnt(0,0,xsz-1,xsz-1)<K) {
			ans[i]=-1;
			continue;
		}
		while(s<=e) {
			int m=(s+e)>>1, l, r;
			l=lower_bound(X,X+xsz,p-m)-X;
			r=upper_bound(X,X+xsz,p+m)-X-1;
			if(l<=r && get_cnt(l,l,r,r)==K) e=m-1;
			else s=m+1;
		}
		if(s>1e8) ans[i]=-1;
		else ans[i]=s;
	}
	for(int i=0;i<M;i++) cout<<ans[i]<<'\n';
	return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:98:14: warning: unused variable 't' [-Wunused-variable]
    auto[t,v,p]=L[p1++];
              ^
new_home.cpp:113:14: warning: unused variable 't' [-Wunused-variable]
    auto[t,v,p]=R[p2++];
              ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 484216 KB Output is correct
2 Correct 413 ms 484048 KB Output is correct
3 Correct 412 ms 484088 KB Output is correct
4 Correct 440 ms 484088 KB Output is correct
5 Correct 424 ms 484216 KB Output is correct
6 Correct 426 ms 484328 KB Output is correct
7 Correct 416 ms 484216 KB Output is correct
8 Correct 431 ms 484340 KB Output is correct
9 Correct 419 ms 484180 KB Output is correct
10 Correct 430 ms 484344 KB Output is correct
11 Correct 434 ms 484216 KB Output is correct
12 Correct 427 ms 484252 KB Output is correct
13 Correct 415 ms 484216 KB Output is correct
14 Correct 423 ms 484156 KB Output is correct
15 Correct 435 ms 484216 KB Output is correct
16 Correct 446 ms 484376 KB Output is correct
17 Correct 423 ms 484216 KB Output is correct
18 Correct 418 ms 484216 KB Output is correct
19 Correct 419 ms 484248 KB Output is correct
20 Correct 427 ms 484204 KB Output is correct
21 Correct 413 ms 484204 KB Output is correct
22 Correct 420 ms 484216 KB Output is correct
23 Correct 416 ms 484216 KB Output is correct
24 Correct 422 ms 484396 KB Output is correct
25 Correct 428 ms 484128 KB Output is correct
26 Correct 427 ms 484348 KB Output is correct
27 Correct 421 ms 484204 KB Output is correct
28 Correct 424 ms 484120 KB Output is correct
29 Correct 424 ms 484188 KB Output is correct
30 Correct 423 ms 484088 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 484216 KB Output is correct
2 Correct 413 ms 484048 KB Output is correct
3 Correct 412 ms 484088 KB Output is correct
4 Correct 440 ms 484088 KB Output is correct
5 Correct 424 ms 484216 KB Output is correct
6 Correct 426 ms 484328 KB Output is correct
7 Correct 416 ms 484216 KB Output is correct
8 Correct 431 ms 484340 KB Output is correct
9 Correct 419 ms 484180 KB Output is correct
10 Correct 430 ms 484344 KB Output is correct
11 Correct 434 ms 484216 KB Output is correct
12 Correct 427 ms 484252 KB Output is correct
13 Correct 415 ms 484216 KB Output is correct
14 Correct 423 ms 484156 KB Output is correct
15 Correct 435 ms 484216 KB Output is correct
16 Correct 446 ms 484376 KB Output is correct
17 Correct 423 ms 484216 KB Output is correct
18 Correct 418 ms 484216 KB Output is correct
19 Correct 419 ms 484248 KB Output is correct
20 Correct 427 ms 484204 KB Output is correct
21 Correct 413 ms 484204 KB Output is correct
22 Correct 420 ms 484216 KB Output is correct
23 Correct 416 ms 484216 KB Output is correct
24 Correct 422 ms 484396 KB Output is correct
25 Correct 428 ms 484128 KB Output is correct
26 Correct 427 ms 484348 KB Output is correct
27 Correct 421 ms 484204 KB Output is correct
28 Correct 424 ms 484120 KB Output is correct
29 Correct 424 ms 484188 KB Output is correct
30 Correct 423 ms 484088 KB Output is correct
31 Execution timed out 5056 ms 490920 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 484216 KB Output is correct
2 Correct 413 ms 484048 KB Output is correct
3 Correct 412 ms 484088 KB Output is correct
4 Correct 440 ms 484088 KB Output is correct
5 Correct 424 ms 484216 KB Output is correct
6 Correct 426 ms 484328 KB Output is correct
7 Correct 416 ms 484216 KB Output is correct
8 Correct 431 ms 484340 KB Output is correct
9 Correct 419 ms 484180 KB Output is correct
10 Correct 430 ms 484344 KB Output is correct
11 Correct 434 ms 484216 KB Output is correct
12 Correct 427 ms 484252 KB Output is correct
13 Correct 415 ms 484216 KB Output is correct
14 Correct 423 ms 484156 KB Output is correct
15 Correct 435 ms 484216 KB Output is correct
16 Correct 446 ms 484376 KB Output is correct
17 Correct 423 ms 484216 KB Output is correct
18 Correct 418 ms 484216 KB Output is correct
19 Correct 419 ms 484248 KB Output is correct
20 Correct 427 ms 484204 KB Output is correct
21 Correct 413 ms 484204 KB Output is correct
22 Correct 420 ms 484216 KB Output is correct
23 Correct 416 ms 484216 KB Output is correct
24 Correct 422 ms 484396 KB Output is correct
25 Correct 428 ms 484128 KB Output is correct
26 Correct 427 ms 484348 KB Output is correct
27 Correct 421 ms 484204 KB Output is correct
28 Correct 424 ms 484120 KB Output is correct
29 Correct 424 ms 484188 KB Output is correct
30 Correct 423 ms 484088 KB Output is correct
31 Execution timed out 5056 ms 490920 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 484216 KB Output is correct
2 Correct 413 ms 484048 KB Output is correct
3 Correct 412 ms 484088 KB Output is correct
4 Correct 440 ms 484088 KB Output is correct
5 Correct 424 ms 484216 KB Output is correct
6 Correct 426 ms 484328 KB Output is correct
7 Correct 416 ms 484216 KB Output is correct
8 Correct 431 ms 484340 KB Output is correct
9 Correct 419 ms 484180 KB Output is correct
10 Correct 430 ms 484344 KB Output is correct
11 Correct 434 ms 484216 KB Output is correct
12 Correct 427 ms 484252 KB Output is correct
13 Correct 415 ms 484216 KB Output is correct
14 Correct 423 ms 484156 KB Output is correct
15 Correct 435 ms 484216 KB Output is correct
16 Correct 446 ms 484376 KB Output is correct
17 Correct 423 ms 484216 KB Output is correct
18 Correct 418 ms 484216 KB Output is correct
19 Correct 419 ms 484248 KB Output is correct
20 Correct 427 ms 484204 KB Output is correct
21 Correct 413 ms 484204 KB Output is correct
22 Correct 420 ms 484216 KB Output is correct
23 Correct 416 ms 484216 KB Output is correct
24 Correct 422 ms 484396 KB Output is correct
25 Correct 428 ms 484128 KB Output is correct
26 Correct 427 ms 484348 KB Output is correct
27 Correct 421 ms 484204 KB Output is correct
28 Correct 424 ms 484120 KB Output is correct
29 Correct 424 ms 484188 KB Output is correct
30 Correct 423 ms 484088 KB Output is correct
31 Execution timed out 5056 ms 490920 KB Time limit exceeded
32 Halted 0 ms 0 KB -