Submission #1117914

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1117914	2024-11-24T09:57:47 Z	gdragon	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	288 ms	87032 KB

apple

#include <bits/stdc++.h>
using namespace std;
#define TASK "long"
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define GETBIT(mask, i) ((mask) >> (i) & 1)
#define MASK(i) ((1LL) << (i))
#define SZ(x) ((int)(x).size())
#define mp make_pair
#define CNTBIT(mask) __builtin_popcount(mask)
template<class X, class Y> bool maximize(X &x, Y y){ if (x < y) {x = y; return true;} return false;};
template<class X, class Y> bool minimize(X &x, Y y){ if (x > y) {x = y; return true;} return false;};
typedef pair<int, int> ii;
const int N = 1e5 + 5;
const int INF = 1e9 + 7;
const int mod = 1e9 + 7;
struct Node {
    int lz = 0;
    long long val = 0;
    Node* left = NULL, *right = NULL;
} *root;
int q;
void read() {
    cin >> q;
}
void update(Node* &head, int l, int r, int u, int v, int lz) {
    if (u > r || v < l) return;
    if (head == NULL) head = new Node();
    if (u <= l && r <= v) {
        // cout << "UPD: " << l << ' ' << r << ' ' << r - l + 1 << endl;
        head->lz = 1;
        head->val = r - l + 1;
        return;
    }
    // cerr << "RUN: " << l << ' ' << r << ' ' << u << ' ' << v << endl;
    int mid = (l + r) >> 1;
    lz |= head->lz;
    if (v <= mid) update(head->left, l, mid, u, v, lz);
    else if (u > mid) update(head->right, mid + 1, r, u, v, lz);
    else {
        update(head->left, l, mid, u, v, lz);
        update(head->right, mid + 1, r, u, v, lz);
    }
    head->val = (head->left != NULL ? head->left->val : 0) + 
                (head->right != NULL ? head->right->val : 0);
    if (lz) {
        head->val = r - l + 1;
        head->lz = 1;
    }
    // cout << l << ' ' << r << ' ' << head->val << endl;
}
long long getSum(Node* &head, int l, int r, int u, int v, int lz) {
    if (u > r || v < l) return 0;
    if (head == NULL) {
        if (lz) {
            // if (u == 8 && v == 11) cerr << l << ' ' << r << ' ' << min(v, r) - max(u, l) + 1 << endl;
            return min(v, r) - max(u, l) + 1;
        }
        return 0;
    }
    lz |= head->lz;
    if (lz) head->val = r - l + 1;
    // cerr << l << ' ' << r << ' ' << u << ' ' << v << endl;
    if (u <= l && r <= v) {
        // if (u == 8 && v == 11) cerr << l << ' ' << r << ' ' << lz << ' ' << head->val << endl;
        // cout << l << ' ' << r << ' ' << head->val << endl;
        return head->val;
    }
    int mid = (l + r) >> 1;
    if (v <= mid) return getSum(head->left, l, mid, u, v, lz);
    else if (u > mid) return getSum(head->right, mid + 1, r, u, v, lz);
    else {
        return getSum(head->left, l, mid, u, v, lz) + getSum(head->right, mid + 1, r, u, v, lz);
    }
}
void solve() {
    root = new Node();
    long long C = 0;
    while(q--) {
        long long type, l, r; cin >> type >> l >> r;
        l += C; r += C;
        if (type == 2) update(root, 1, (int)1e9, l, r, root->lz);
        else {
            C = getSum(root, 1, (int)1e9, l, r, 0);
            cout << C << endl;
        }
    }
}
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
    int test = 1;
    // cin >> test;
    while(test--) {
        read();
        solve();
    }
    return 0;
}

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	376 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	19 ms	2384 KB	Output is correct
5	Correct	18 ms	2896 KB	Output is correct
6	Correct	23 ms	2968 KB	Output is correct
7	Correct	16 ms	2896 KB	Output is correct
8	Correct	120 ms	20868 KB	Output is correct
9	Correct	233 ms	37380 KB	Output is correct
10	Correct	224 ms	40856 KB	Output is correct
11	Correct	244 ms	43088 KB	Output is correct
12	Correct	219 ms	44308 KB	Output is correct
13	Correct	194 ms	46408 KB	Output is correct
14	Correct	191 ms	47692 KB	Output is correct
15	Correct	272 ms	85148 KB	Output is correct
16	Correct	288 ms	85384 KB	Output is correct
17	Correct	215 ms	48848 KB	Output is correct
18	Correct	219 ms	48768 KB	Output is correct
19	Correct	274 ms	86856 KB	Output is correct
20	Correct	282 ms	87032 KB	Output is correct