Submission #335074

#	Time	Username	Problem	Language	Result	Execution time	Memory
335074		limabeans	Weighting stones (IZhO11_stones)	C++17	100 / 100	99 ms	13548 KiB

stones

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll inf = 1e18;



struct minsegtree {
    vector<ll> t,o;
    int n;
    void init(int _n) {
	n=_n;
	t.resize(4*n);
	o.resize(4*n);
    }

    void push(int v) {
	t[2*v]+=o[v];
	t[2*v+1]+=o[v];
	o[2*v]+=o[v];
	o[2*v+1]+=o[v];
	o[v]=0;
    }

    ll qry(int v, int tl, int tr, int l, int r) {
	if (l>tr||r<tl) return -inf;
	if (l<=tl&&tr<=r) {
	    return t[v];
	} else {
	    push(v);
	    int tm=(tl+tr)/2;
	    return min(qry(2*v,tl,tm,l,r),qry(2*v+1,tm+1,tr,l,r));
	}
    }

    void rangeAdd(int v, int tl, int tr, int l, int r, ll dx) {
	if (l>r) return;
	if (l>tr||r<tl) return;
	if (l<=tl&&tr<=r) {
	    t[v]+=dx;
	    o[v]+=dx;
	} else {
	    push(v);
	    int tm=(tl+tr)/2;
	    rangeAdd(2*v,tl,tm,l,r,dx);
	    rangeAdd(2*v+1,tm+1,tr,l,r,dx);
	    t[v]=min(t[2*v],t[2*v+1]);
	}
    }
};

struct maxsegtree {
    int n;
    vector<ll> t,o;
    void init(int _n) {
	n=_n;
	t.resize(4*n);
	o.resize(4*n);
    }

    void push(int v) {
	t[2*v]+=o[v];
	t[2*v+1]+=o[v];
	o[2*v]+=o[v];
	o[2*v+1]+=o[v];
	o[v]=0;
    }

    ll qry(int v, int tl, int tr, int l, int r) {
	if (l>tr||r<tl) return -inf;
	if (l<=tl&&tr<=r) {
	    return t[v];
	} else {
	    push(v);
	    int tm=(tl+tr)/2;
	    return max(qry(2*v,tl,tm,l,r),qry(2*v+1,tm+1,tr,l,r));
	}
    }

    void rangeAdd(int v, int tl, int tr, int l, int r, ll dx) {
	if (l>r) return;
	if (l>tr||r<tl) return;
	if (l<=tl&&tr<=r) {
	    t[v]+=dx;
	    o[v]+=dx;
	} else {
	    push(v);
	    int tm=(tl+tr)/2;
	    rangeAdd(2*v,tl,tm,l,r,dx);
	    rangeAdd(2*v+1,tm+1,tr,l,r,dx);
	    t[v]=max(t[2*v],t[2*v+1]);
	}
    }
};


minsegtree tmin;
maxsegtree tmax;

int n;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n;
    tmin.init(n);
    tmax.init(n);
    for (int i=1; i<=n; i++) {
	int val,id;
	cin>>val>>id;
	if (id==1) {
	    tmin.rangeAdd(1,1,n,1,val,1);
	    tmax.rangeAdd(1,1,n,1,val,1);
	} else {
	    tmin.rangeAdd(1,1,n,1,val,-1);
	    tmax.rangeAdd(1,1,n,1,val,-1);
	}

	int lo = tmin.qry(1,1,n,1,n);
	int hi = tmax.qry(1,1,n,1,n);

	assert(!(lo==0 && hi==0));

	if (hi>0) {
	    if (lo>=0) cout<<">\n"; else cout<<"?\n";
	} else {
	    cout<<"<\n";
	}
    }
    
    
    return 0;
}

• Subtask 1: 100 / 100