1028D, C++ (gcc) - rextester

1028D

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define pb push_back
#define F first
#define S second
typedef long long int ll;
#define pii pair<int, int>

const int mod = 1e9 + 7;

struct seg_tree{
    struct node{
        int cnt1,cnt2;
        node() : cnt1(0), cnt2(0){}
        
        void merge(const node& rhs){
            cnt1 += rhs.cnt1;
            cnt2 += rhs.cnt2;
        }
        void clear(){
            cnt1 = cnt2 = 0;
        }
    };
    
    struct lazy{
        int fg, tim;
        lazy() : fg(0), tim(0){}
        
        void merge(const lazy& rhs){
            if(rhs.fg == 0) return;
            fg = rhs.fg;
            //tim = rhs.tim;
        }
    };
    
    node *seg;
    lazy *lzy;
    int n, timer;
    
    seg_tree(int x) : n(x), timer(0){
        seg = new node[4*n];
        lzy = new lazy[4*n];
    }
    
    void update_lazy(int l, int r, int i){
        if(lzy[i].fg == 0) return;
        else if(lzy[i].fg == 1){
            if(l == r) seg[i].cnt1 = 1, seg[i].cnt2 = 0;
            else{
                lzy[i*2+1].merge(lzy[i]), lzy[i*2+2].merge(lzy[i]);
                seg[i].cnt2 = 0, seg[i].cnt1 = r - l + 1;
            }
        }
        else if(lzy[i].fg == 2){
            if(l == r) seg[i].cnt2 = 1, seg[i].cnt1 = 0;
            else{
                lzy[i*2+1].merge(lzy[i]), lzy[i*2+2].merge(lzy[i]);
                seg[i].cnt1 = 0, seg[i].cnt2 = r - l + 1;
            }
        }
        else{                         //for making current node inactive (i.e. already ACCEPTED as sale OR buy)!
            assert(l == r);
            seg[i].cnt1 = seg[i].cnt2 = 0;
        }
        lzy[i].fg = 0;
    }
    
    void update(int x, int y, int fg, int l = 0, int r = -1, int i = 0){
        if(x > y) return;
        if(r == -1) r += n;
        update_lazy(l, r, i);
        if(r < x || l > y) return;
        if(l >= x && r <= y){
            lzy[i].fg = fg;
            return update_lazy(l, r , i);
        }
        int m = (l+r) >> 1;
        update(x, y, fg, l, m, i*2+1);
        update(x, y, fg, m+1, r, i*2+2);
        seg[i].clear(), seg[i].merge(seg[i*2+1]), seg[i].merge(seg[i*2+2]);
    }
    
    void query(int l, int r, int i, int x, int y, node& ans){
        update_lazy(l ,r , i);
        if(r < x || l > y) return;
        if(l >= x && r <= y) return ans.merge(seg[i]);
        int m = (l+r) >> 1;
        query(l, m, i*2+1, x, y, ans), query(m+1, r ,i*2+2, x, y, ans);
        seg[i].clear(), seg[i].merge(seg[i*2+1]), seg[i].merge(seg[i*2+2]);
    }
    
    pii query(int l, int r){
        if(l < 0 || r < 0 || l > r) return mp(0, 0);
        node ans;
        query(0, n-1, 0, l, r, ans);
        return mp(ans.cnt1, ans.cnt2);
    }
};

ll fast_pow(ll a, ll b){
    ll ans = 1;
    while(b > 0){
        if(b&1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b /= 2;
    }
    return ans;
}

vector<pii> q;
vector<int> add;

ll solve(){
    for(auto i : q) cout << "(" << i.F << " " << i.S << ")  "; cout << endl;
    
    ll ans = 1;
    int n = add.size();
    seg_tree s(n);
    int j = (int)q.size() - 1;
    while(j >= 0){
        if(q[j].F == 0) ans = (ans * 2) % mod, j--;        //add state
        else break;
    }
    for(; j >= 0; j--){
        if(q[j].F == 0) continue;
        int ind = q[j].S;
        pii t1 = s.query(0, ind-1);
        pii t2 = s.query(ind+1, n-1);
        cout << j << " : " << "(" << t1.F << " " << t1.S << ") (" << t2.F << " " << t2.S << ")" << endl;
        
        if(t1.S > 0 || t2.F > 0) return 0;
        s.update(0, ind-1, 1);
        s.update(ind+1, n-1, 2);
        
        pii cur = s.query(ind, ind);
        if(cur.F == 0 && cur.S == 0) ans = (ans * 2) % mod;
        s.update(ind, ind, 3);
    }
    return ans;
}

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    vector<pii> v;
    vector< pair<int, pii> > qry;
    for(int j = 0; j < n; j++){
        string s;
        int t;
        cin >> s >> t;
        if(s[1] == 'D')
            v.pb(mp(t, j)), add.pb(t);
        qry.pb(mp((s[1] == 'C'), mp(j, t)));
    }
    sort(v.begin(), v.end());
    map<int, int> m;
    int k = 0;
    for(auto i : v) m[i.F] = k++;
    
    for(int j = 0; j < n; j++)
        q.pb(mp(qry[j].F, m[qry[j].S.S]));
    
    cout << solve() << endl;
    return 0;  
}


run \| edit \| history \| help	0