Submission #321088

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
321088	2020-11-10T22:31:16 Z	thatprogrammer	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	555 ms	207844 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	21 ms	5120 KB	Output is correct
5	Correct	25 ms	6116 KB	Output is correct
6	Correct	24 ms	5988 KB	Output is correct
7	Correct	25 ms	6124 KB	Output is correct
8	Correct	177 ms	44620 KB	Output is correct
9	Correct	357 ms	77668 KB	Output is correct
10	Correct	367 ms	85476 KB	Output is correct
11	Correct	389 ms	91876 KB	Output is correct
12	Correct	391 ms	94692 KB	Output is correct
13	Correct	368 ms	110052 KB	Output is correct
14	Correct	371 ms	111076 KB	Output is correct
15	Correct	546 ms	201956 KB	Output is correct
16	Correct	555 ms	203276 KB	Output is correct
17	Correct	373 ms	114840 KB	Output is correct
18	Correct	374 ms	114916 KB	Output is correct
19	Correct	553 ms	207844 KB	Output is correct
20	Correct	555 ms	207844 KB	Output is correct