Submission #89878

#	Time	Username	Problem	Language	Result	Execution time	Memory
89878		popovicirobert	Weighting stones (IZhO11_stones)	C++14	100 / 100	85 ms	16932 KiB

stones

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int MAXN = (int) 1e5;

struct Aint {
    int mn, mx;
    int lazy;
}aint[4 * MAXN + 1];

inline void solve_lazy(int nod) {
    if(2 * nod + 1 <= 4 * MAXN) {
       aint[2 * nod].lazy += aint[nod].lazy;
       aint[2 * nod + 1].lazy += aint[nod].lazy;
    }
    aint[nod].mn += aint[nod].lazy;
    aint[nod].mx += aint[nod].lazy;
    aint[nod].lazy = 0;
}

inline void refresh(int nod) {
    if(2 * nod + 1 > 4 * MAXN) {
        return ;
    }
    solve_lazy(2 * nod);
    solve_lazy(2 * nod + 1);
    aint[nod].mn = min(aint[2 * nod].mn, aint[2 * nod + 1].mn);
    aint[nod].mx = max(aint[2 * nod].mx, aint[2 * nod + 1].mx);
}

void update(int nod, int left, int right, int l, int r, int val) {
    solve_lazy(nod);
    if(l <= left && right <= r) {
        aint[nod].lazy += val;
        solve_lazy(nod);
    }
    else {
        int mid = (left + right) / 2;
        if(l <= mid)
            update(2 * nod, left, mid, l, r, val);
        if(mid < r)
            update(2 * nod + 1, mid + 1, right, l, r, val);
    }
    refresh(nod);
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(i = 1; i <= n; i++) {
        int r, s;
        cin >> r >> s;
        if(s == 1) {
            update(1, 1, n, 1, r, 1);
        }
        else {
            update(1, 1, n, 1, r, -1);
        }
        if(aint[1].mn >= 0) {
            cout << '>';
        }
        else if(aint[1].mx <= 0) {
            cout << '<';
        }
        else {
            cout << '?';
        }
        cout << "\n";
    }
    //cin.close();
    //cout.close();
    return 0;
}

• Subtask 1: 100 / 100