Submission #878984

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
878984	2023-11-26T02:13:51 Z	MDSPro	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	160 ms	102480 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 N = 1 << 30;

const int MAXN = 4e8; // 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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	8 ms	3732 KB	Output is correct
5	Correct	8 ms	3676 KB	Output is correct
6	Correct	8 ms	3708 KB	Output is correct
7	Correct	8 ms	3576 KB	Output is correct
8	Correct	56 ms	22236 KB	Output is correct
9	Correct	124 ms	39084 KB	Output is correct
10	Correct	117 ms	40788 KB	Output is correct
11	Correct	119 ms	45056 KB	Output is correct
12	Correct	121 ms	44880 KB	Output is correct
13	Correct	122 ms	53328 KB	Output is correct
14	Correct	119 ms	55444 KB	Output is correct
15	Correct	160 ms	98384 KB	Output is correct
16	Correct	156 ms	98384 KB	Output is correct
17	Correct	115 ms	57412 KB	Output is correct
18	Correct	110 ms	57420 KB	Output is correct
19	Correct	156 ms	102428 KB	Output is correct
20	Correct	157 ms	102480 KB	Output is correct