Submission #1111130

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1111130	2024-11-11T15:01:37 Z	Icelast	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	404 ms	202124 KB

apple

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct ImplicitSegmentTree{
    struct Node{
        ll sum = 0, s = -1;
        int ln = 0, rn = 0;
    };
    ll n, N;
    vector<Node> T;
    int cnt;
    ImplicitSegmentTree(ll n): n(n){
        N = n;
        T.push_back(Node());
        T.push_back(Node());
        cnt = 1;
    };
    int new_node(){
        T.push_back(Node());
        cnt++;
        return cnt;
    }
    void down(int node, ll low, ll high){
        if(low < high){
            if(T[node].ln == 0){
                int x = new_node();
                T[node].ln = x;
            }
            if(T[node].s != -1)
                T[T[node].ln].s = T[node].s;
            if(T[node].rn == 0){
                int x = new_node();
                T[node].rn = x;
            }
            if(T[node].s != -1)
                T[T[node].rn].s = T[node].s;
        }
        ll len = high-low+1;
        if(T[node].s != -1){
            T[node].sum = T[node].s*len;
        }
        T[node].s = -1;
    }
    void apply(int i, int x){
        auto apply = [&](auto apply, int node, ll low, ll high, int i, int x) -> void{
            down(node, low, high);
            if(low == high){
                T[node].s = x;
                down(node, low, high);
                return;
            }
            ll mid = (low+high)/2;
            if(i <= mid){
                if(T[node].ln == 0){
                    int x = new_node();
                    T[node].ln = x;
                }
                apply(apply, T[node].ln, low, mid, i, x);
            }else{
                if(T[node].rn == 0){
                    int x = new_node();
                    T[node].rn = x;
                }
                apply(apply, T[node].rn, mid+1, high, i, x);
            }
            T[node].sum = T[T[node].ln].sum + T[T[node].rn].sum;
        };
        apply(apply, 1, 1, N, i, x);
    }
    void rangeApply(ll l, ll r, int x){
        auto rangeApply = [&](auto self, int node, ll low, ll high, ll l, ll r, int x) -> void{
            down(node, low, high);
            if(low > r || l > high) return;
            if(low >= l && r >= high){
                T[node].s = x;
                down(node, low, high);
                return;
            }
            ll mid = (low+high)/2;
            if(T[node].ln == 0){
                int x = new_node();
                T[node].ln = x;
            }
            self(self, T[node].ln, low, mid, l, r, x);
            if(T[node].rn == 0){
                int x = new_node();
                T[node].rn = x;
            }
            self(self, T[node].rn, mid+1, high, l, r, x);
            T[node].sum = T[T[node].ln].sum + T[T[node].rn].sum;
        };
        rangeApply(rangeApply, 1, 1, N, l, r, x);
    }
    ll get(ll l, ll r){
       auto get = [&](auto self, int node, ll low, ll high, ll l, ll r) -> ll{
            down(node, low, high);
            if(low > r || l > high) return 0;
            if(low >= l && r >= high){
                return T[node].sum;
            }
            ll mid = (low+high)/2;
            if(T[node].ln == 0){
                int x = new_node();
                T[node].ln = x;
            }
            if(T[node].rn == 0){
                int x = new_node();
                T[node].rn = x;
            }
            ll res = self(self, T[node].ln, low, mid, l, r) + self(self, T[node].rn, mid+1, high, l, r);
            T[node].sum = T[T[node].ln].sum + T[T[node].rn].sum;
            return res;
        };
        return get(get, 1, 1, N, l, r);
    }
};
void solve(){
    int q;
    cin >> q;
    ImplicitSegmentTree T(1e9);
    ll C = 0;
    for(int i = 1; i <= q; i++){
        int t, l, r;
        cin >> t >> l >> r;
        l+=C;
        r+=C;
        if(t == 1){
            C = T.get(l, r);
            cout << C << "\n";
        }else{
            T.rangeApply(l, r, 1);
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	16 ms	7892 KB	Output is correct
5	Correct	20 ms	7884 KB	Output is correct
6	Correct	21 ms	7872 KB	Output is correct
7	Correct	19 ms	7872 KB	Output is correct
8	Correct	114 ms	52360 KB	Output is correct
9	Correct	228 ms	102548 KB	Output is correct
10	Correct	239 ms	102292 KB	Output is correct
11	Correct	247 ms	102292 KB	Output is correct
12	Correct	237 ms	102296 KB	Output is correct
13	Correct	302 ms	202124 KB	Output is correct
14	Correct	307 ms	200076 KB	Output is correct
15	Correct	398 ms	198904 KB	Output is correct
16	Correct	383 ms	201036 KB	Output is correct
17	Correct	309 ms	199932 KB	Output is correct
18	Correct	325 ms	199932 KB	Output is correct
19	Correct	404 ms	200952 KB	Output is correct
20	Correct	401 ms	198712 KB	Output is correct