Ispiti

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define F first
#define S second
using pi=pair<int,int>;
const int inf = 1e9;
struct segtree {
    vector<pi> puu;
    int N;
    segtree()
    {
        N = 1 << 19;
        puu.resize(N * 2, make_pair(0, 0));
    }

    void muuta(int l, int r, int ll, int rr, int s, pi x)
    {
        if (rr < l || r < ll) return;
        if (l <= ll && rr <= r) {
            puu[s] = x;
            return;
        }
        int w = (rr - ll) / 2;
        muuta(l, r, ll, ll + w, s * 2, x);
        muuta(l, r, ll + w + 1, rr, s * 2 + 1, x);
        puu[s] = max(puu[s*2],puu[s*2+1]);
    }

    int hae(int l, int ll ,int rr, int s, int x, int itse)
    {
        if (rr < l) return inf;
        if (puu[s].F < x) return inf;
        if (s >= N) {
            if (puu[s].S == itse) return inf;
            return puu[s].S;
        }
        int w = (rr - ll) / 2;
        int r = hae(l, ll, ll + w, s * 2, x, itse);
        if (r == inf) return hae(l, ll + w + 1, rr, s * 2 + 1, x, itse);
        return r;
    }

    void muuta(int l, pi x)
    {
        muuta(l, l, 0, N - 1, 1, x);
    }

    int hae(int l, int x, int itse)
    {
        return hae(l, 0, N - 1, 1, x, itse);
    }
};

int main()
{
    int n;
    cin >> n;
    vector<pi> o;
    vector<pair<int, pi>>q;
    vector<pi> orig(n * 2);
    int idx = 1;
    for (int i = 0; i < n; ++i) {
        char c;
        cin >> c;
        int a, b;
        if (c == 'D') {
            cin >> a >> b;
            q.emplace_back(0, make_pair(a, b));
            o.emplace_back(b, a);
        }
        else {
            cin >> a;
            q.emplace_back(1, make_pair(a, a));
        }
    }
    sort(all(o));
    vector<int> start(o.size());
    segtree lol;
    for (int i = 0; i < n; ++i) {
        if (q[i].F == 0) {
            int it = lower_bound(all(o), make_pair(q[i].S.S, q[i].S.F)) - o.begin();
            lol.muuta(it + 1, make_pair(q[i].S.F, idx));
            orig[idx++] = q[i].S;
        }
        else {
            auto z = orig[q[i].S.F];
            int it = lower_bound(all(o), make_pair(z.S, -inf)) - o.begin();
            int y = lol.hae(it + 1, z.F, q[i].S.F);
            if (y == inf) cout << "NE\n";
            else cout << y << "\n";
        }
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED