Submission #49578

#	Time	Username	Problem	Language	Result	Execution time	Memory
49578		Diuven	New Home (APIO18_new_home)	C++11	100 / 100	4849 ms	370900 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef multiset<int>::iterator mit;
const int MX=300010, inf=1<<29;

struct SHOP {
	int x, type, s, e, idx;
} S[MX];

struct QUERY {
	int x, t, idx, ans;
} Q[MX];

inline int max(int x, int y){ return x>y ? x : y; }

int n, q, k;

void input(){
	cin>>n>>k>>q;
	for(int i=1; i<=n; i++){
		int t, x, s, e;
		cin>>x>>t>>s>>e;
		S[i]={x,t,s,e,i};
	}
	for(int i=1; i<=q; i++){
		int x, t;
		cin>>x>>t;
		Q[i]={x,t,i};
	}
}

vector<int> X;
int xmax;

int lo(int x){
	return upper_bound(X.begin(), X.end(), x)-X.begin()-1;
}
int hi(int x){
	return lower_bound(X.begin(), X.end(), x)-X.begin();
}

void prec(){
	for(int i=1; i<=n; i++){
		S[i].x*=2;
	}
	for(int i=1; i<=q; i++){
		Q[i].x*=2;
		X.push_back(Q[i].x);
	}
	sort(X.begin(), X.end());
	X.resize(unique(X.begin(), X.end())-X.begin());
	xmax=X.size()-1U;
}

//////

multiset<int> pos[MX];
int nonzero_cnt;

struct SegTree {
	int tree[4*MX]={};
	multiset<int> leaf[MX];
	// [0, xmax]

	void init(){
		for(int i=1; i<=4*xmax; i++) tree[i]=-inf;
	}

	int mx(int v, int s, int e, int l, int r){
		if(r<s || e<l) return -inf;
		if(l<=s && e<=r) return tree[v];
		return max(mx(v*2, s, (s+e)/2, l, r), mx(v*2+1, (s+e)/2+1, e, l, r));
	}
	int mx(int l, int r){
		return mx(1,0,xmax,l,r);
	}
	void upt(int v, int s, int e, int x){
		if(x<s || e<x) return;
		if(s==e){
			if(leaf[x].empty()) tree[v]=-inf;
			else tree[v]=*leaf[x].rbegin();
			return;
		}
		upt(v*2, s, (s+e)/2, x);
		upt(v*2+1, (s+e)/2+1, e, x);
		tree[v]=max(tree[v*2], tree[v*2+1]);
	}
	void put(int x, int val){
		if(x<0 || xmax<x) return;
		leaf[x].insert(val);
		upt(1,0,xmax,x);
	}
	void pop(int x, int val){
		if(x<0 || xmax<x) return;
		leaf[x].erase(leaf[x].find(val));
		upt(1,0,xmax,x);
	}
} Seg1, Seg2;

// 1이 /, 2가 \
//1: max(y-x), 2: max(y+x)

void add(int x1, int x2){
	int mx=(0LL+x1+x2)/2, my=(0LL+x2-x1)/2;
	int pos=hi(mx);
	Seg1.put(pos-1, my-mx);
	Seg2.put(pos, my+mx);
}

void del(int x1, int x2){
	int mx=(0LL+x1+x2)/2, my=(0LL+x2-x1)/2;
	int pos=hi(mx);
	Seg1.pop(pos-1, my-mx);
	Seg2.pop(pos, my+mx);
}

int find(int qx){
	if(nonzero_cnt<k) return -2;
	int x=lo(qx);
	int ans=max(Seg1.mx(x, xmax)+qx, Seg2.mx(0, x)-qx);
	return ans;
}

////

void add_store(int idx){
	multiset<int> &stores = pos[S[idx].type];

	if(stores.size()==2U) nonzero_cnt++;

	int x=S[idx].x;

	if(stores.find(x)==stores.end()){
		mit it1=stores.lower_bound(x), it2=it1; it2--;
		int lx=*it2, rx=*it1;
		del(lx, rx);
		add(lx, x); add(x, rx);
	}

	stores.insert(x);
}

void del_store(int idx){
	multiset<int> &stores = pos[S[idx].type];

	if(stores.size()==3U) nonzero_cnt--;

	int x=S[idx].x;

	stores.erase(stores.find(x));

	if(stores.find(x)!=stores.end())
		return;

	mit it1=stores.lower_bound(x), it2=it1; it2--;
	int lx=*it2, rx=*it1;
	del(lx, x); del(x, rx);
	add(lx, rx);
}

void init(){
	Seg1.init();
	Seg2.init();
	for(int i=1; i<=k; i++){
		pos[i].insert(inf);
		pos[i].insert(-inf);
		add(-inf, inf);
	}
}

void solve(){
	vector<pii> in, out;
	for(int i=1; i<=n; i++){
		in.push_back({S[i].s, i});
		out.push_back({S[i].e, i});
	}
	sort(Q+1, Q+q+1, [](QUERY &a, QUERY &b){ return a.t<b.t; });
	sort(in.begin(), in.end());
	sort(out.begin(), out.end());

	init();

	for(int i=1, a=0, b=0; i<=q; i++){
		int qt=Q[i].t, qx=Q[i].x;
		while(a<n){
			int t,idx; tie(t,idx)=in[a];
			if(qt<t) break;
			a++;
			add_store(idx);
		}
		while(b<n){
			int t,idx; tie(t,idx)=out[b];
			if(qt<=t) break;
			b++;
			del_store(idx);
		}
		Q[i].ans=find(qx);
	}
}


int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	input();
	prec();
	solve();

	sort(Q+1, Q+q+1, [](QUERY &a, QUERY &b){ return a.idx<b.idx; });
	for(int i=1; i<=q; i++){
		cout<<Q[i].ans/2<<'\n';
	}
	return 0;
}

Compilation message (stderr)

new_home.cpp:102:1: warning: multi-line comment [-Wcomment]
 // 1이 /, 2가 \
 ^

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