Submission #88676

#	Time	Username	Problem	Language	Result	Execution time	Memory
88676		turbat	Weighting stones (IZhO11_stones)	C++14	100 / 100	250 ms	8548 KiB

stones

#include <bits/stdc++.h>
using namespace std;

int n, ss, cnt[2][400005], r, tree[2][400005];
void update(int node, int L, int R, int x){
    if (x < L || x > R) return;
    if (L == x && R == x){
        cnt[ss - 1][node]++;
        tree[2 - ss][node]++;
        return;
    }
    int mid = (L + R)/2;
    update(node * 2, L, mid, x);
    update(node * 2 + 1, mid + 1, R, x);    
    int k = cnt[0][node * 2 + 1] - cnt[1][node * 2];
    if (k > 0) cnt[0][node] = k + cnt[0][node * 2], cnt[1][node] = cnt[1][node * 2 + 1];
    else cnt[0][node] = cnt[0][node * 2], cnt[1][node] = cnt[1][node * 2 + 1] - k;
    k = tree[0][node * 2 + 1] - tree[1][node * 2];
    if (k > 0) tree[0][node] = k + tree[0][node * 2], tree[1][node] = tree[1][node * 2 + 1];
    else tree[0][node] = tree[0][node * 2], tree[1][node] = tree[1][node * 2 + 1] - k;
}

int main (){
    cin >> n;
    int m = n;
    while (m--){
        cin >> r>> ss;
        update(1, 1, n, r);
        if (cnt[1][1] == 0) cout << ">\n";
        else if (tree[1][1] == 0) cout <<"<\n";
        else cout <<"?\n";
    }
}

• Subtask 1: 100 / 100