Submission #683898

#TimeUsernameProblemLanguageResultExecution timeMemory
683898KiriLL1caWeighting stones (IZhO11_stones)C++17
100 / 100
106 ms6080 KiB
#include <bits/stdc++.h>
#define vec vector
#define forn(i, s, f) for (int i = s; i <= f; ++i)
#define pb push_back
#define sz(x) (int)((int)(x).size())
#define endl '\n'

using namespace std;

typedef long long ll;
template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }

typedef pair <int, int> pii;

struct segtree {
        int n; vector <int> tmx, tmn, p;
        segtree (int n = 0) : n(n), tmn(4 * n), tmx(4 * n), p(4 * n) {}
        inline void push (int v, int tl, int tr) {
                if (p[v] && tl != tr) {
                        p[v << 1] += p[v];
                        p[v << 1 | 1] += p[v];
                        tmn[v << 1] += p[v];
                        tmn[v << 1 | 1] += p[v];
                        tmx[v << 1] += p[v];
                        tmx[v << 1 | 1] += p[v];
                        p[v] = 0;
                }
        }
        inline void upd (int v, int tl, int tr, int l, int r, int x) {
                if (tl > r || l > tr) return;
                if (l <= tl && tr <= r) {
                        tmx[v] += x; tmn[v] += x;
                        p[v] += x; push(v, tl, tr);
                        return;
                }
                int tm = (tl + tr) >> 1; push(v, tl, tr);
                upd(v << 1, tl, tm, l, r, x);
                upd(v << 1 | 1, tm + 1, tr, l, r, x);
                tmn[v] = min(tmn[v << 1], tmn[v << 1 | 1]);
                tmx[v] = max(tmx[v << 1], tmx[v << 1 | 1]);
        }

        inline void upd (int l, int r, int x) { upd(1, 0, n - 1, l, r, x); }
        inline int gmin () { return tmn[1]; }
        inline int gmax () { return tmx[1]; }
};

inline void solve () {
        int q; cin >> q;
        segtree s (q + 1);
        while (q--) {
                int a, b; cin >> a >> b;
                s.upd(1, a, (b == 2 ? -1 : +1));
                if (s.gmin() >= 0) cout << ">" << endl;
                else if (s.gmax() <= 0) cout << "<" << endl;
                else cout << "?" << endl;
        }
}

signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        #ifdef LOCAL
                freopen("input.txt", "r", stdin);
                freopen("output.txt", "w", stdout);
        #else
                
        #endif
        int t = 1; //cin >> t;
        while (t--) solve();
        return 0;
}

Compilation message (stderr)

stones.cpp: In constructor 'segtree::segtree(int)':
stones.cpp:17:34: warning: 'segtree::tmn' will be initialized after [-Wreorder]
   17 |         int n; vector <int> tmx, tmn, p;
      |                                  ^~~
stones.cpp:17:29: warning:   'std::vector<int> segtree::tmx' [-Wreorder]
   17 |         int n; vector <int> tmx, tmn, p;
      |                             ^~~
stones.cpp:18:9: warning:   when initialized here [-Wreorder]
   18 |         segtree (int n = 0) : n(n), tmn(4 * n), tmx(4 * n), p(4 * n) {}
      |         ^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...