Submission #51985

#	Time	Username	Problem	Language	Result	Execution time	Memory
51985		FLDutchman	Weighting stones (IZhO11_stones)	C++14	100 / 100	291 ms	21572 KiB

stones

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

#define int long long
#define FOR(i, l, r) for(int i = l; i < r; i++)
#define snd second
#define fst first
#define pb push_back

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

vi tmin, tmax, lazy;
int N;

void update(int l, int r, int v, int lb, int rb, int n = 1){
    //cout << lb << " " << rb << " " << n << endl;
    if(l <= lb and rb <= r){
        lazy[n] += v; tmin[n] += v; tmax[n] += v;
        return;
    }

    int mb = (lb+rb)/2;
    if(lazy[n] != 0){
        update(lb, rb, lazy[n], lb, mb, n<<1);
        update(lb, rb, lazy[n], mb, rb, n<<1|1);
        lazy[n] = 0;
    }

    if(l < mb) update(l, r, v, lb, mb, n<<1);
    if(r > mb) update(l, r, v, mb, rb, n<<1|1);
    tmin[n] = min(tmin[2*n], tmin[2*n+1]);
    tmax[n] = max(tmax[2*n], tmax[2*n+1]);
}

signed main(){
    cin >> N;
    //N = 100; 
    tmin.assign(4*N+5, 0); 
    tmax.assign(4*N+5, 0); 
    lazy.assign(4*N+5, 0);
    /*update(0, 10, 2, 0, N);
    update(2, 20, -1, 0, N);
    update(0, 10, 2, 0, N);
    cout << tmin[1] << endl;
    cout << tmax[1] << endl;*/
    FOR(i, 0, N){
        int R, S;
        cin >> R >> S;
        update(0, R, 2*S-3, 0, N);
        //cout << tmin[1] << " " << tmax[1] << endl;
        if(tmin[1] <= 0 and tmax[1] <= 0) cout << ">" << endl;
        else if(tmin[1] >= 0 and tmax[1] >= 0) cout << "<" << endl;
        else cout << "?" << endl;
    }

}

• Subtask 1: 100 / 100