oj.uz

Submission #88623

# Submission time Handle Problem Language Result Execution time Memory
88623 2018-12-07T06:22:54 Z toloraia Weighting stones (IZhO11_stones) C++14
100 / 100
 275 ms 17164 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define ll long long
#define LEFT(a) ((a)<<1)
#define RIGHT(a) (LEFT(a) + 1)
#define MID(a,b) ((a+b)>>1)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
//#define temo

using namespace std;

const int N = 400005;

int n, nn = 1;
int a[N], T1[N], T2[N];
int L[N], R[N];
int pu[N];
void go (int k, int l, int r){
    L[k] = l;
    R[k] = r;
    if (r > n){
        T1[k] = N + 100;
        T2[k] = -N - 100;
    }
    if (l == r)
        return;
    go (LEFT(k), l, (l + r) / 2);
    go (RIGHT(k), (l + r) / 2 + 1, r);
}
void update (int k, int l, int r, int x){
    if (r < L[k] || R[k] < l)
        return;
    if (l <= L[k] && R[k] <= r){
        T1[k] += x;
        T2[k] += x;
        pu[k] += x;
        return;
    }
    T1[LEFT(k)] += pu[k];
    T2[LEFT(k)] += pu[k];
    pu[LEFT(k)] += pu[k];
    T1[RIGHT(k)] += pu[k];
    T2[RIGHT(k)] += pu[k];
    pu[RIGHT(k)] += pu[k];
    pu[k] = 0;
    update (LEFT(k), l, r, x);
    update (RIGHT(k), l, r, x);
    T1[k] = min (T1[LEFT(k)], T1[RIGHT(k)]);
    T2[k] = max (T2[LEFT(k)], T2[RIGHT(k)]);
}

int main()
{
    cin>>n;
    while (nn < n)
        nn *= 2;
    go (1, 1, nn);
    for (int i = 1; i <= n; i++){
        int x, y;
        cin>>x>>y;
        x = n - x + 1;
        y = 3 - 2 * y;
        update (1, x, n, y);
        if (T1[1] >= 0){
            cout<<">\n";
            continue;
        }
        if (T2[1] <= 0){
            cout<<"<\n";
            continue;
        }
        cout<<"?\n";
    }
    return 0;
}

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 3 ms 400 KB Output is correct
4 Correct 2 ms 420 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 5 ms 896 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 26 ms 1520 KB Output is correct
11 Correct 161 ms 4056 KB Output is correct
12 Correct 264 ms 7188 KB Output is correct
13 Correct 266 ms 7968 KB Output is correct
14 Correct 267 ms 8656 KB Output is correct
15 Correct 264 ms 9420 KB Output is correct
16 Correct 266 ms 10164 KB Output is correct
17 Correct 265 ms 10988 KB Output is correct
18 Correct 263 ms 11864 KB Output is correct
19 Correct 275 ms 12552 KB Output is correct
20 Correct 275 ms 13304 KB Output is correct
21 Correct 269 ms 14016 KB Output is correct
22 Correct 269 ms 14748 KB Output is correct
23 Correct 264 ms 15688 KB Output is correct
24 Correct 266 ms 16392 KB Output is correct
25 Correct 266 ms 17164 KB Output is correct