oj.uz

Submission #277773

# Submission time Handle Problem Language Result Execution time Memory
277773 2020-08-21T07:19:31 Z 임성재(#5118) Interval Collection (CCO20_day2problem2) C++17
4 / 25
 1571 ms 218584 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<int,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;

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

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());

			int k = tl.cal(r, 1000000) - l;
			if(k < 1000000) pQ.em(k, mp(l, r));
			
			k = r + tr.cal(1, l);
			if(k < 1000000) pQ.em(k, 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());
		}

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

			if((s.find(mp(l, r)) != s.end()) && (tl.cal(r, 1000000) - l == k || r + tr.cal(1, l) == k)) {
				break;
			}
			if(s.find(mp(l, r)) != s.end()) {	
				int k = tl.cal(r, 1000000) - l;
				if(k < 1000000) pQ.em(k, mp(l, r));
				
				k = r + tr.cal(1, l);
				if(k < 1000000) pQ.em(k, mp(l, r));
			}

			pQ.pop();
		}

		if(pQ.empty()) cout << *ans.begin() << "\n";
		else cout << pQ.top().fi << "\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;
      |           ~~^~~

Subtask #1
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 110712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 110712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 110712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 514 ms 154272 KB Output is correct
2 Correct 514 ms 154120 KB Output is correct
3 Correct 937 ms 196524 KB Output is correct
4 Correct 966 ms 196492 KB Output is correct
5 Correct 1165 ms 218264 KB Output is correct
6 Correct 1232 ms 218584 KB Output is correct
7 Correct 1227 ms 125976 KB Output is correct
8 Correct 899 ms 123672 KB Output is correct
9 Correct 883 ms 123416 KB Output is correct
10 Correct 1336 ms 135540 KB Output is correct
11 Correct 926 ms 123808 KB Output is correct
12 Correct 893 ms 123524 KB Output is correct
13 Correct 1571 ms 136776 KB Output is correct
14 Correct 1004 ms 123844 KB Output is correct
15 Correct 886 ms 123400 KB Output is correct
16 Correct 924 ms 118396 KB Output is correct
17 Correct 919 ms 118200 KB Output is correct
18 Correct 927 ms 118324 KB Output is correct
19 Correct 935 ms 118324 KB Output is correct
20 Correct 944 ms 118352 KB Output is correct

Subtask #5
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 110712 KB Output isn't correct
2 Halted 0 ms 0 KB -