Submission #878983

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
878983	2023-11-26T02:13:12 Z	MDSPro	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	179 ms	104020 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 = 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.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	7 ms	2908 KB	Output is correct
5	Correct	8 ms	5196 KB	Output is correct
6	Correct	8 ms	4952 KB	Output is correct
7	Correct	8 ms	4956 KB	Output is correct
8	Correct	54 ms	22388 KB	Output is correct
9	Correct	118 ms	39760 KB	Output is correct
10	Correct	115 ms	43856 KB	Output is correct
11	Correct	120 ms	45908 KB	Output is correct
12	Correct	119 ms	48144 KB	Output is correct
13	Correct	111 ms	56644 KB	Output is correct
14	Correct	113 ms	56768 KB	Output is correct
15	Correct	179 ms	99836 KB	Output is correct
16	Correct	157 ms	101968 KB	Output is correct
17	Correct	111 ms	58704 KB	Output is correct
18	Correct	109 ms	58712 KB	Output is correct
19	Correct	159 ms	104020 KB	Output is correct
20	Correct	154 ms	104016 KB	Output is correct