Submission #217325

#	Time	Username	Problem	Language	Result	Execution time	Memory
217325		theStaticMind	New Home (APIO18_new_home)	C++14	100 / 100	4233 ms	217696 KiB

new_home

#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 1e9
#define modulo 1000000007
#define mod 998244353
//#define int long long int
using namespace std;

int S;

struct MaxSeg{
	vector<int> seg;

	void build(){
		S = (1 << (int)ceil(log2(sz(seg))));
		int l = S - sz(seg);
		for(int i = 0; i < l; i++) seg.pb(-INF);
		reverse(all(seg));
		for(int i = 1; i < sz(seg); i += 2) seg.pb(max(seg[i - 1], seg[i]));
		seg.pb(0);
		reverse(all(seg));
	}

	MaxSeg(int n){
		seg = vector<int>(n, -INF);
		build();
	}

	int query(int a, int b, int j = 1, int l = 0, int r = S - 1){
		if(r < a || b < l) return -INF;
		if(a <= l && r <= b) return seg[j];
		return max(query(a,b,j*2,l,(l+r)/2), query(a,b,j*2+1,(l+r)/2+1,r));
	}
	void update(int j, int v){
		j += S;
		seg[j] = v;
		j /= 2;
		while(j != 0){
			seg[j] = max(seg[j * 2], seg[j * 2 + 1]);
			j /= 2;
		}
	}
};

struct Store{
	int x, type, tl, tr, id;
};
struct Query{
	int x, time, id;
};
struct Event{
	int t, l, r, i, id; 
	Event(int a, int b, int c, int d, int e){
		t=a,l=b,r=c,i=d,id=e;
	}
	int mid(){
		return (1ll * l + 1ll * r) / 2;
	}
	bool operator<=(Event& A){
		if(mid() < A.mid()) return true;
		if(mid() == A.mid()){
			if(id <= A.id) return true;
		}
		return false;
	}

} ;
vector<Event> E;

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
  
	int n, k, q;
	cin >> n >> k >> q;

	vector<Store> X, Y;
	vector<Query> Q;
	vector<int> ans(q);
	vector<int> cnt(k + 1, 0);
	map<int, int> K[k + 1];
	int c = k;

	for(int i = 1; i <= k; i++) {
		K[i][1e9]++, K[i][-1e9]++;
		E.pb(Event(-1, -1e9, 1e9, 1, i));
	}

	for(int i = 0; i < n; i++){
		int a, b, c, d; 
		cin >> a >> b >> c >> d; a*=2;
		X.pb({a, b, c, d, i});
		Y.pb({a, b, c, d, i});
	}
	for(int i = 0; i < q; i++){
		int a, b; 
		cin >> a >> b; a*=2;
		Q.pb({a, b, i});
	}

	sort(all(X), [&](Store& A, Store& B){return A.tl < B.tl;});
	sort(all(Y), [&](Store& A, Store& B){return A.tr < B.tr;});
	sort(all(Q), [&](Query& A, Query& B){return A.time < B.time;});

	int a = 0, b = 0;

	for(auto& curr : Q){
		while(a < n && X[a].tl <= curr.time){
			int t = X[a].type, x = X[a].x;
			if(++cnt[t] == 1) c--;

			if(!K[t].count(x)){
				auto next = K[t].upper_bound(x);
				auto prev = std::prev(next);

				E.pb(Event(X[a].tl, prev->first, next->first, 0, t));
				E.pb(Event(X[a].tl, prev->first, x, 1, t));
				E.pb(Event(X[a].tl, x, next->first, 1, t));

			}
			K[t][x]++;

			a++;
		}
		while(b < n && Y[b].tr < curr.time){
			int t = Y[b].type, x = Y[b].x;
			if(--cnt[Y[b].type] == 0) c++;

			if(K[t][x] == 1){	
				K[t].erase(x);

				auto next = K[t].upper_bound(x);
				auto prev = std::prev(next);
				
				E.pb(Event(Y[b].tr+1, prev->first, x, 0, t));
				E.pb(Event(Y[b].tr+1, x, next->first, 0, t));
				E.pb(Event(Y[b].tr+1, prev->first, next->first, 1, t));
			}
			else{
				K[t][x]--;
			}

			b++;
		}
		if(c > 0){
			ans[curr.id] = -2;
			continue;
		}

	}

	MaxSeg L(sz(E)), R(sz(E));

	a = 0;

	vector<int> seq;
	for(int i = 0; i < sz(E); i++) if(E[i].i) seq.pb(i);
	sort(all(seq), [&](int x, int y){return E[x] <= E[y];});

	auto lower = [&](Event x){
		int l = 0, r = sz(seq) - 1;
		int ret = 0;
		while(l <= r){
			int mid = (l + r) / 2;
			if(x <= E[seq[mid]]){
				ret = mid;
				r = mid - 1;
			}
			else l = mid + 1;
		}
		return ret;
	};
	int w;
	for(auto& curr : Q){
		while(a < sz(E) && E[a].t <= curr.time){
			w = lower(E[a]);
			if(E[a].i){
				R.update(w, -E[a].l);
				L.update(w, E[a].r);
			}
			else{
				R.update(w, -INF);
				L.update(w, -INF);
			}
			a++;
		}
		if(ans[curr.id] == -2){
			continue;
		}
		int x = curr.x;
		w = lower(Event(0,x,x,1,-1));
		ans[curr.id] = max(L.query(0, w - 1) - x, R.query(w, S-1) + x);

	}

	for(int i = 0; i < q; i++) cout << ans[i] / 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