Submission #920527

# Submission time Handle Problem Language Result Execution time Memory
920527 2024-02-02T17:23:23 Z Macker Monkey and Apple-trees (IZhO12_apple) C++17
0 / 100
2000 ms 70884 KB
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()

struct node{
    int val = 0;
    int lz = 0;
};
map<int, node> st;

void prop(int i, int d){
    if(!st[i].lz) return;
    st[i * 2].val = d / 2;
    st[i * 2 + 1].val = d / 2;
    st[i * 2].lz = 1;
    st[i * 2 + 1].lz = 1;
    st[i].lz = 0;
}

void upd(int l, int r, int i = 1, int s = 0, int e = 2147483647){
    if(l >= e || r <= s) return;
    if(l <= s && e <= r){
        st[i].val = e - s;
        st[i].lz = 1;
        return;
    }
    prop(i, e - s);

    upd(l, r, i * 2, s, (s + e) / 2);
    upd(l, r, i * 2 + 1, (s + e) / 2, e);
    st[i].val = st[i * 2].val + st[i * 2 + 1].val;
}

int qry(int l, int r, int i = 1, int s = 0, int e = 2147483647){
    if(l >= e || r <= s) return 0;
    if(l <= s && e <= r) return st[i].val;
    prop(i, e - s);

    return qry(l, r, i * 2, s, (s + e) / 2) + qry(l, r, i * 2 + 1, (s + e) / 2, e);
}

int main()
{
    int m; cin >> m;
    int c = 0;
    for (int i = 0; i < m; i++) {
        int d, x, y; cin >> d >> x >> y;
        if(d == 1){
            int res = qry(x + c, y + c + 1);
            cout << res << "\n";
            c = res;
        }
        else{
            upd(x + c, y + c + 1);
        }
    }
    
}
# 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 1 ms 348 KB Output is correct
4 Correct 132 ms 6480 KB Output is correct
5 Correct 168 ms 7764 KB Output is correct
6 Correct 180 ms 7640 KB Output is correct
7 Correct 167 ms 7764 KB Output is correct
8 Correct 1754 ms 58996 KB Output is correct
9 Execution timed out 2084 ms 70884 KB Time limit exceeded
10 Halted 0 ms 0 KB -