Submission #393506

#	Time	Username	Problem	Language	Result	Execution time	Memory
393506		SavicS	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	552 ms	163064 KiB

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 / 100