Submission #878983

#	Time	Username	Problem	Language	Result	Execution time	Memory
878983		MDSPro	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	179 ms	104020 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 N = 1 << 30;

const int MAXN = 2e8; // 200 MB
static char buf[MAXN];
void* operator new(size_t s) {
	static size_t i = sizeof buf;
	assert(s < i);
	return (void*)&buf[i -= s];
}
void operator delete(void*) {}
 
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