Submission #683390

#TimeUsernameProblemLanguageResultExecution timeMemory
683390vovamrWeighting stones (IZhO11_stones)C++17
100 / 100
43 ms7648 KiB
#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 (stderr)

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;
      |           ~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...