제출 #1332576

#제출 시각아이디문제언어결과실행 시간메모리
1332576michael12원숭이와 사과 나무 (IZhO12_apple)C++20
0 / 100
27 ms62932 KiB
#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define int long long
#define endl '\n'
using namespace std;
const int maxn = 1e6 + 10;
struct ST {
    int n;
    vector<int> tree;
    vector<int> lazy;
    int ans;  
 
    ST(int size) {
        n = size;
        tree.assign(4 * n, 0);
        lazy.assign(4 * n, 0);
        ans = 0;
    }
    void push(int node, int start, int end){
        if(lazy[node] != 0){
            tree[node] = (end - start + 1) * lazy[node];
            if(start != end){
                lazy[2 * node] = lazy[node];
                lazy[2 * node + 1] = lazy[node];
            }
            lazy[node] = 0;
        }
    }
    void update(int node, int start, int end, int l, int r, int val){
        push(node, start, end);
        if(start > r || end < l) return;
        if(start >= l && end <= r){
            lazy[node] = val;
            push(node, start, end);
            return;
        }
        int mid = (start + end) / 2;
        update(2 * node, start, mid, l, r, val);
        update(2 * node + 1, mid + 1, end, l, r, val);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
    int query(int node, int start, int end, int l, int r){
        push(node, start, end);
        if(start > r || end < l) return 0;
        if(start >= l && end <= r) return tree[node];
        int mid = (start + end) / 2;
        int l1 = query(2 * node, start, mid, l, r);
        int r1 = query(2 * node + 1, mid + 1, end, l, r);
        return l1 + r1;
    }
    int get(int node, int start, int end, int id){
        if(start == end){
            return tree[node];
        }
        else{
            int mid = (start + end) / 2;
            if(mid >= id){
                return get(2 * node, start, mid, id);
            }
            else{
                return get(2 * node + 1, mid + 1, end, id);
            }
        }
    }
 
};
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int k = n;
    vector<array<int, 3>> T;
    int mx = 0;
    ST st(maxn);
    int c = 0;
    while(n--){
        int u, l, r;
        cin >> u;
        cin >> l >> r;
        l--, r--;
        l += c;
        r += c;
        if(l + c <= 0 || l + c > 1e9) return 0;
        if(r + c <= 0 || r + c > 1e9) return 0;
        if(u == 2){
           st.update(1, 0, maxn, l, r, 1);
        }
        else{
            c = st.query(1, 0, maxn, l, r);
            cout << c << endl;

        }
    }

 }
#Verdict Execution timeMemoryGrader output
Fetching results...