Mountain IOI 2005

#include <bits/stdc++.h>

using namespace std;

int N;

struct node {
    int totsum, maxsum, lazyval;
    bool lazy;
    node *left, *right;
}*root;

void propagate(node* x, int lx, int rx) {
    if(!x -> lazy)
        return;
    if(!x -> left)
        x -> left = new node();
    if(!x -> right)
        x -> right = new node();
    x -> totsum = x -> maxsum = (rx - lx + 1) * x -> lazyval;
    if(lx != rx) {
        x -> left -> lazy = x -> right -> lazy = true;
        x -> left -> lazyval = x -> right -> lazyval = x -> lazyval;
    }
    x -> lazy = false;
}

void update(int st, int dr, int val, node* x = root, int lx = 1, int rx = N + 1) {
    if(!x -> left)
        x -> left = new node();
    if(!x -> right)
        x -> right = new node();
    propagate(x, lx, rx);
    if(st <= lx && rx <= dr) {
        x -> lazy = 1;
        x -> lazyval = val;
        propagate(x, lx, rx);
        return;
    }
    int mid = (lx + rx) >> 1;
    if(st <= mid)
        update(st, dr, val, x -> left, lx, mid), propagate(x -> right, mid + 1, rx);
    if(mid < dr)
        update(st, dr, val, x -> right, mid + 1, rx), propagate(x -> left, lx, mid);
    x -> totsum = x -> left -> totsum + x -> right -> totsum;
    x -> maxsum = max(x -> left -> maxsum, x -> left -> totsum + x -> right -> maxsum);
}

int query(int val, node* x = root, int lx = 1, int rx = N + 1) {
    if(lx == rx)
        return lx;
    if(!x -> left)
        x -> left = new node();
    if(!x -> right)
        x -> right = new node();
    int mid = (lx + rx) >> 1;
    propagate(x, lx, rx);
    propagate(x -> left, lx, mid);
    if(x -> left -> maxsum > val)
        return query(val, x -> left, lx, mid);
    return query(val - x -> left -> totsum, x -> right, mid + 1, rx);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> N;
    root = new node();
    char type;
    update(N + 1, N + 1, INT_MAX);
    while(cin >> type, type != 'E') {
        if(type == 'Q') {
            int x;
            cin >> x;
            cout << query(x) - 1 << '\n';
        }
        else {
            int st, dr, val;
            cin >> st >> dr >> val;
            update(st, dr, val);
        }
    }
}