Submission #217055

#	Time	Username	Problem	Language	Result	Execution time	Memory
217055		theStaticMind	New Home (APIO18_new_home)	C++14	5 / 100	5105 ms	185060 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 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;
#define rand() (1ll * rand() * rand() + rand() + 1)

struct Node{
	int left = 0, right = 0;
	int mx = -INF, val = -INF;
	int key = 0, prior = 0;

	Node(){}
	Node(int k, int v){
		key = k;
		val = mx = v;
		prior = rand();
	}

	bool operator<(Node& A){
		return key < A.key || (key == A.key && val < A.val);
	}
} node[3000000];

int new_node(int k, int v){
	static int ind = 1;
	node[ind].key = k;
	node[ind].val = node[ind].mx = v;
	node[ind].prior = rand();
	return ind++;
}

struct Treap{
	int root = 0;
	void up(int j){
		if(!j)return;
		int l = node[j].left, r = node[j].right;
		node[j].mx = max(node[j].val, max(node[l].mx, node[r].mx));
	}
	void split(int j, Node& v, int& l, int& r){
		if(!j) l = r = 0;
		else if(node[j] < v) split(node[j].right, v, node[j].right, r), l = j;
		else split(node[j].left, v, l, node[j].left), r = j;
		up(j);
	}
	void merge(int& j, int l, int r){
		if(!l || !r) j = max(l, r);
		else if(node[l].prior > node[r].prior) merge(node[l].right, node[l].right, r), j = l;
		else merge(node[r].left, l, node[r].left), j = r;
		up(j);
	}
	void insert(int& j, int i){
		if(!j) j = i;
		else if(node[i].prior > node[j].prior) split(j, node[i], node[i].left, node[i].right), j = i;
		else{
			if(node[i] < node[j]) insert(node[j].left, i);
			else insert(node[j].right, i);
		}
		up(j);
	}
	void erase(int& j, Node& v){
		assert(j);
		if(node[j].key == v.key && node[j].val == v.val) merge(j, node[j].left, node[j].right);
		else if(v < node[j]) erase(node[j].left, v);
		else erase(node[j].right, v);
		up(j);
	}
	void add(int k, int v){
		insert(root, new_node(k, v));
	}
	void remove(int k, int v){
		Node t(k, v);
		erase(root, t);
	}
	int query(int x, int y){
		int a, b, c;
		Node t; t.key = x; t.val = -INF;
		split(root, t, a, b);
		t.key = y, t.val = INF;
		split(b, t, b, c);

		int ret = node[b].mx;

		merge(root, a, b);
		merge(root, root, c);

		return ret;
	}
} Ltree, Rtree;

struct Store{
	int x, type, tl, tr;
};
struct Query{
	int x, time, id;
};

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	srand(time(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);
	multiset<int> K[k + 1];
	int c = k;
	for(int i = 1; i <= k; i++) {
		K[i].insert(-2e9), K[i].insert(2e9);
		Rtree.add(0, 2e9);
		Ltree.add(0, 2e9);
	}
	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});
		Y.pb({a, b, c, d});
	}
	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--;

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

			int mid = (*next + *prev) / 2; 

			Rtree.remove(mid, -*prev);
			Ltree.remove(mid, *next);

			mid = (*prev + x) / 2;

			Rtree.add(mid, -*prev);
			Ltree.add(mid, x);
			
			mid = (x + *next) / 2;
			
			Rtree.add(mid, -x);
			Ltree.add(mid, *next);

			K[t].insert(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++;

			K[t].erase(K[t].find(x));
			
			auto next = K[t].upper_bound(x);
			auto prev = std::prev(next);

			int mid = (*prev + x) / 2;

			Rtree.remove(mid, -*prev);
			Ltree.remove(mid, x);
			
			mid = (x + *next) / 2;
			
			Rtree.remove(mid, -x);
			Ltree.remove(mid, *next);
			
			mid = (*next + *prev) / 2; 

			Rtree.add(mid, -*prev);
			Ltree.add(mid, *next);

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

		ans[curr.id] = max(Rtree.query(curr.x, INF) + curr.x, Ltree.query(-INF, curr.x) - curr.x);

	}

	for(int i = 0; i < q; i++) cout << ans[i] / 2 << ' ';
}

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