oj.uz

Submission #1108426

# Submission time Handle Problem Language Result Execution time Memory
1108426 2024-11-04T06:02:05 Z Tsagana Weighting stones (IZhO11_stones) C++17
100 / 100
 190 ms 5812 KB 
#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define lnl long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

struct lf {
	int an1, ah1;
	int an2, ah2;

	void set(int x) {
		an1 = ah1 = 0;
		an2 = ah2 = 0;

		if (x == 1) an1 = an2 = 1;
		else ah1 = ah2 = 1;
	}
	void merge(lf x, lf y) {
		an1 = x.an1; ah1 = y.ah1;
		an2 = y.an2; ah2 = x.ah2;
		
		if (y.an1 < x.ah1) ah1 += x.ah1-y.an1;
		else an1 += y.an1-x.ah1;

		if (y.ah2 < x.an2) an2 += x.an2-y.ah2;
		else ah2 += y.ah2-x.an2;
	}
};

int n;
pair<int, int> mx;
lf S[400001];

void print(int i) {
	cout << i << ": " << S[i].an1 << ' ' << S[i].ah1 << " - ";
	cout << S[i].an2 << ' ' << S[i].ah2 << '\n';
} 
void build(int id, int L, int R) {
	print(id);
	if (L == R) {return ;}
	int M = (L+R)/2, x = 2*id, y = x+1;
	build(x, L, M);
	build(y, M+1, R);
}
void update(int id, int L, int R, int i, int k) {
	if (L == R) {S[id].set(k); return ;}
	int M = (L+R)/2, x = 2*id, y = x+1;
	if (i <= M) update(x, L, M, i, k);
	else update(y, M+1, R, i, k);
	S[id].merge(S[x], S[y]);
} void update(int i, int k) {update(1, 1, n, i, k);}

void solve () {
	cin >> n;
	mx = {0, 0};
	for (int i = 0; i < n; i++) {
		int a, b; cin >> a >> b;
		if (mx.F < a) mx = {a, b};
		update(a, b);

		if (mx.S == 1) cout << (!S[1].ah1 ? ">\n" : "?\n");
		else cout << (!S[1].an2 ? "<\n" : "?\n");
	}
	//build(1, 1, n);
}
int main() {IOS solve(); return 0;}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 3 ms 336 KB Output is correct
9 Correct 3 ms 336 KB Output is correct
10 Correct 16 ms 2640 KB Output is correct
11 Correct 96 ms 3108 KB Output is correct
12 Correct 163 ms 5448 KB Output is correct
13 Correct 160 ms 5544 KB Output is correct
14 Correct 157 ms 5708 KB Output is correct
15 Correct 166 ms 5652 KB Output is correct
16 Correct 170 ms 5704 KB Output is correct
17 Correct 190 ms 5704 KB Output is correct
18 Correct 159 ms 5704 KB Output is correct
19 Correct 160 ms 5704 KB Output is correct
20 Correct 156 ms 5644 KB Output is correct
21 Correct 172 ms 5540 KB Output is correct
22 Correct 160 ms 5812 KB Output is correct
23 Correct 156 ms 5612 KB Output is correct
24 Correct 159 ms 5704 KB Output is correct
25 Correct 157 ms 5704 KB Output is correct