Submission #1268354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268354		nikaa123	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	367 ms	205680 KiB

apple

#pragma comment(linker, "/STACK:100000000")
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define eb emplace_back
#define mp make_pair
#define pb push_back
#define pp pop_back
#define endl '\n'
#define ff first
#define ss second
#define stop exit(0)
#define sz(x) (int)x.size()
#define pause system("pause")
#define all(x) (x).begin(), (x).end()
#define deb(x) cout << #x << "-" << x << endl

typedef char chr;
typedef string str;
typedef long long ll;
typedef vector<int> vii;
typedef pair<int, int> pii;

const long long INF = LLONG_MAX;
const int inf = INT_MAX;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};
const double PI = 2 * acos(0.0);

const int N = 1e9;

int m,c,x,y;

struct node{
    int lazy = 0;
    int freq = 0;
    node *left = nullptr;
    node *right=nullptr;
};

node *root = new node;

int merge(int a, int b) {
    return a+b;
}

inline void apply (node *cur, int len, int val) {
    if (val == 1) {
        (cur->lazy)=val;
        (cur->freq)=val*len;
    }
}

void qush(node *cur, int l, int r) {
    // if ((cur->lazy) == 0) return; 
    if ((cur->left) == nullptr) {(cur->left) = new node;}
    if ((cur->right) == nullptr) {(cur->right) = new node;}
    int mid = (l+r)/2;
    apply((cur->left), mid-l+1,(cur->lazy));
    apply((cur->right), r - mid, cur->lazy);
    // (cur->lazy) = 0;   
}

void update(node *cur, int l, int r, int ql, int qr, int val) {
    if (ql > r || qr < l) return;
    if (ql <= l && r <= qr) {
        apply(cur, r-l+1,val);
        return;
    }
    qush(cur,l,r);
    int mid = (l+r)/2;
    update((cur->left), l, mid, ql, qr,val);
    update((cur->right), mid+1,r,ql,qr,val);
    (cur->freq) = merge(((cur->left))->freq,((cur->right))->freq);
}

int getsum(node *cur, int l, int r, int ql, int qr) {
    if (ql > r || qr < l) return 0;
    if (ql <= l && r <= qr) {
        return (cur->freq);
    }
    qush(cur,l,r);
    int mid = (l+r)/2;
    return merge(getsum((cur->left),l,mid,ql,qr),getsum((cur->right),mid+1,r,ql,qr));
}

inline void test_case() {
    
    cin >> m;
    c = 0;
    for (int i = 1; i <= m; i++) {
        int t;
        cin >> t;
        cin >> x >> y;
        if (t == 1) {
            int ans = getsum(root, 0, N, x+c,y+c);
            cout << ans << endl;
            c = ans;
        } else {
            update(root,0,N,x+c,y+c,1);
        }
    }

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        test_case();
    }
    return 0;
}

• Subtask 1: 100 / 100