oj.uz

Submission #173247

# Submission time Handle Problem Language Result Execution time Memory
173247 2020-01-03T16:14:33 Z kig9981 New Home (APIO18_new_home) C++17
5 / 100
 5000 ms 516420 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];
vector<tuple<int,int,int,int>> S;
vector<tuple<int,int,int>> Q, L, R;
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;
	S.resize(N);
	for(auto &[p,t,a,b]: S) {
		cin>>p>>t>>a>>b; --t;
		X[xsz++]=p;
	}
	sort(X,X+N);
	xsz=unique(X,X+N)-X;
	Q.resize(M);
	for(int i=0;i<M;i++) {
		auto &[t,p,idx]=Q[i];
		cin>>p>>t; idx=i;
	}
	sort(Q.begin(),Q.end());
	for(auto &[p,t,a,b]: S) {
		p=lower_bound(X,X+xsz,p)-X;
		L.emplace_back(a,t,p);
		R.emplace_back(b,t,p);
	}
	sort(L.begin(),L.end());
	sort(R.begin(),R.end());
	node_cnt=xsz+1;
	for(auto[t,p,i]: Q) {
		int s=0, e=1e8;
		while(p1<L.size() && 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<R.size() && 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:100:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p1<L.size() && get<0>(L[p1])<=t) {
         ~~^~~~~~~~~
new_home.cpp:101:14: warning: unused variable 't' [-Wunused-variable]
    auto[t,v,p]=L[p1++];
              ^
new_home.cpp:115:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p2<R.size() && get<0>(R[p2])<t) {
         ~~^~~~~~~~~
new_home.cpp:116: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 468 ms 484040 KB Output is correct
2 Correct 413 ms 484216 KB Output is correct
3 Correct 412 ms 484120 KB Output is correct
4 Correct 416 ms 484156 KB Output is correct
5 Correct 439 ms 484192 KB Output is correct
6 Correct 493 ms 484224 KB Output is correct
7 Correct 421 ms 484140 KB Output is correct
8 Correct 415 ms 484096 KB Output is correct
9 Correct 417 ms 484128 KB Output is correct
10 Correct 428 ms 484180 KB Output is correct
11 Correct 429 ms 484276 KB Output is correct
12 Correct 428 ms 484344 KB Output is correct
13 Correct 415 ms 484152 KB Output is correct
14 Correct 419 ms 484176 KB Output is correct
15 Correct 425 ms 484204 KB Output is correct
16 Correct 424 ms 484256 KB Output is correct
17 Correct 425 ms 484216 KB Output is correct
18 Correct 422 ms 484136 KB Output is correct
19 Correct 417 ms 484188 KB Output is correct
20 Correct 421 ms 484164 KB Output is correct
21 Correct 418 ms 484136 KB Output is correct
22 Correct 419 ms 484216 KB Output is correct
23 Correct 421 ms 484136 KB Output is correct
24 Correct 421 ms 484216 KB Output is correct
25 Correct 422 ms 484140 KB Output is correct
26 Correct 430 ms 484332 KB Output is correct
27 Correct 432 ms 484188 KB Output is correct
28 Correct 421 ms 484192 KB Output is correct
29 Correct 422 ms 484088 KB Output is correct
30 Correct 418 ms 484224 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 484040 KB Output is correct
2 Correct 413 ms 484216 KB Output is correct
3 Correct 412 ms 484120 KB Output is correct
4 Correct 416 ms 484156 KB Output is correct
5 Correct 439 ms 484192 KB Output is correct
6 Correct 493 ms 484224 KB Output is correct
7 Correct 421 ms 484140 KB Output is correct
8 Correct 415 ms 484096 KB Output is correct
9 Correct 417 ms 484128 KB Output is correct
10 Correct 428 ms 484180 KB Output is correct
11 Correct 429 ms 484276 KB Output is correct
12 Correct 428 ms 484344 KB Output is correct
13 Correct 415 ms 484152 KB Output is correct
14 Correct 419 ms 484176 KB Output is correct
15 Correct 425 ms 484204 KB Output is correct
16 Correct 424 ms 484256 KB Output is correct
17 Correct 425 ms 484216 KB Output is correct
18 Correct 422 ms 484136 KB Output is correct
19 Correct 417 ms 484188 KB Output is correct
20 Correct 421 ms 484164 KB Output is correct
21 Correct 418 ms 484136 KB Output is correct
22 Correct 419 ms 484216 KB Output is correct
23 Correct 421 ms 484136 KB Output is correct
24 Correct 421 ms 484216 KB Output is correct
25 Correct 422 ms 484140 KB Output is correct
26 Correct 430 ms 484332 KB Output is correct
27 Correct 432 ms 484188 KB Output is correct
28 Correct 421 ms 484192 KB Output is correct
29 Correct 422 ms 484088 KB Output is correct
30 Correct 418 ms 484224 KB Output is correct
31 Execution timed out 5102 ms 490960 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 5119 ms 516288 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 5076 ms 516420 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 484040 KB Output is correct
2 Correct 413 ms 484216 KB Output is correct
3 Correct 412 ms 484120 KB Output is correct
4 Correct 416 ms 484156 KB Output is correct
5 Correct 439 ms 484192 KB Output is correct
6 Correct 493 ms 484224 KB Output is correct
7 Correct 421 ms 484140 KB Output is correct
8 Correct 415 ms 484096 KB Output is correct
9 Correct 417 ms 484128 KB Output is correct
10 Correct 428 ms 484180 KB Output is correct
11 Correct 429 ms 484276 KB Output is correct
12 Correct 428 ms 484344 KB Output is correct
13 Correct 415 ms 484152 KB Output is correct
14 Correct 419 ms 484176 KB Output is correct
15 Correct 425 ms 484204 KB Output is correct
16 Correct 424 ms 484256 KB Output is correct
17 Correct 425 ms 484216 KB Output is correct
18 Correct 422 ms 484136 KB Output is correct
19 Correct 417 ms 484188 KB Output is correct
20 Correct 421 ms 484164 KB Output is correct
21 Correct 418 ms 484136 KB Output is correct
22 Correct 419 ms 484216 KB Output is correct
23 Correct 421 ms 484136 KB Output is correct
24 Correct 421 ms 484216 KB Output is correct
25 Correct 422 ms 484140 KB Output is correct
26 Correct 430 ms 484332 KB Output is correct
27 Correct 432 ms 484188 KB Output is correct
28 Correct 421 ms 484192 KB Output is correct
29 Correct 422 ms 484088 KB Output is correct
30 Correct 418 ms 484224 KB Output is correct
31 Execution timed out 5102 ms 490960 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 484040 KB Output is correct
2 Correct 413 ms 484216 KB Output is correct
3 Correct 412 ms 484120 KB Output is correct
4 Correct 416 ms 484156 KB Output is correct
5 Correct 439 ms 484192 KB Output is correct
6 Correct 493 ms 484224 KB Output is correct
7 Correct 421 ms 484140 KB Output is correct
8 Correct 415 ms 484096 KB Output is correct
9 Correct 417 ms 484128 KB Output is correct
10 Correct 428 ms 484180 KB Output is correct
11 Correct 429 ms 484276 KB Output is correct
12 Correct 428 ms 484344 KB Output is correct
13 Correct 415 ms 484152 KB Output is correct
14 Correct 419 ms 484176 KB Output is correct
15 Correct 425 ms 484204 KB Output is correct
16 Correct 424 ms 484256 KB Output is correct
17 Correct 425 ms 484216 KB Output is correct
18 Correct 422 ms 484136 KB Output is correct
19 Correct 417 ms 484188 KB Output is correct
20 Correct 421 ms 484164 KB Output is correct
21 Correct 418 ms 484136 KB Output is correct
22 Correct 419 ms 484216 KB Output is correct
23 Correct 421 ms 484136 KB Output is correct
24 Correct 421 ms 484216 KB Output is correct
25 Correct 422 ms 484140 KB Output is correct
26 Correct 430 ms 484332 KB Output is correct
27 Correct 432 ms 484188 KB Output is correct
28 Correct 421 ms 484192 KB Output is correct
29 Correct 422 ms 484088 KB Output is correct
30 Correct 418 ms 484224 KB Output is correct
31 Execution timed out 5102 ms 490960 KB Time limit exceeded
32 Halted 0 ms 0 KB -