Submission #393503

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
393503	2021-04-23T16:16:36 Z	SavicS	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	480 ms	200460 KB

apple

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 100005;
const int inf = 1e9 + 5;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n, q;

int idx = 0;
int ls[50 * maxn], rs[50 * maxn], root, lenj[50 * maxn];
ll bor[50 * maxn];

void propagate(int v, int tl, int tr) {
    if(lenj[v] != -1) {
        bor[v] = (tr - tl + 1) * 1ll * lenj[v];
        if(tl != tr) {
            if(ls[v] == 0)ls[v] = ++idx;
            lenj[ls[v]] = lenj[v];
            if(rs[v] == 0)rs[v] = ++idx;
            lenj[rs[v]] = lenj[v];
        }
        lenj[v] = -1;
    }
}

void lazyupd(int &v, int tl, int tr, int l, int r, int val) {
    if(!v) {
        v = ++idx;
        lenj[v] = -1;
    }
    propagate(v, tl, tr);
    if(tl > tr || tl > r || l > tr)return;
    if(tl >= l && tr <= r) {
        bor[v] = (tr - tl + 1) * 1ll * val;
        if(tl != tr) {
            if(ls[v] == 0)ls[v] = ++idx;
            lenj[ls[v]] = val;
            if(rs[v] == 0)rs[v] = ++idx;
            lenj[rs[v]] = val;
        }
        return;
    }
    int mid = (tl + tr) / 2;
    lazyupd(ls[v], tl, mid, l, r, val);
    lazyupd(rs[v], mid + 1, tr, l, r, val);
    bor[v] = bor[ls[v]] + bor[rs[v]];
}

ll kveri(int v, int tl, int tr, int l, int r) {
    propagate(v, tl, tr);
    if(!v || tl > r || l > tr)return 0;
    if(tl >= l && tr <= r)return bor[v];
    int mid = (tl + tr) / 2;
    return kveri(ls[v], tl, mid, l, r) + kveri(rs[v], mid + 1, tr, l, r);
}

int main() 
{
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
    cin >> q;

    const int N = (int)1e9;

    int last = 0;
    while(q--) {
        int t, l, r;
        cin >> t >> l >> r;

        l += last, r += last;

        if(t == 2) {
            lazyupd(root, 1, N, l, r, 1);
        }

        if(t == 1) {
            last = kveri(root, 1, N, l, r);
            cout << last << endl;
        }

    }
    return 0;
}
/**



// probati bojenje sahovski ili slicno

**/

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	23 ms	3916 KB	Output is correct
5	Correct	28 ms	4692 KB	Output is correct
6	Correct	28 ms	4480 KB	Output is correct
7	Correct	28 ms	4648 KB	Output is correct
8	Correct	197 ms	33224 KB	Output is correct
9	Correct	456 ms	56664 KB	Output is correct
10	Correct	447 ms	63332 KB	Output is correct
11	Correct	464 ms	68588 KB	Output is correct
12	Correct	460 ms	70908 KB	Output is correct
13	Correct	420 ms	87904 KB	Output is correct
14	Correct	412 ms	88780 KB	Output is correct
15	Runtime error	480 ms	200460 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-