Submission #1014194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014194		pcc	New Home (APIO18_new_home)	C++17	12 / 100	1448 ms	593456 KiB

new_home

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")

#define _all(T) T.begin(),T.end()
#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 1e6;
const int inf = 1e9;
const int lim = 1e8+10;

struct SEG{
#define mid ((l+r)>>1)
#define ls now*2+1
#define rs now*2+2
	int seg[mxn*4];
	pii op[mxn];
	int head[mxn];
	int cnt = 0;
	SEG(){
		fill(seg,seg+mxn*4,-inf);
	}
	void modify(int now,int l,int r,int s,int e,int v,bool rec = false){
		if(rec&&now == 0){
			cnt++;
			head[cnt] = head[cnt-1];
		}
		if(l>=s&&e>=r){
			if(rec){
				op[++head[cnt]] = pii(now,seg[now]);
			}
			seg[now] = max(seg[now],v);
			return;
		}
		if(mid>=s)modify(ls,l,mid,s,e,v,rec);
		if(mid<e)modify(rs,mid+1,r,s,e,v,rec);
		return;
	}
	void undo(){
		assert(cnt);
		while(head[cnt]>head[cnt-1]){
			auto &[p,v] = op[head[cnt]--];
			seg[p] = v;
		}
		cnt--;
		return;
	}
	int getval(int now,int l,int r,int p){
		if(l == r)return seg[now];
		if(mid>=p)return max(seg[now],getval(ls,l,mid,p));
		else return max(seg[now],getval(rs,mid+1,r,p));
	}
#undef mid
#undef ls
#undef rs
};

SEG seg1,seg2;
int N,K,Q;
multiset<int> st[mxn];
vector<int> all;
vector<int> allt;
vector<pii> req;
array<int,4> shop[mxn];
int ans[mxn];
vector<pii> tseg[mxn*4];
vector<pii> ask[mxn];

void addev(int now,int l,int r,int s,int e,pii val){
	assert(e>=s);
	if(l>=s&&e>=r){
		tseg[now].push_back(val);
		return;
	}
	int mid = (l+r)>>1;
	if(mid>=s)addev(now*2+1,l,mid,s,e,val);
	if(mid<e)addev(now*2+2,mid+1,r,s,e,val);
	return;
}

void del(int pos,int tp){
	st[tp].erase(st[tp].find(pos));
	auto lit = --st[tp].lower_bound(pos);
	auto rit = st[tp].lower_bound(pos);
	int mid = all[*lit]+(all[*rit]-all[*lit])/2;
	int mp = upper_bound(_all(all),mid)-all.begin();
	//cerr<<"DEL: "<<pos<<' '<<tp<<"::"<<*lit<<' '<<mp<<' '<<*rit<<endl;
	seg1.modify(0,0,all.size(),*lit,mp-1,-all[*lit],1);
	seg2.modify(0,0,all.size(),mp,*rit,all[*rit],1);
	//cerr<<"DEL DONE! "<<endl;
	return;
}

void undo(){
	seg1.undo();
	seg2.undo();
}

void dfs(int now,int l,int r){
	//cerr<<"DFS IN: "<<l<<' '<<r<<endl;
	for(auto &i:tseg[now])del(i.fs,i.sc);
	if(l == r){
		for(auto &i:ask[l]){//p,idx
			//cerr<<"ASK: "<<i.fs<<','<<i.sc<<' '<<all[i.fs]<<' '<<seg1.getval(0,0,all.size(),i.fs)<<' '<<seg2.getval(0,0,all.size(),i.fs)<<endl;
			ans[i.sc] = max(all[i.fs]+seg1.getval(0,0,all.size(),i.fs),seg2.getval(0,0,all.size(),i.fs)-all[i.fs]);
		}
	}
	else{
		int mid = (l+r)>>1;
		dfs(now*2+1,l,mid);
		dfs(now*2+2,mid+1,r);
	}
	for(auto &[pos,tp]:tseg[now]){
		undo();
		//cerr<<"UNDO: "<<pos<<','<<tp<<endl;
		st[tp].insert(pos);
	}
	//cerr<<"DFS OUT: "<<l<<' '<<r<<endl;
	return;
}

int main(){

	cin>>N>>K>>Q;
	allt.push_back(-1);
	for(int i = 1;i<=N;i++){
		cin>>shop[i][0]>>shop[i][1]>>shop[i][2]>>shop[i][3];//x,t,a,b
		all.push_back(shop[i][0]);
		allt.push_back(shop[i][2]);
		allt.push_back(shop[i][3]);
	}
	for(int i = 0;i<Q;i++){
		int l,y;
		cin>>l>>y;
		all.push_back(l);
		allt.push_back(y);
		req.push_back(pii(l,y));
	}
	all.push_back(-inf);all.push_back(inf);
	sort(_all(all));all.resize(unique(_all(all))-all.begin());
	sort(_all(allt));allt.resize(unique(_all(allt))-allt.begin());
	//cerr<<"ALL: ";for(auto &i:all)cerr<<i<<' ';cerr<<endl;
	//cerr<<"ALLT: ";for(auto &i:allt)cerr<<i<<' ';cerr<<endl;
	for(int i = 1;i<=K;i++){
		st[i].insert(0);
		st[i].insert(all.size()-1);
	}
	for(int i = 1;i<=N;i++){
		shop[i][0] = lower_bound(_all(all),shop[i][0])-all.begin();
		st[shop[i][1]].insert(shop[i][0]);
		shop[i][2] = lower_bound(_all(allt),shop[i][2])-allt.begin();
		shop[i][3] = lower_bound(_all(allt),shop[i][3])-allt.begin();
	}
	for(int i = 1;i<=K;i++){
		for(auto it = ++st[i].begin();it != st[i].end();it++){
			int l = *prev(it),r = *it;
			int mid = all[l]+(all[r]-all[l])/2;
			auto pos = upper_bound(_all(all),mid)-all.begin();
			seg1.modify(0,0,all.size(),l,pos-1,-all[l]);
			seg2.modify(0,0,all.size(),pos,r,all[r]);
		}
	}
	//cerr<<"INIT DONE!"<<endl;
	for(int i = 1;i<=N;i++){
		int pos = shop[i][0],tp = shop[i][1],s = shop[i][2],e = shop[i][3];
		//cerr<<"ADDEV: "<<0<<' '<<s-1<<' '<<pos<<' '<<tp<<endl;
		//cerr<<"ADDEV: "<<e+1<<' '<<allt.size()<<' '<<pos<<' '<<tp<<endl;
		addev(0,0,allt.size(),0,s-1,pii(pos,tp));
		addev(0,0,allt.size(),e+1,allt.size(),pii(pos,tp));
	}
	for(int i = 0;i<Q;i++){
		auto &[p,t] = req[i];
		p = lower_bound(_all(all),p)-all.begin();
		t = lower_bound(_all(allt),t)-allt.begin();
		//cerr<<"ASK POS: "<<p<<' '<<t<<endl;
		ask[t].push_back(pii(p,i));
	}

	//cerr<<"ADDEV DONE!"<<' '<<seg1.getval(0,0,all.size(),req[0].fs)<<' '<<seg2.getval(0,0,all.size(),req[0].fs)<<endl;

	dfs(0,0,allt.size());
	assert(!seg1.cnt);
	assert(!seg2.cnt);
	//cerr<<"DFS DONE! "<<endl;
	for(int i = 0;i<Q;i++)cout<<(ans[i]>lim?-1:ans[i])<<'\n';
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20