oj.uz

Submission #88676

# Submission time Handle Problem Language Result Execution time Memory
88676 2018-12-07T11:57:17 Z turbat Weighting stones (IZhO11_stones) C++14
100 / 100
 250 ms 8548 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 3 ms 688 KB Output is correct
6 Correct 3 ms 688 KB Output is correct
7 Correct 4 ms 688 KB Output is correct
8 Correct 5 ms 688 KB Output is correct
9 Correct 5 ms 688 KB Output is correct
10 Correct 24 ms 1120 KB Output is correct
11 Correct 150 ms 3552 KB Output is correct
12 Correct 242 ms 6148 KB Output is correct
13 Correct 244 ms 6908 KB Output is correct
14 Correct 247 ms 7804 KB Output is correct
15 Correct 244 ms 8432 KB Output is correct
16 Correct 241 ms 8484 KB Output is correct
17 Correct 245 ms 8484 KB Output is correct
18 Correct 246 ms 8548 KB Output is correct
19 Correct 243 ms 8548 KB Output is correct
20 Correct 245 ms 8548 KB Output is correct
21 Correct 247 ms 8548 KB Output is correct
22 Correct 248 ms 8548 KB Output is correct
23 Correct 248 ms 8548 KB Output is correct
24 Correct 250 ms 8548 KB Output is correct
25 Correct 247 ms 8548 KB Output is correct