oj.uz

Submission #166791

# Submission time Handle Problem Language Result Execution time Memory
166791 2019-12-04T06:42:59 Z Dovran Weighting stones (IZhO11_stones) C++11
100 / 100
 408 ms 7672 KB 
#include <bits/stdc++.h>

#define pb push_back
#define ss second
#define ff first
#define N 100005
#define inf 1000000009
#define ll long long
#define mid(a,b) (a+b)/2

using namespace std;

int n,T[4*N][3],T1[4*N][3],mx,mt,t,r;

void upd(int v,int pos,int l,int r,int nd){
	T[nd][1] += T[nd / 2][2];
	T1[nd][1] += T1[nd / 2][2];
	T[nd][2] += T[nd / 2][2];
	T1[nd][2] += T1[nd / 2][2];
	if(r <= pos){
		T[nd][1] += v;
		T[nd][2] += v;
		T1[nd][1] += v;
		T1[nd][2] += v;
		return;
	}
	if(l <= pos){
		upd(v,pos,l,mid(l,r),nd * 2);
		upd(v,pos,mid(l,r)+1,r,nd*2+1);
		T[nd][2] = 0;
		T1[nd][2] = 0;
		T[nd][1] = max(T[nd * 2][1],T[nd * 2 + 1][1]);
		T1[nd][1] = min(T1[nd * 2][1],T1[nd * 2 + 1][1]);
	}
}

int main()
{
	cin>>n;
	for(int i = 1;i <= n;i++){
		cin >> r >> t;
		if(r > mx){
			mx = r;
			mt = t;
		}
		if(t == 1)
			upd(-1,r,1,n,1);
		else upd(1,r,1,n,1);
		if(mt == 1)
			if(T[1][1] <= 0) cout << ">\n";
			else cout << "?\n";
		else {
			if(T1[1][1] >= 0) cout << "<\n";
			else cout << "?\n";
		}
	}
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 7 ms 376 KB Output is correct
9 Correct 6 ms 504 KB Output is correct
10 Correct 36 ms 1144 KB Output is correct
11 Correct 231 ms 4040 KB Output is correct
12 Correct 389 ms 7388 KB Output is correct
13 Correct 384 ms 7672 KB Output is correct
14 Correct 408 ms 7472 KB Output is correct
15 Correct 402 ms 7484 KB Output is correct
16 Correct 387 ms 7544 KB Output is correct
17 Correct 392 ms 7544 KB Output is correct
18 Correct 391 ms 7544 KB Output is correct
19 Correct 392 ms 7516 KB Output is correct
20 Correct 386 ms 7548 KB Output is correct
21 Correct 391 ms 7544 KB Output is correct
22 Correct 393 ms 7544 KB Output is correct
23 Correct 389 ms 7608 KB Output is correct
24 Correct 403 ms 7536 KB Output is correct
25 Correct 395 ms 7440 KB Output is correct