제출 #497303

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
497303		jamezzz	New Home (APIO18_new_home)	C++17	100 / 100	2690 ms	581232 KiB

new_home

#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 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 20 / 20