oj.uz

Submission #277902

# Submission time Handle Problem Language Result Execution time Memory
277902 2020-08-21T07:57:19 Z 송준혁(#5117) Interval Collection (CCO20_day2problem2) C++17
0 / 25
 1451 ms 1048580 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define Mup(a,x) a=max(a, x)
#define mup(a,x) a=min(a, x)
#define all(v) v.begin(),v.end()
#define lb lower_bound
#define INF (1ll<<60)
#define MOD 1'000'000'007 
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N=1000010, Q;
pii T[4040404];
multiset<pii> L[4040404], R[4040404];
multiset<int> xL[4040404], xR[4040404];

void upd(int id, int s, int e, int t, int l, int r){
	if ((t<=1?l:r) < s || e < (t<=1?l:r)) return;
	if (t==0) L[id].insert(pii(l, -r)), xR[id].insert(r);
	if (t==1) L[id].erase(L[id].find(pii(l, -r))), xR[id].erase(xR[id].find(r));
	if (t==2) R[id].insert(pii(r, -l)), xL[id].insert(l);
	if (t==3) R[id].erase(R[id].find(pii(r, -l))), xL[id].erase(xL[id].find(l));
	if (s == e){
		T[id] = pii(N+1, 0);
		if (xL[id].size() && xR[id].size()) T[id] = pii(0, *xR[id].rbegin()-*xL[id].begin());
		return;
	}
	int m=s+e>>1;
	upd(id*2, s, m, t, l, r);
	upd(id*2+1, m+1, e, t, l, r);
	T[id] = min(T[id*2], T[id*2+1]);
	if (L[id*2].size() && R[id*2+1].size()){
		pii x=*L[id*2].rbegin(), y=*R[id*2+1].begin();
		T[id] = min(T[id], pii(y.fi-x.fi, -x.se+y.se));
	}
	if (xL[id*2].size() && xR[id*2+1].size()){
		T[id] = min(T[id], pii(0, *xR[id*2+1].rbegin()-*xL[id*2].begin()));
	}
}

int main(){
	scanf("%d", &Q);
	for (int i=1; i<=4*N; i++) T[i]=pii(N+1, 0);
	while (Q--){
		char ch;
		int l, r;
		scanf(" %c %d %d", &ch, &l, &r);
		upd(1, 1, N, 0+(ch=='R'), l, r);
		upd(1, 1, N, 2+(ch=='R'), l, r);
		printf("%d\n", T[1].se);
	}
	return 0;
}

Compilation message

Main.cpp: In function 'void upd(int, int, int, int, int, int)':
Main.cpp:31:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |  int m=s+e>>1;
      |        ~^~
Main.cpp: In function 'int main()':
Main.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
Main.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |   scanf(" %c %d %d", &ch, &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 526 ms 791804 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 526 ms 791804 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 526 ms 791804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 1451 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 3.0

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