oj.uz

Submission #94796

# Submission time Handle Problem Language Result Execution time Memory
94796 2019-01-24T05:13:56 Z jangwonyoung New Home (APIO18_new_home) C++14
33 / 100
 3593 ms 221476 KB 
#include<iostream>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int N=3e5+1,Q=3e5+1,K=3e5+1;
int n,k,q;
struct pt{
	ll x,tp,t;//<0: add, =0: qry, >0: rmv
};
bool operator<(pt x,pt y){
	return x.t<y.t;
}
pt a[2*N];
multiset<ll>s[K];
map<pair<ll,ll>,ll>mp;//should clear after inserting all stores :)
struct upd{
	ll x,l,r,pos;
};
bool operator<(upd x,upd y){
	return x.pos<y.pos;
}
vector<upd>pve,nve;
string f(ll x){
	string ret;
	if(x<=-1e8) return "-inf";
	if(x>=1e8) return "inf";
	if(x==0) ret+='0';
	while(x>0){
		char c=x%10+48;
		x/=10;
		ret=c+ret;
	}
	return ret;
}
void add(ll xl,ll xr,ll t,ll tp){
	mp[{xl,tp}]=t;
}
void rmv(ll xl,ll xr,ll t,ll tp){
	ll p=mp[{xl,tp}];
	if(p==t) return;t--;
	upd pl={-xl,p,t,-(xl+xr)/2};
	upd nl={xr,p,t,(xl+xr+1)/2};
	pve.push_back(pl);nve.push_back(nl);
}
ll ans[Q];
pair<pair<ll,ll>,int>b[Q];
pair<ll,ll>c[Q];
ll st[1<<20];
void init(int id,int l,int r){
	st[id]=-1e9;
	if(l==r) return;
	int mid=(l+r)/2;
	init(id*2,l,mid);init(id*2+1,mid+1,r);
}
void upd(int id,int l,int r,int ql,int qr,ll v){
	if(l>qr || r<ql) return;
	if(ql<=l && r<=qr){
		st[id]=max(st[id],v);
		return;
	}
	int mid=(l+r)/2;
	upd(id*2,l,mid,ql,qr,v);
	upd(id*2+1,mid+1,r,ql,qr,v);
}
ll qry(int id,int l,int r,int p){
	if(l==r) return st[id];
	int mid=(l+r)/2;
	if(p<=mid) return max(st[id],qry(id*2,l,mid,p));
	else return max(st[id],qry(id*2+1,mid+1,r,p));
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> k >> q;
	for(int i=1; i<=n ;i++){
		ll x,tp,u,v;cin >> x >> tp >> u >> v;
		a[i*2-1]={x,-tp,u};
		a[i*2]={x,tp,v+1};
	}
	for(int i=1; i<=k ;i++){
		s[i].insert(-1e9);
		s[i].insert(1e9);
	}
	sort(a+1,a+2*n+1);
	for(int i=1; i<=2*n ;i++){
		ll x=a[i].x,tp=a[i].tp,t=a[i].t;
		if(tp<0){
			tp=-tp;
			auto it=s[tp].lower_bound(x);
			auto it2=it;--it2;
			rmv(*it2,*it,t,tp);add(*it2,x,t,tp);add(x,*it,t,tp);
			s[tp].insert(x);
		}
		else{
			auto it3=s[tp].lower_bound(x);
			auto it=it3;++it;
			auto it2=it3;--it2;
			rmv(*it2,x,t,tp);rmv(x,*it,t,tp);add(*it2,*it,t,tp);
			s[tp].erase(it3);
		}
	}
	for(int i=1; i<=k ;i++) rmv(-1e9,1e9,1e9,i);
	sort(nve.begin(),nve.end());
	sort(pve.begin(),pve.end());
	for(int i=1; i<=q ;i++){
		cin >> b[i].fi.fi >> b[i].fi.se;
		b[i].se=i;
		c[i]={b[i].fi.se,i};
	}
	sort(c+1,c+q+1);
	for(int i=1; i<=q ;i++) b[c[i].se].fi.se=i;
	sort(b+1,b+q+1);
	int ptr=0;
	init(1,1,q);
	for(int i=1; i<=q ;i++){
		while(ptr<nve.size() && nve[ptr].pos<=b[i].fi.fi){
			int l=lower_bound(c+1,c+q+1,(pair<ll,ll>){nve[ptr].l,0LL})-c;
			int r=lower_bound(c+1,c+q+1,(pair<ll,ll>){nve[ptr].r+1,0LL})-c-1;
			if(l<=r) upd(1,1,q,l,r,nve[ptr].x);
			ptr++;
		}
		ans[b[i].se]=max(ans[b[i].se],qry(1,1,q,b[i].fi.se)-b[i].fi.fi);
	}
	init(1,1,q);
	reverse(b+1,b+q+1);
	for(int i=1; i<=q ;i++) b[i].fi.fi=-b[i].fi.fi;
	ptr=0;
	for(int i=1; i<=q ;i++){
		while(ptr<pve.size() && pve[ptr].pos<=b[i].fi.fi){
			int l=lower_bound(c+1,c+q+1,(pair<ll,ll>){pve[ptr].l,0LL})-c;
			int r=lower_bound(c+1,c+q+1,(pair<ll,ll>){pve[ptr].r+1,0LL})-c-1;
			if(l<=r) upd(1,1,q,l,r,pve[ptr].x);
			ptr++;
		}
		ans[b[i].se]=max(ans[b[i].se],qry(1,1,q,b[i].fi.se)-b[i].fi.fi);
	}
	for(int i=1; i<=q ;i++){
		if(ans[i]>=(ll)1e8) cout << "-1\n";
		else cout << ans[i] << '\n';
	}
}

Compilation message

new_home.cpp: In function 'void rmv(ll, ll, ll, ll)':
new_home.cpp:45:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(p==t) return;t--;
  ^~
new_home.cpp:45:18: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(p==t) return;t--;
                  ^
new_home.cpp: In function 'int main()':
new_home.cpp:120:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr<nve.size() && nve[ptr].pos<=b[i].fi.fi){
         ~~~^~~~~~~~~~~
new_home.cpp:133:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr<pve.size() && pve[ptr].pos<=b[i].fi.fi){
         ~~~^~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2596 ms 126152 KB Output is correct
2 Correct 2687 ms 104808 KB Output is correct
3 Correct 2969 ms 209512 KB Output is correct
4 Correct 2343 ms 140508 KB Output is correct
5 Correct 2273 ms 104680 KB Output is correct
6 Correct 2493 ms 105000 KB Output is correct
7 Correct 2302 ms 209168 KB Output is correct
8 Correct 1857 ms 140380 KB Output is correct
9 Correct 1744 ms 116196 KB Output is correct
10 Correct 1934 ms 105688 KB Output is correct
11 Correct 1083 ms 103592 KB Output is correct
12 Correct 1190 ms 105008 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3380 ms 125964 KB Output is correct
2 Correct 779 ms 69900 KB Output is correct
3 Correct 3545 ms 135340 KB Output is correct
4 Correct 3454 ms 220372 KB Output is correct
5 Correct 3593 ms 152472 KB Output is correct
6 Correct 2992 ms 163872 KB Output is correct
7 Correct 2825 ms 134752 KB Output is correct
8 Correct 3366 ms 135252 KB Output is correct
9 Correct 2589 ms 221476 KB Output is correct
10 Correct 3107 ms 158184 KB Output is correct
11 Correct 3135 ms 141256 KB Output is correct
12 Correct 3456 ms 136312 KB Output is correct
13 Correct 1351 ms 132132 KB Output is correct
14 Correct 1276 ms 130700 KB Output is correct
15 Correct 1566 ms 133564 KB Output is correct
16 Correct 1742 ms 135572 KB Output is correct
17 Correct 1731 ms 132928 KB Output is correct

Subtask #5
0 / 35.0

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

Subtask #6
0 / 20.0

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