Submission #877519

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
877519	2023-11-23T09:34:59 Z	MDSPro	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	298 ms	136228 KB

apple

// MDSPro
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

const ld PI = 3.141592653589793;
const int MOD = 1e9+7;
const int INF = 1e9;
const ll INFLL = 4e18;
const double EPS = 1e-9;
const int MAXN = 1000*1007;

const int N = 1 << 30;

struct Node {
    int sum, apply;
    Node *left, *right;
    Node(): sum(0), apply(0), left(NULL), right(NULL) {}
};

void impact(Node *& x, int v, int len) {
    if(x == NULL) x = new Node();
    
    x->apply = v;
    x->sum = v * len;
}

void split(Node *& x, int len) {
    if(len == 1) return;
    len >>= 1;
    if(x->apply != -1) {
        impact(x->left, x->apply, len);
        impact(x->right, x->apply, len);
        x->apply = -1;
    }
}

void merge(Node *& x) {
    x->sum = x->left->sum + x->right->sum;
}

void update(Node *& cur, int l, int r, int ql, int qr, int val) {
    if(qr <= l || r <= ql) return;
    if(ql <= l && r <= qr) {
        impact(cur, val, r - l);
        return;
    }

    split(cur, r - l);
    
    int mid = (l + r) >> 1;
    update(cur-> left, l, mid, ql, qr, val);
    update(cur->right, mid, r, ql, qr, val);
    
    merge(cur);
}

void update(Node *& root, int ql, int qr, int val) {
    update(root, 0, N, ql, qr, val);
}

int sum(Node *& cur, int l, int r, int ql, int qr) {
    if(qr <= l || r <= ql) return 0;
    if(ql <= l && r <= qr) {
        return cur->sum;
    }

    split(cur, r - l);
    
    int mid = (l + r) >> 1;
    return sum(cur-> left, l, mid, ql, qr) + sum(cur->right, mid, r, ql, qr);
}

int sum(Node *& root, int ql, int qr) {
    return sum(root, 0, N, ql, qr);
}

void solve(int NT){
    Node *root = new Node();

    int C = 0;
    int q; cin >> q;
    while(q--) {
        int d, x, y; cin >> d >> x >> y; x--;
        x += C; y += C;
        if(d == 1) {
            C = sum(root, x, y);
            cout << C << '\n';
        } else {
            update(root, x, y, 1);
        }
    }
}

// #define TESTCASES
int main() {
    cin.tie(0)->sync_with_stdio(0);

    int t = 1;
    #ifdef TESTCASES
        cin >> t;
    #endif
    
    for(int i = 1; i <= t; ++i){
        solve(i);
        cout << "\n";
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	0 ms	604 KB	Output is correct
4	Correct	13 ms	3420 KB	Output is correct
5	Correct	11 ms	3932 KB	Output is correct
6	Correct	11 ms	3884 KB	Output is correct
7	Correct	11 ms	4168 KB	Output is correct
8	Correct	83 ms	29012 KB	Output is correct
9	Correct	179 ms	51984 KB	Output is correct
10	Correct	166 ms	55440 KB	Output is correct
11	Correct	175 ms	59476 KB	Output is correct
12	Correct	184 ms	61332 KB	Output is correct
13	Correct	187 ms	72788 KB	Output is correct
14	Correct	179 ms	73192 KB	Output is correct
15	Correct	274 ms	132108 KB	Output is correct
16	Correct	286 ms	133184 KB	Output is correct
17	Correct	183 ms	75892 KB	Output is correct
18	Correct	185 ms	75708 KB	Output is correct
19	Correct	298 ms	136188 KB	Output is correct
20	Correct	288 ms	136228 KB	Output is correct