Submission #336573

#	Time	Username	Problem	Language	Result	Execution time	Memory
336573		jovan_b	Weighting stones (IZhO11_stones)	C++17	100 / 100	73 ms	6636 KiB

stones

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

typedef long long ll;
typedef long double ld;

#define pb push_back

struct Segment{
    int val[1000005], open[1000005], closed[1000005];
    Segment(){

    }
    void mrg(int node){
        int g = min(open[node*2], closed[node*2+1]);
        open[node] = open[node*2] + open[node*2+1]- g;
        closed[node] = closed[node*2] + closed[node*2+1] - g;
        val[node] = val[node*2] + val[node*2+1] + g;
    }
    void upd(int node, int l, int r, int x, int g){
        if(l == r){
            if(g == -1) open[node] = 1;
            else closed[node] = 1;
            return;
        }
        int mid = (l+r)/2;
        if(x <= mid) upd(node*2, l, mid, x, g);
        else upd(node*2+1, mid+1, r, x, g);
        mrg(node);
    }
};

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n;
    cin >> n;
    Segment *prvi = new Segment();
    Segment *drugi = new Segment();
    int prvih = 0, drugih = 0;
    for(int i=1; i<=n; i++){
        int a, b;
        cin >> a >> b;
        if(b == 1){
            prvih++;
            prvi->upd(1, 1, n, a, -1);
            drugi->upd(1, 1, n, a, 1);
        }
        else{
            drugih++;
            prvi->upd(1, 1, n, a, 1);
            drugi->upd(1, 1, n, a, -1);
        }
        if(prvi->val[1] == prvih) cout << "<\n";
        else if(drugi->val[1] == drugih) cout << ">\n";
        else cout << "?\n";
    }
    return 0;
}

• Subtask 1: 100 / 100