oj.uz

Submission #173241

# Submission time Handle Problem Language Result Execution time Memory
173241 2020-01-03T16:04:09 Z kig9981 New Home (APIO18_new_home) C++17
0 / 100
 5000 ms 489716 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) {}
};

const int SZ=1<<19;
vector<Seg> tree;
vector<int> X;
multiset<int> P[300000];
vector<tuple<int,int,int,int>> S;
vector<tuple<int,int,int>> Q, L, R;
int ans[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=tree.size(), tree.push_back(Seg());
		add_tree2(n,v,tree[p].l,s,m);
	}
	else {
		if(tree[p].r==0) tree[p].r=tree.size(), tree.push_back(Seg());
		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<=X.size();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.push_back(p);
	}
	sort(X.begin(),X.end());
	X.resize(unique(X.begin(),X.end())-X.begin());
	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.begin(),X.end(),p)-X.begin();
		L.emplace_back(a,t,p);
		R.emplace_back(b,t,p);
	}
	sort(L.begin(),L.end());
	sort(R.begin(),R.end());
	tree.resize(X.size()+1);
	for(auto[t,p,i]: Q) {
		int s=0, e=1e8, pl=0, pr=X.size()-1;
		bool res=true;
		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,X.size()-1,X.size()-1)<K) {
			ans[i]=-1;
			continue;
		}
		while(s<=e) {
			int m=(s+e)>>1, l, r;
			l=lower_bound(X.begin(),X.end(),p-m)-X.begin();
			r=upper_bound(X.begin(),X.end(),p+m)-X.begin()-1;
			if(pl==l && pr==r) {
				if(res) e=m-1;
				else s=m+1;
				continue;
			}
			if((pl=l)<=(pr=r) && (res=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 'void add_tree(int, int, int)':
new_home.cpp:47:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(++x;x<=X.size();x+=x&-x) add_tree2(y,v,x);
          ~^~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:103:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p1<L.size() && get<0>(L[p1])<=t) {
         ~~^~~~~~~~~
new_home.cpp:104:14: warning: unused variable 't' [-Wunused-variable]
    auto[t,v,p]=L[p1++];
              ^
new_home.cpp:118:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p2<R.size() && get<0>(R[p2])<t) {
         ~~^~~~~~~~~
new_home.cpp:119:14: warning: unused variable 't' [-Wunused-variable]
    auto[t,v,p]=R[p2++];
              ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 14 ms 14456 KB Output is correct
3 Correct 15 ms 14456 KB Output is correct
4 Incorrect 15 ms 14456 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 14 ms 14456 KB Output is correct
3 Correct 15 ms 14456 KB Output is correct
4 Incorrect 15 ms 14456 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5124 ms 488664 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 5066 ms 489716 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 14 ms 14456 KB Output is correct
3 Correct 15 ms 14456 KB Output is correct
4 Incorrect 15 ms 14456 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 14 ms 14456 KB Output is correct
3 Correct 15 ms 14456 KB Output is correct
4 Incorrect 15 ms 14456 KB Output isn't correct
5 Halted 0 ms 0 KB -