Submission #870648

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
870648	2023-11-08T16:58:25 Z	NoLove	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	319 ms	262144 KB

apple

/**
 *    author : Lăng Trọng Đạt
 *    created: 08-11-2023 
**/
#include <bits/stdc++.h>
using namespace std;
#ifndef LANG_DAT
#define db(...) ;
#endif // LANG_DAT
#define int int64_t
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define all(v) (v).begin(), (v).end()
using pii = pair<int, int>;

const int MAXN = 2e7 + 5;
struct Node {
    int val, lazy;
    int lc, rc; // left child, right child
    int lb, rb; // left border, right border
} st[MAXN];
ostream& operator<<(ostream& os, Node& v) {
    os << "[" << v.val << " " << v.lb << " " << v.rb << "]";
}
int q, type, l, r;
int id = 2;

void extend(Node& v) {
    if (!v.lc) {
        int mid = (v.lb + v.rb) / 2;
        st[id].lb = v.lb;
        st[id].rb = mid;
        v.lc = id++;

        st[id].lb = mid + 1;
        st[id].rb = v.rb;
        v.rc = id++;
    }
}
void push(Node& v) {
    if (v.lazy) {
        if (v.lb < v.rb) {
            extend(v);
            st[v.lc].lazy = st[v.rc].lazy = 1;
        }
        v.val = v.rb - v.lb + 1;
        v.lazy = 0;
    }
}
void upd(Node& v, int l, int r) {
    // db(v)
    push(v);
    // if (v.lb > r or l > v.rb) return;
    if (l == v.lb && v.rb == r) {
        v.lazy = 1;
        push(v);
    } else {
        extend(v);
        int mid = (v.rb + v.lb) / 2;
        if (l > mid) upd(st[v.rc], l, r);
        else if (r <= mid) upd(st[v.lc], l, r);
        else {
            upd(st[v.lc], l, mid); 
            upd(st[v.rc], mid + 1, r);
        }
        push(st[v.lc]); push(st[v.rc]);
        v.val = st[v.lc].val + st[v.rc].val;
    }
}
int get(Node& v, int l, int r) {
    push(v);
    // db(v)
    // if (v.lb > r or l > v.rb) return 0;
    if (l == v.lb && v.rb == r) {
        return v.val;
    } else {
        extend(v);
        int mid = (v.rb + v.lb) / 2;
        if (l > mid) return get(st[v.rc], l, r);
        else if (r <= mid) return get(st[v.lc], l, r);
        else {
            return get(st[v.lc], l, mid) + 
                   get(st[v.rc], mid + 1, r);
        }
    }
}

int32_t main() {
    // cin.tie(0)->sync_with_stdio(0);
    if (fopen("hi.inp", "r")) {
        freopen("hi.inp", "r", stdin);
//        freopen("hi.out", "w", stdout);
    } 
    st[1].lb = 1; st[1].rb = 1e9 + 50;
    cin >> q;
    int c = 0;
    while (cin >> type >> l >> r) {
        // db(l, r)
        l += c; r += c;
        if (type == 2) {
            upd(st[1], l, r);
        } else {
            c = get(st[1], l, r);
            cout << c << "\n";
        }
    }
}

Compilation message

apple.cpp: In function 'std::ostream& operator<<(std::ostream&, Node&)':
apple.cpp:26:1: warning: no return statement in function returning non-void [-Wreturn-type]
   26 | }
      | ^
apple.cpp: In function 'int32_t main()':
apple.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         freopen("hi.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	15 ms	8796 KB	Output is correct
5	Correct	19 ms	10916 KB	Output is correct
6	Correct	19 ms	10844 KB	Output is correct
7	Correct	19 ms	10844 KB	Output is correct
8	Correct	144 ms	70568 KB	Output is correct
9	Correct	286 ms	119748 KB	Output is correct
10	Correct	319 ms	134272 KB	Output is correct
11	Correct	290 ms	144576 KB	Output is correct
12	Correct	289 ms	148564 KB	Output is correct
13	Correct	269 ms	181568 KB	Output is correct
14	Correct	277 ms	183468 KB	Output is correct
15	Runtime error	279 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-