oj.uz

답안 #683898

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
683898 2023-01-19T15:04:41 Z KiriLL1ca 돌 무게 재기 (IZhO11_stones) C++17
100 / 100
 106 ms 6080 KB 
#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

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) {}
      |         ^~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 7 ms 828 KB Output is correct
11 Correct 51 ms 3484 KB Output is correct
12 Correct 86 ms 5328 KB Output is correct
13 Correct 86 ms 6000 KB Output is correct
14 Correct 98 ms 5860 KB Output is correct
15 Correct 88 ms 6080 KB Output is correct
16 Correct 85 ms 5928 KB Output is correct
17 Correct 87 ms 5976 KB Output is correct
18 Correct 92 ms 5964 KB Output is correct
19 Correct 106 ms 5968 KB Output is correct
20 Correct 96 ms 5964 KB Output is correct
21 Correct 86 ms 5904 KB Output is correct
22 Correct 89 ms 5888 KB Output is correct
23 Correct 92 ms 5920 KB Output is correct
24 Correct 101 ms 5920 KB Output is correct
25 Correct 95 ms 6028 KB Output is correct