제출 #481010

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
481010		FatihSolak	Weighting stones (IZhO11_stones)	C++17	100 / 100	261 ms	7620 KiB

stones

#include <bits/stdc++.h>
using namespace std;
struct SegTree{
    vector<int> t,lazy;
    SegTree(int size){
        t.assign(4*size+5,1e9);
        lazy.assign(4*size+5,0);
    }
    void push(int v){
        t[v*2] += lazy[v];
        t[v*2+1] += lazy[v];
        lazy[v*2] += lazy[v];
        lazy[v*2+1] += lazy[v];
        lazy[v] = 0;
    }
    void upd(int v,int tl,int tr,int l,int r,int val){
        if(r  < tl || tr < l)return;
        if(l <= tl && tr <= r){
            t[v] += val;
            lazy[v] += val;
            return;
        }
        push(v);
        int tm = (tl + tr)/2;
        upd(v*2,tl,tm,l,r,val);
        upd(v*2+1,tm+1,tr,l,r,val);
        t[v] = min(t[v*2],t[v*2+1]);
    }
    int get(int v,int tl,int tr,int l,int r){
        if(r < tl || tr < l)return 1e9;
        if(l <= tl && tr <= r)return t[v];
        push(v);
        int tm = (tl + tr)/2;
        return min(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
    }
};
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifdef Local
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int n;
    cin >> n;
    SegTree t1(n);
    SegTree t2(n);
    for(int i=1;i<=n;i++){
        int r,s;
        cin >> r >> s;
        if(s == 1){
            t1.upd(1,1,n,1,r-1,-1);
            t1.upd(1,1,n,r,r,-(int)1e9);
            t2.upd(1,1,n,1,r,1);
        }
        if(s == 2){
            t2.upd(1,1,n,1,r-1,-1);
            t2.upd(1,1,n,r,r,-(int)1e9);
            t1.upd(1,1,n,1,r,1);
        }
        if(t1.get(1,1,n,1,n) > 0){
            cout << '<';
        }
        else if(t2.get(1,1,n,1,n) > 0){
            cout << '>';    
        }
        else cout << '?';
        cout << endl;
    }
}

• Subtask 1: 100 / 100