oj.uz

Submission #277901

# Submission time Handle Problem Language Result Execution time Memory
277901 2020-08-21T07:57:02 Z 임성재(#5118) Interval Collection (CCO20_day2problem2) C++17
4 / 25
 2761 ms 276124 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define em emplace
#define mb emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<pii,pii> piii;
const int inf = 1e9;
const ll INF = 1e18;

struct seg {
	int tree[4000010];

	seg() {
		init(1, 1, 1000000);
	}

	void init(int node, int s, int e) {
		tree[node] = inf;
		if(s == e) return;

		init(node*2, s, (s+e)/2);
		init(node*2+1, (s+e)/2+1, e);
	}

	void _update(int node, int s, int e, int i, int x) {
		if(s == e) {
			tree[node] = x;
			return;
		}

		int m = s + e >> 1;
		if(i <= m) _update(node*2, s, m, i, x);
		else _update(node*2+1, m+1, e, i, x);

		tree[node] = min(tree[node*2], tree[node*2+1]);
	}

	int _cal(int node, int s, int e, int l, int r) {
		if(r < s || e < l) return inf;
		if(l <= s && e <= r) return tree[node];

		return min(_cal(node*2, s, (s+e)/2, l, r), _cal(node*2+1, (s+e)/2+1, e, l, r)); 
	}

	void upd(int i, int x) {
		_update(1, 1, 1000000, i, x);
	}

	int cal(int l, int r) {
		return _cal(1, 1, 1000000, l, r);
	}
} tl, tr;

struct SEG {
	pii tree[4000010];

	SEG() {
		init(1, 1, 1000000);
	}

	void init(int node, int s, int e) {
		tree[node] = mp(inf,inf);
		if(s == e) return;

		init(node*2, s, (s+e)/2);
		init(node*2+1, (s+e)/2+1, e);
	}

	void _update(int node, int s, int e, int i, pii x) {
		if(s == e) {
			tree[node] = x;
			return;
		}

		int m = s + e >> 1;
		if(i <= m) _update(node*2, s, m, i, x);
		else _update(node*2+1, m+1, e, i, x);

		tree[node] = min(tree[node*2], tree[node*2+1]);
	}

	pii _cal(int node, int s, int e, int l, int r) {
		if(r < s || e < l) return mp(inf, inf);
		if(l <= s && e <= r) return tree[node];

		return min(_cal(node*2, s, (s+e)/2, l, r), _cal(node*2+1, (s+e)/2+1, e, l, r)); 
	}

	void upd(int i, pii x) {
		_update(1, 1, 1000000, i, x);
	}

	pii cal(int l, int r) {
		return _cal(1, 1, 1000000, l, r);
	}
} TL, TR;

int q;
set<pii> s;
multiset<int> ans;
priority_queue<piii, vector<piii>, greater<piii>> pQ;
multiset<int> L[1000010], R[1000010];

pii f(int l, int r) {
	pii ret = mp(inf,inf);

	int k = tl.cal(r, 1000000) - l;

	if(k < 1000000) ret = min(ret, mp(0, k));
	
	auto x = TL.cal(1, r);
	if(x.fi <= 1000000) ret = min(ret, mp(min(r, x.se) + min(x.fi, -l), max(r, x.se) + min(-l, x.fi)));
	
	k = r + tr.cal(1, l);
	if(k < 1000000) ret = min(ret, mp(0, k));
	
	x = TR.cal(l, 1000000);
	if(x.fi <= 1000000) ret = min(ret, mp(min(x.fi, r) + min(x.se, -l), max(x.fi, r) + max(-l, x.se)));

	return ret;
}

int main() {
	fast;

	cin >> q;

	for(int i=0; i<q; i++) {
		char c;
		int l, r;
		cin >> c >> l >> r;

		if(c == 'A') {
			s.insert(mp(l, r));
			ans.insert(r - l);

			L[l].insert(r);
			R[r].insert(-l);
			tl.upd(l, *L[l].begin());
			tr.upd(r, *R[r].begin());
			TL.upd(l, mp(-l, *L[l].begin()));
			TR.upd(r, mp(r, *R[r].begin()));

			pQ.em(f(l, r), mp(l, r));
		}
		else {
			s.erase(mp(l, r));
			ans.erase(ans.find(r - l));

			L[l].erase(L[l].find(r));
			R[r].erase(R[r].find(-l));

			tl.upd(l, L[l].empty() ? inf : *L[l].begin());
			tr.upd(r, R[r].empty() ? inf : *R[r].begin());
			TL.upd(l, L[l].empty() ? mp(inf,inf) : mp(-l, *L[l].begin()));
			TR.upd(r, R[r].empty() ? mp(inf,inf) : mp(r, *R[r].begin()));
		}

		while(pQ.size()) {
			int l, r;
			pii x = pQ.top().fi;
			tie(l, r) = pQ.top().se;

			if((s.find(mp(l, r)) != s.end()) && x == f(l, r)) {
				break;
			}

			pQ.pop();
			
			if(s.find(mp(l, r)) != s.end()) {	
				pQ.em(f(l, r), mp(l, r));
			}
		}

		cout << pQ.top().fi.se << "\n";
	}
}

Compilation message

Main.cpp: In member function 'void seg::_update(int, int, int, int, int)':
Main.cpp:40:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |   int m = s + e >> 1;
      |           ~~^~~
Main.cpp: In member function 'void SEG::_update(int, int, int, int, pii)':
Main.cpp:84:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |   int m = s + e >> 1;
      |           ~~^~~

Subtask #1
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 173432 KB Output is correct
2 Correct 136 ms 173304 KB Output is correct
3 Incorrect 160 ms 173304 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 173432 KB Output is correct
2 Correct 136 ms 173304 KB Output is correct
3 Incorrect 160 ms 173304 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 173432 KB Output is correct
2 Correct 136 ms 173304 KB Output is correct
3 Incorrect 160 ms 173304 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 979 ms 214532 KB Output is correct
2 Correct 900 ms 214432 KB Output is correct
3 Correct 1656 ms 255588 KB Output is correct
4 Correct 1697 ms 255576 KB Output is correct
5 Correct 2094 ms 276124 KB Output is correct
6 Correct 2091 ms 276096 KB Output is correct
7 Correct 2242 ms 181324 KB Output is correct
8 Correct 1762 ms 179284 KB Output is correct
9 Correct 1849 ms 179232 KB Output is correct
10 Correct 2534 ms 190284 KB Output is correct
11 Correct 1787 ms 180608 KB Output is correct
12 Correct 1528 ms 180316 KB Output is correct
13 Correct 2761 ms 192144 KB Output is correct
14 Correct 1641 ms 180676 KB Output is correct
15 Correct 1643 ms 180340 KB Output is correct
16 Correct 1736 ms 177444 KB Output is correct
17 Correct 1706 ms 177444 KB Output is correct
18 Correct 1654 ms 177464 KB Output is correct
19 Correct 1704 ms 177800 KB Output is correct
20 Correct 1700 ms 177620 KB Output is correct

Subtask #5
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 173432 KB Output is correct
2 Correct 136 ms 173304 KB Output is correct
3 Incorrect 160 ms 173304 KB Output isn't correct
4 Halted 0 ms 0 KB -