oj.uz

Submission #920528

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

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

#pragma GCC optimize("O3")
#pragma GCC target("avx2")

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 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 48 ms 5012 KB Output is correct
5 Correct 51 ms 5392 KB Output is correct
6 Correct 48 ms 5320 KB Output is correct
7 Correct 50 ms 5320 KB Output is correct
8 Correct 571 ms 41124 KB Output is correct
9 Correct 1344 ms 80632 KB Output is correct
10 Correct 1523 ms 80164 KB Output is correct
11 Correct 1552 ms 84360 KB Output is correct
12 Correct 1733 ms 85896 KB Output is correct
13 Correct 1477 ms 95984 KB Output is correct
14 Correct 1485 ms 96500 KB Output is correct
15 Execution timed out 2105 ms 162468 KB Time limit exceeded
16 Halted 0 ms 0 KB -