oj.uz

Submission #920526

# Submission time Handle Problem Language Result Execution time Memory
920526 2024-02-02T17:20:48 Z Macker Monkey and Apple-trees (IZhO12_apple) C++17
0 / 100
 2000 ms 164444 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;
};
unordered_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);
        }
    }
    
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 41 ms 5228 KB Output is correct
5 Correct 50 ms 5576 KB Output is correct
6 Correct 52 ms 5468 KB Output is correct
7 Correct 48 ms 5680 KB Output is correct
8 Correct 616 ms 41756 KB Output is correct
9 Correct 1443 ms 82056 KB Output is correct
10 Correct 1495 ms 81880 KB Output is correct
11 Correct 1617 ms 86044 KB Output is correct
12 Correct 1605 ms 87780 KB Output is correct
13 Correct 1549 ms 97868 KB Output is correct
14 Correct 1571 ms 98572 KB Output is correct
15 Execution timed out 2072 ms 164444 KB Time limit exceeded
16 Halted 0 ms 0 KB -