Submission #1272253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272253		thuhienne	Interval Collection (CCO20_day2problem2)	C++20	25 / 25	727 ms	168664 KiB

Main

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

const int inf = 1e9;

int q,n = 1000000;

multiset <int> leftend[1000009],rightend[1000009];

int getmax(multiset <int>& s) {
	if (s.empty()) return -inf;
	return *s.rbegin();
}
int getmin(multiset <int>& s) {
	if (s.empty()) return inf;
	return *s.begin();
}

struct node {
	int minr,maxl,res;
};
node st[1000009 * 4];

void build(int id,int l,int r) {
	st[id] = {inf,-inf,inf};
	if (l == r) return;
	int mid = (l + r) >> 1;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
}
void updatel(int id,int l,int r,int u,int v) {
	if (l > v || r < v) return;
	if (l == r) {
		st[id].maxl = u;
		st[id].res = st[id].minr - st[id].maxl;
		return;
	}
	int mid = (l + r) >> 1;
	updatel(id*2,l,mid,u,v);
	updatel(id*2+1,mid+1,r,u,v);
	st[id].maxl = max(st[id * 2].maxl,st[id*2 + 1].maxl);
	st[id].minr = min(st[id * 2].minr,st[id*2 + 1].minr);
	st[id].res = min({st[id*2].res,st[id*2+1].res,st[id*2+1].minr - st[id*2].maxl});
}
void updater(int id,int l,int r,int u,int v) {
	if (l > u || r < u) return;
	if (l == r) {
		st[id].minr = v;
		st[id].res = st[id].minr - st[id].maxl;
		return;
	}
	int mid = (l + r) >> 1;
	updater(id*2,l,mid,u,v);
	updater(id*2+1,mid+1,r,u,v);
	st[id].maxl = max(st[id * 2].maxl,st[id*2 + 1].maxl);
	st[id].minr = min(st[id * 2].minr,st[id*2 + 1].minr);
	st[id].res = min({st[id*2].res,st[id*2+1].res,st[id*2+1].minr - st[id*2].maxl});
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(nullptr);
	//freopen(".inp","r",stdin);
	//freopen(".out","w",stdout);
	cin >> q;
	
	build(1,1,n);
	while (q--) {
		char op;int l,r;
		cin >> op >> l >> r;
		if (op == 'A') {
			leftend[l].insert(r);
			rightend[r].insert(l);
			if (l == getmax(rightend[r])) {
				updatel(1,1,n,l,r);
			}
			if (r == getmin(leftend[l])) {
				updater(1,1,n,l,r);
			}
		} else {
			leftend[l].erase(leftend[l].find(r));
			rightend[r].erase(rightend[r].find(l));
			if (l > getmax(rightend[r])) {
				updatel(1,1,n,getmax(rightend[r]),r);
			}
			if (r < getmin(leftend[l])) {
				updater(1,1,n,l,getmin(leftend[l]));
			}
		}
		if (st[1].minr >= st[1].maxl) {
			cout << getmin(leftend[st[1].maxl]) - getmax(rightend[st[1].minr]) << '\n';
		}
		else cout << st[1].res << '\n';
	}
}

/*
  Nho doi vai em gay
			  co gai ay ngoi duoi goc pho nen tho ...
*/

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 4 / 4
• Subtask 5: 3 / 3