Submission #474642

#	Time	Username	Problem	Language	Result	Execution time	Memory
474642		Marslai24	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	288 ms	262148 KiB

apple

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()

const int INF = 1e18, MOD = 1e9 + 7, N = 1e7 + 1;

void setIO(string name = ""){
    ios::sync_with_stdio(false);
    cin.tie(0);
}

template<class T> struct seg{
    T val, lz;
    seg<T> *lc, *rc;
    int sz;
    seg(int n) : sz(n){val = lz = 0; lc = rc = NULL;}
    void pull(){
        val = (lc ? lc -> val : 0) + (rc ? rc -> val : 0);
    }
    void push(int l, int r){
        int m = l + r >> 1;
        if(!lc)lc = new seg(m - l);
        if(!rc)rc = new seg(r - m);
        if(!lz)return;
        lc -> val = lc -> sz;
        lc -> lz = 1;
        rc -> val = rc -> sz;
        rc -> lz = 1;
        lz = 0;
    }
    void add(int a, int b, T v, int l, int r){
        if(a <= l && b >= r){
            val = r - l, lz = 1;
            return;
        }
        push(l, r);
        int m = l + r >> 1;
        if(a < m){
            lc -> add(a, b, v, l, m);
        }
        if(b > m){
            rc -> add(a, b, v, m, r);
        }
        pull();
    }
    T query(int a, int b, int l, int r){
        if(a <= l && b >= r)return val;
        push(l, r);
        int m = l + r >> 1, ans = 0;
        if(a < m)ans += lc -> query(a, b, l, m);
        if(b > m)ans += rc -> query(a, b, m, r);
        return ans;
    }
    void add(int a, int b, T v){add(a, b, v, 0, sz);}
    T query(int a, int b){return query(a, b, 0, sz);}
};

signed main(){
    setIO();
    seg<int> rt(N);
    int n, c = 0;
    cin >> n;
    while(n--){
        int t, l, r;
        cin >> t >> l >> r;
        l = l - 1 + c, r = r + c;
        if(t == 1){
            c = rt.query(l, r);
            cout << c << '\n';
        }else{
            rt.add(l, r, 1);
        }
    }
}

Compilation message (stderr)

apple.cpp: In instantiation of 'T seg<T>::query(long long int, long long int, long long int, long long int) [with T = long long int]':
apple.cpp:56:39:   required from 'T seg<T>::query(long long int, long long int) [with T = long long int]'
apple.cpp:69:30:   required from here
apple.cpp:50:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |         int m = l + r >> 1, ans = 0;
      |                 ~~^~~
apple.cpp: In instantiation of 'void seg<T>::add(long long int, long long int, T, long long int, long long int) [with T = long long int]':
apple.cpp:55:36:   required from 'void seg<T>::add(long long int, long long int, T) [with T = long long int]'
apple.cpp:72:27:   required from here
apple.cpp:38:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         int m = l + r >> 1;
      |                 ~~^~~
apple.cpp: In instantiation of 'void seg<T>::push(long long int, long long int) [with T = long long int]':
apple.cpp:49:9:   required from 'T seg<T>::query(long long int, long long int, long long int, long long int) [with T = long long int]'
apple.cpp:56:39:   required from 'T seg<T>::query(long long int, long long int) [with T = long long int]'
apple.cpp:69:30:   required from here
apple.cpp:22:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         int m = l + r >> 1;
      |                 ~~^~~

• Subtask 1: 0 / 100