답안 #551328

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
551328 2022-04-20T10:13:21 Z Jarif_Rahman 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
285 ms 190924 KB
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

template<int maxn>
struct sparse_segtree{
    struct node{
        int l, r;
        int ln = -1, rn = -1;
        ll sm, lazy_assign = -1;
        node(){
            sm = 0;
        }
        node(ll x, int _l, int _r){
            l = _l, r = _r;
            sm = x;
        }
    };

    node* v;
    int cnt = 0;

    int new_node(int l, int r){
        v[cnt] = node(0, l, r);
        return cnt++;
    }

    void pushdown(node &nd){
        if(nd.ln == -1)
            nd.ln = new_node(nd.l, (nd.l+nd.r)/2),
            nd.rn = new_node((nd.l+nd.r)/2+1, nd.r);

        if(nd.lazy_assign == -1) return;
        
        v[nd.ln].sm = nd.lazy_assign*(v[nd.ln].r-v[nd.ln].l+1);
        v[nd.ln].lazy_assign = nd.lazy_assign;

        v[nd.rn].sm = nd.lazy_assign*(v[nd.rn].r-v[nd.rn].l+1);
        v[nd.rn].lazy_assign = nd.lazy_assign;

        nd.lazy_assign = -1;
    }

    sparse_segtree(int n){
        v = new node[maxn];
        int k = 1;
        while(k < n) k*=2;
        new_node(0, k-1);
    }

    void assign(node &nd, int l, int r, ll x){
        if(nd.l > r || nd.r < l) return;
        if(nd.l >= l && nd.r <= r){
            nd.lazy_assign = x;
            nd.sm = x*(nd.r-nd.l+1);
            return;
        }
        pushdown(nd);
        assign(v[nd.ln], l, r, x);
        assign(v[nd.rn], l, r, x);
        nd.sm = v[nd.ln].sm+v[nd.rn].sm;
    }
    void assign(int l, int r, ll x){
        assign(v[0], l, r, x);
    }

    ll sum(node &nd, int l, int r){
        if(nd.l > r || nd.r < l) return 0;
        if(nd.l >= l && nd.r <= r) return nd.sm;
        pushdown(nd);
        ll rt = sum(v[nd.ln], l, r) + sum(v[nd.rn], l, r);
        nd.sm = v[nd.ln].sm+v[nd.rn].sm;
        return rt;
    }
    ll sum(int l, int r){
        return sum(v[0], l, r);
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    sparse_segtree<int(60e5)> sp(1e9);

    int c = 0;
    int q; cin >> q;
    while(q--){
        int tt, x, y; cin >> tt >> x >> y;
        x--, y--;
        if(tt == 1){
            c = sp.sum(x+c, y+c);
            cout << c << "\n";
        }
        else{
            sp.assign(x+c, y+c, 1);
        }
    }
}
# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 188108 KB Output is correct
2 Correct 75 ms 188108 KB Output is correct
3 Correct 74 ms 188164 KB Output is correct
4 Correct 84 ms 188236 KB Output is correct
5 Correct 86 ms 188372 KB Output is correct
6 Correct 87 ms 188364 KB Output is correct
7 Correct 86 ms 188296 KB Output is correct
8 Correct 152 ms 189132 KB Output is correct
9 Correct 243 ms 190240 KB Output is correct
10 Correct 244 ms 190264 KB Output is correct
11 Correct 250 ms 190252 KB Output is correct
12 Correct 245 ms 190380 KB Output is correct
13 Correct 230 ms 190640 KB Output is correct
14 Correct 225 ms 190924 KB Output is correct
15 Correct 284 ms 190800 KB Output is correct
16 Correct 284 ms 190848 KB Output is correct
17 Correct 226 ms 190768 KB Output is correct
18 Correct 234 ms 190784 KB Output is correct
19 Correct 285 ms 190924 KB Output is correct
20 Correct 285 ms 190860 KB Output is correct