Submission #1248252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248252		Minbaev	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	266 ms	137324 KiB

apple

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define pb      push_back
#define all(x)  x.begin(),x.end()
#define ar      array
#define mrand(a, b)   uniform_int_distribution<int>(a, b)(rng)

template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}

template<class T> using ste = tree<T, null_type, less_equal<T>,
rb_tree_tag, tree_order_statistics_node_update>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

namespace FAST {
    template<typename T, typename F>
    istream &operator>>(istream &cin, pair<T, F> &p) {
        cin >> p.first >> p.second;
        return cin;
    }

    template<typename T, typename F>
    ostream &operator<<(ostream &cout, pair<T, F> &p) {
        cout << p.first << ' ' << p.second;
        return cout;
    }

    template<typename T>
    istream &operator>>(istream &cin, vector<T> &a) {
    for (T &i: a) cin >> i;
        return cin;
    }

    template<typename T>
    ostream &operator<<(ostream &cout, vector<T> &a) {
          for (T i: a) cout << i << ' ';
        return cout;
    }

    template<typename T>
    istream &operator>>(istream &cin, deque<T> &a) {
        for (T &i: a) cin >> i;
        return cin;
    }

    template<typename T>
    ostream &operator<<(ostream &cout, deque<T> &a) {
        for (T i: a) cout << i << ' ';
        return cout;
    }
}
using namespace FAST;

const int inf = 1e17 + 7;
const int mod = 1e9 + 7;
const int N = 3e5 + 5;
const int md = 998244353;

int binpow(int a, int b, int m){
    if(b == 0)return 1;
    if(b % 2 == 0){
        int c = binpow(a,b/2,m);
        return (c*c)%m;
    }
    return (binpow(a,b-1,m)*a)%m;
}

int divi(int a, int b, int m){
    return (a*(binpow(b,m-2, m)))%m;
}

struct Bit {
    vector<int> b, b2;
    int n;

    Bit(int n) {
        this->n = n + 1;
        b.assign(n + 1, 0);
        b2.assign(n+1, 0);
    }

    void add(vector<int>&b, int idx, int x){
        while(idx <= n){
            b[idx] += x;
            idx += idx & -idx;
        }
    }

    void update(int l, int r, int x){
        add(b, l, x);
        add(b, r+1, -x);
        add(b2, l, x*(l-1));
        add(b2, r+1, -x*r);
    }

    int sum(vector<int>&b, int idx){
        int res = 0;
        while(idx > 0){
            res += b[idx];
            idx -= idx & -idx;
        }
        return res;
    }

    int pref(int idx){
        return sum(b, idx) * idx - sum(b2, idx);
    }

    int get(int l, int r){                  
        return pref(r) - pref(l-1);
    }
};

int n,m,k;

struct node{
    int sum, lz;
    node *lx, *rx;

    node(){
        sum = 0;
        lz = 0;
        lx = nullptr;
        rx = nullptr;
    }
};

node *root = new node();

void push(node *a, int len){
    if(a->lz == 0)return;
    if(a->lx != nullptr)a->lx->lz = 1;
    if(a->rx != nullptr)a->rx->lz = 1;
    a->sum = len;
}

void update(node *a, int tl, int tr, int l, int r){
    if(r < tl || tr < l)return;
    
    push(a, tr - tl + 1);

    if(l <= tl && tr <= r){
        a->lz = 1;
        push(a, tr - tl + 1);
        return;
    }

    int tm = (tl + tr) / 2;

    if(a->lx == nullptr)a->lx = new node();
    if(a->rx == nullptr)a->rx = new node();
    push(a, tr - tl + 1);

    update(a->lx, tl, tm, l, r);
    update(a->rx, tm+1, tr, l, r);

    push(a->lx, tm - tl + 1);
    push(a->rx, tr - tm - 1 + 1);

    a->sum = a->lx->sum + a->rx->sum;
    // cout << tl << " " << tr << " " << l << " " << r << " " << a->sum << "\n";
}

int get(node *a, int tl, int tr, int l, int r){
    if(r < tl || tr < l)return 0;

    push(a, tr - tl + 1);

    if(l <= tl && tr <= r){
        return a->sum;
    }

    if(a->lx == nullptr)a->lx = new node();
    if(a->rx == nullptr)a->rx = new node();
    push(a, tr - tl + 1);

    int tm = (tl + tr) / 2;

    int res = get(a->lx, tl, tm, l, r);
    res += get(a->rx, tm+1, tr, l, r);

    push(a->lx, tm - tl + 1);
    push(a->rx, tr - tm - 1 + 1);

    a->sum = a->lx->sum + a->rx->sum;

    return res;
}

void solve(){

    cin >> n;

    vector<int>v;

    int cnt = 0;
    for(int i = 1;i<=n;i++){
        int type, l, r;
        cin >> type >> l >> r;
        if(type == 1){
            cnt = get(root, 1, 1e9, l + cnt, r + cnt);
            cout << cnt << "\n";
        }
        else{
            update(root, 1, 1e9, l + cnt, r + cnt);
        }
    }

}
/*

*/
 signed main()
{
//  freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);
    ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    int tt=1; //cin >> tt;
    while(tt--)solve();

}

Compilation message (stderr)

apple.cpp:62:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+17' to '2147483647' [-Woverflow]
   62 | const int inf = 1e17 + 7;
      |                 ~~~~~^~~

• Subtask 1: 100 / 100