Submission #321088

#	Time	Username	Problem	Language	Result	Execution time	Memory
321088		thatprogrammer	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	555 ms	207844 KiB

apple

#include <bits/stdc++.h>
using namespace std;
// source: thatprogrammer, modified off normal segtree
// version supports add on range, assign on range
class segtree {
public:
    struct node {
        int val;
        int lazyVal;
        node* c[2];
        bool identity;
        node() {
            val = lazyVal = 0;
            c[0] = c[1] = nullptr;
            identity = false;
        }
        
        void apply(int l, int r, int v) {
            //make sure to update lazyVal here
            val = (r - l + 1) * v;
            lazyVal = v;
        }
    };
    
    node unite(const node &a, const node &b) const {
        // combines two nodes
        if(a.identity) return b;
        if(b.identity) return a;
        node res;
        res.val = a.val + b.val;
        return res;
    }

    inline void push(node* x, int l, int r) {
        // return; if no lazy prop
        // make sure to reset lazyValue here, lazy is added in apply function
        int mid = (l + r) >> 1;
        if(x->lazyVal == 0) return;
        if (l != r) {
            if (!x->c[0]) x->c[0] = new node(); 
            x->c[0]->apply(l, mid, x->lazyVal);

            if (!x->c[1]) x->c[1] = new node();
            x->c[1]->apply(mid + 1, r, x->lazyVal);
        }
        x->lazyVal = 0;
    }

    inline void pull(node* x) { 
        node *temp[2] = {x->c[0], x->c[1]};
        node res;
        res.identity = true;
        if (x->c[0]) res = unite(res, *x->c[0]); 
        if (x->c[1]) res = unite(res, *x->c[1]); 
        if(!res.identity)
            *x = res; 
        x->c[0] = temp[0];
        x->c[1] = temp[1];
    }

    int n;
    node root;
    segtree(int _n) : n(_n) {
        assert(n > 0);
    }
    node get(int ll, int rr) {
        assert(0 <= ll && ll <= rr && rr <= n - 1);
        return get(&root, 0, n - 1, ll, rr);
    }
    template <typename... M>
    void modify(int ll, int rr, const M &... v) {
        assert(0 <= ll && ll <= rr && rr <= n - 1);
        modify(&root, 0, n - 1, ll, rr, v...);
    }

private:
    node get(node* x, int l, int r, int ll, int rr) {
        node res{};
        res.identity = true;
        if (ll > r || l > rr) return res;
        if (ll <= l && r <= rr) return *x;
        int mid = (l + r) >> 1;
        push(x, l, r);

        if (x->c[0]) res = unite(res, get(x->c[0], l, mid, ll, rr)); 

        if (x->c[1]) res = unite(res, get(x->c[1], mid + 1, r, ll, rr)); 
        pull(x);
        return res;
    }
    template <typename... M>
    void modify(node* x, int l, int r, int ll, int rr, const M &... v) {
        if (ll > r || l > rr) return;
        if (ll <= l && r <= rr) {
            x->apply(l, r, v...);
            return;
        }
        int mid = (l + r) >> 1;
        push(x, l, r);

        if (!x->c[0]) x->c[0] = new node(); 
        modify(x->c[0], l, mid, ll, rr, v...);

        if (!x->c[1]) x->c[1] = new node();
        modify(x->c[1], mid + 1, r, ll, rr, v...);
        pull(x);
    }
};
void dfs(segtree::node *x, int l, int r){
    if(!x) return;
    cout<<x->val<<" "<<l<<" "<<r<<" "<<x->identity<<endl;
    dfs(x->c[0], l, (l+r)>>1);
    dfs(x->c[1], ((l+r)>>1)+1, r);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("input.in", "r")) {
        freopen("input.in", "r", stdin);
        freopen("output.out", "w", stdout);
    }
    segtree st(1e9 + 1);
    int m;
    cin>>m;
    int c = 0;
    while(m--){
        int t, x, y;
        cin>>t>>x>>y;
        x+=c; y+=c;
        // cout<<"s\n";
        // dfs(&st.root, 0, 10);
        // cout<<endl;
        if(t-1) st.modify(x, y, 1);
        else {
            c=st.get(x,y).val;
            cout<<c<<'\n';
        }
        
    }
    
}

Compilation message (stderr)

apple.cpp: In function 'int main()':
apple.cpp:120:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  120 |         freopen("input.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:121:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  121 |         freopen("output.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100