Submission #393506

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
393506	2021-04-23T16:19:09 Z	SavicS	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	552 ms	163064 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[100 * maxn], rs[100 * maxn], root, lenj[100 * maxn];
ll bor[100 * 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

100.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	3780 KB	Output is correct
5	Correct	28 ms	4432 KB	Output is correct
6	Correct	29 ms	4292 KB	Output is correct
7	Correct	29 ms	4464 KB	Output is correct
8	Correct	192 ms	32324 KB	Output is correct
9	Correct	473 ms	54952 KB	Output is correct
10	Correct	430 ms	61584 KB	Output is correct
11	Correct	434 ms	66752 KB	Output is correct
12	Correct	451 ms	69032 KB	Output is correct
13	Correct	389 ms	85960 KB	Output is correct
14	Correct	428 ms	86924 KB	Output is correct
15	Correct	546 ms	158044 KB	Output is correct
16	Correct	545 ms	159292 KB	Output is correct
17	Correct	384 ms	89808 KB	Output is correct
18	Correct	394 ms	90032 KB	Output is correct
19	Correct	552 ms	163044 KB	Output is correct
20	Correct	545 ms	163064 KB	Output is correct