Submission #88623

#	Time	Username	Problem	Language	Result	Execution time	Memory
88623		toloraia	Weighting stones (IZhO11_stones)	C++14	100 / 100	275 ms	17164 KiB

stones

#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 / 100