답안 #321088

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
321088 2020-11-10T22:31:16 Z thatprogrammer 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
555 ms 207844 KB
#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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 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