Submission #877519

#	Time	Username	Problem	Language	Result	Execution time	Memory
877519		MDSPro	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	298 ms	136228 KiB

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 / 100