oj.uz

답안 #683390

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
683390 2023-01-18T10:14:08 Z vovamr 돌 무게 재기 (IZhO11_stones) C++17
100 / 100
 43 ms 7648 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

struct node {
	int cnt[2];
	node() { cnt[0] = cnt[1] = 0; }
	node(int x) { cnt[0] = cnt[1] = 0; ++cnt[x]; }
};
inline node mg(const node &a, const node &b) {
	node res;
	int f = min(a.cnt[0], b.cnt[1]);
	res.cnt[0] = a.cnt[0] + b.cnt[0] - f;
	res.cnt[1] = a.cnt[1] + b.cnt[1] - f;
	return res;
}
struct seg {
	int n;
	ve<node> t;
	inline void build(int v, int vl, int vr) {
		if (vl == vr) return void(t[v] = node());
		int m = vl + vr >> 1;
		build(2 * v + 1, vl, m);
		build(2 * v + 2, m + 1, vr);
		t[v] = mg(t[2 * v + 1], t[2 * v + 2]);
	}
	inline void upd(int v, int vl, int vr, int pos, int x) {
		if (vl == vr) return void(t[v] = node(x));
		int m = vl + vr >> 1;
		if (pos <= m) upd(2 * v + 1, vl, m, pos, x);
		else upd(2 * v + 2, m + 1, vr, pos, x);
		t[v] = mg(t[2 * v + 1], t[2 * v + 2]);
	}

	seg(int n) : n(n) {
		t.resize(4 * n);
		build(0, 0, n - 1);
	}
	inline void upd(int pos, int x) { upd(0, 0, n - 1, pos, x); }

	inline bool winning() {
		return t[0].cnt[0] == 0;
	}
};

inline void solve() {
	int n;
	cin >> n;

	seg s1(n), s2(n);

	for (int it = 0; it < n; ++it) {
		int x, c;
		cin >> x >> c, --x;

		s1.upd(x, (c == 1 ? 0 : 1));
		s2.upd(x, (c == 1 ? 1 : 0));

		bool f1 = s1.winning();
		bool f2 = s2.winning();

		if (!(f1 ^ f2)) cout << "?" << '\n';
		else if (f1) cout << "<" << '\n';
		else cout << ">" << '\n';
	}
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Compilation message

stones.cpp: In member function 'void seg::build(int, int, int)':
stones.cpp:40:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |   int m = vl + vr >> 1;
      |           ~~~^~~~
stones.cpp: In member function 'void seg::upd(int, int, int, int, int)':
stones.cpp:47:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   int m = vl + vr >> 1;
      |           ~~~^~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 320 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 4 ms 852 KB Output is correct
11 Correct 25 ms 4368 KB Output is correct
12 Correct 43 ms 6816 KB Output is correct
13 Correct 38 ms 7560 KB Output is correct
14 Correct 42 ms 7544 KB Output is correct
15 Correct 40 ms 7536 KB Output is correct
16 Correct 39 ms 7500 KB Output is correct
17 Correct 38 ms 7456 KB Output is correct
18 Correct 40 ms 7592 KB Output is correct
19 Correct 38 ms 7508 KB Output is correct
20 Correct 38 ms 7648 KB Output is correct
21 Correct 39 ms 7532 KB Output is correct
22 Correct 40 ms 7500 KB Output is correct
23 Correct 38 ms 7548 KB Output is correct
24 Correct 38 ms 7508 KB Output is correct
25 Correct 38 ms 7488 KB Output is correct