Submission #924815

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
924815	2024-02-09T18:27:02 Z	Karoot	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	178 ms	153900 KB

apple

#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>

#define all(x)  (x).begin(), (x).end()
#define rall(x)  (x).rbegin(), (x).rend()

using namespace std;

typedef long long ll;

ll linf = 1e15+1;

inline void scoobydoobydoo(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}


struct Node {
    ll sum;
    bool lzSet;
    int l, r;
    Node() : sum(0), lzSet(0), l(-1), r(-1) {}
};

const int MAXN = 1e5+1;
Node ST[64*MAXN];
int cnt = 2;

void pushup(int p){
    ST[p].sum = (ST[ST[p].l].sum + ST[ST[p].r].sum);
}

void pushdown(int p, int l, int r){
    int mid = (l+r)/2;
    int a = ST[p].l, b = ST[p].r;
    ST[a].lzSet |= ST[p].lzSet;
    ST[b].lzSet |= ST[p].lzSet;
    ST[a].sum = (ST[a].lzSet ? (mid-l+1) : ST[a].sum);
    ST[b].sum = (ST[b].lzSet ? (r - mid) : ST[b].sum);
    ST[p].lzSet = 0;
    return;
}

void update(int p, int l, int r, int a, int b){
    if (a == l && b == r){
        ST[p].sum = r-l+1;
        ST[p].lzSet = 1;
        return;
    }
    int mid = (l+r)/2;
    if (ST[p].l == -1){
        ST[p].l = cnt++;
        ST[ST[p].l];
    }
    if (ST[p].r == -1){
        ST[p].r = cnt++;
        ST[ST[r].l];
    }
    pushdown(p, l, r);
    
    if (b <= mid){
        update(ST[p].l, l, mid, a, b);
    } else if (a >= mid+1){
        update(ST[p].r, mid+1, r, a, b);
    } else {
        update(ST[p].l, l, mid, a, mid);
        update(ST[p].r, mid+1, r, mid+1, b);
    }
    pushup(p);
    return;
}

ll query(int p, int l, int r, int a, int b) {
	if (a == l && r == b) return ST[p].sum;
	int mid = (l + r) >> 1;
    if (ST[p].l == -1){
        ST[p].l = cnt++;
        ST[ST[p].l];
    }
    if (ST[p].r == -1){
        ST[p].r = cnt++;
        ST[ST[r].l];
    }
	pushdown(p, l, r);
    if (b <= mid){
        return query(ST[p].l, l, mid, a, b);
    }
    if (a >= mid+1){
        return query(ST[p].r, mid+1, r, a, b);
    
    }
	return query(ST[p].l, l, mid, a, mid) + query(ST[p].r, mid + 1, r, mid+1, b);
}



int main(){
    scoobydoobydoo();
    int q; cin >> q;
    vector<ll> ans;
    ST[1];
    ll C = 0;
    while (q--){
        int t, x, y; cin >> t >> x >> y;
        if (t == 2){
            update(1, 0, 1e9, x+C, y+C);
        } else {
            ans.push_back(query(1, 0, 1e9, x+C, y+C));
            C = ans[ans.size()-1];
        }
    }

    for (auto& e : ans){
        cout << e << "\n";
    }


    return 0;
}

Compilation message

apple.cpp: In function 'void update(int, int, int, int, int)':
apple.cpp:63:19: warning: statement has no effect [-Wunused-value]
   63 |         ST[ST[p].l];
      |         ~~~~~~~~~~^
apple.cpp:67:19: warning: statement has no effect [-Wunused-value]
   67 |         ST[ST[r].l];
      |         ~~~~~~~~~~^
apple.cpp: In function 'll query(int, int, int, int, int)':
apple.cpp:88:19: warning: statement has no effect [-Wunused-value]
   88 |         ST[ST[p].l];
      |         ~~~~~~~~~~^
apple.cpp:92:19: warning: statement has no effect [-Wunused-value]
   92 |         ST[ST[r].l];
      |         ~~~~~~~~~~^
apple.cpp: In function 'int main()':
apple.cpp:111:9: warning: statement has no effect [-Wunused-value]
  111 |     ST[1];
      |     ~~~~^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	50 ms	150516 KB	Output is correct
2	Correct	29 ms	150612 KB	Output is correct
3	Correct	29 ms	150616 KB	Output is correct
4	Correct	36 ms	150868 KB	Output is correct
5	Correct	38 ms	150904 KB	Output is correct
6	Correct	39 ms	151284 KB	Output is correct
7	Correct	38 ms	150868 KB	Output is correct
8	Correct	82 ms	151968 KB	Output is correct
9	Correct	152 ms	153296 KB	Output is correct
10	Correct	170 ms	153292 KB	Output is correct
11	Correct	155 ms	153328 KB	Output is correct
12	Correct	154 ms	153300 KB	Output is correct
13	Correct	156 ms	153812 KB	Output is correct
14	Correct	148 ms	153808 KB	Output is correct
15	Correct	175 ms	153692 KB	Output is correct
16	Correct	175 ms	153704 KB	Output is correct
17	Correct	145 ms	153776 KB	Output is correct
18	Correct	146 ms	153804 KB	Output is correct
19	Correct	178 ms	153724 KB	Output is correct
20	Correct	177 ms	153900 KB	Output is correct