Submission #1039348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039348		Blagoj	Event Hopping (BOI22_events)	C++17	0 / 100	309 ms	157000 KiB

events

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()

const int mxn = 2e5 + 100;

vector<pair<ll, ll>> v;
vector<int> dg[mxn], g[mxn];

struct Node {
    ll lp = -1, rp = -1, r = -1, ind = -1, lz = -1, lzind = -1;
} null;

struct Query {
    ll l1, r1, l2, r2, ans, ind;
};

struct SGT {
    ll cnt = 2;
    vector<Node> sgt;

    SGT(ll sz) {
        sgt.resize(8 * sz);
    }

    void set(ll &x, ll &y, ll &s1, ll &s2) {
        if (x == -1) x = cnt++;
        if (y == -1) y = cnt++;
        s1 = x, s2 = y;
    }

    void push(ll k, ll l, ll r) {
        if (sgt[k].lz != -1) {
            if (sgt[k].lz > sgt[k].r) sgt[k].ind = sgt[k].lzind;
            sgt[k].r = max(sgt[k].r, sgt[k].lz);
            if (l != r) {
                ll lp, rp;
                set(sgt[k].lp, sgt[k].rp, lp, rp);
                sgt[lp].lz = sgt[k].lz;
                sgt[rp].lz = sgt[k].lz;
                sgt[lp].lzind = sgt[k].lzind;
                sgt[rp].lzind = sgt[k].lzind;
            }
            sgt[k].lz = sgt[k].lzind = -1;
        }
    }

    void merge(Node &k, Node k1, Node k2) {
        k.r = max(k1.r, k2.r);
        if (k1.r > k2.r) k.ind = k1.ind;
        else k.ind = k2.ind;
    }

    void update(ll k, ll l, ll r, ll i, ll j, ll ind) {
        push(k, l, r);
        if (l > j || r < i) return;
        if (i <= l && r <= j) {
            sgt[k].lz = j;
            sgt[k].lzind = ind;
            push(k, l, r);
            return;
        }
        ll mid = (l + r) / 2;
        ll lp, rp;
        set(sgt[k].lp, sgt[k].rp, lp, rp);
        update(lp, l, mid, i, j, ind);
        update(rp, mid + 1, r, i, j, ind);
        merge(sgt[k], sgt[lp], sgt[rp]);
    }

    Node get(ll k, ll l, ll r, ll i) {
        push(k, l, r);
        if (l > i || r < i) return null;
        if (l == r) return sgt[k];
        ll mid = (l + r) / 2;
        ll lp, rp;
        set(sgt[k].lp, sgt[k].rp, lp, rp);
        Node ansL = get(lp, l, mid, i), ansR = get(rp, mid + 1, r, i);
        Node ans;
        merge(ans, ansL, ansR);
        return ans;
    }
} sgt(mxn);

struct sgtINT {
    vector<ll> sgt;

    sgtINT(int sz) {
        sgt.resize(8 * sz, -1);
    }

    void update(int k, int l, int r, int i, ll val) {
        if (l > i || r < i) return;
        if (l == r) {
            sgt[k] = max(sgt[k], val);
            return;
        }
        int mid = (l + r) / 2;
        update(k * 2, l, mid, i, val);
        update(k * 2 + 1, mid + 1, r, i, val);
        sgt[k] = max(sgt[k * 2], sgt[k * 2 + 1]);
    }

    ll get(int k, int l, int r, int i, int j) {
        if (l > j || r < i) return -1;
        if (i <= l && r <= j) return sgt[k];
        int mid = (l + r) / 2;
        return max(get(k * 2, l, mid, i, j), get(k * 2 + 1, mid + 1, r, i, j));
    }
} con(mxn);

vector<int> ord;
bool visited[mxn];

void dfs(int cur, int par = -1) {
    visited[cur] = 1;
    for (auto x : dg[cur]) if (x != par && !visited[x]) dfs(x, cur);
    ord.push_back(cur);
}

ll nxt[mxn][18], sum[mxn][18];
set<ll> all;

void calc(int cur, int par) {
    visited[cur] = 1;
    if (cur == par) {
        for (int i = 0; i < 18; i++) nxt[cur][i] = cur, sum[cur][i] = 0;
    }
    else {
        nxt[cur][0] = par;
        sum[cur][0] = 1;
        for (int i = 1; i < 18; i++) {
            int node = nxt[nxt[cur][i - 1]][i - 1];
            nxt[cur][i] = node;
            sum[cur][i] = sum[cur][i - 1] + sum[node][i - 1];
        }
    }
    for (auto x : g[cur]) {
        if (!visited[x]) calc(x, cur);
    }
}

vector<Query> qr;
vector<string> res;

void solve(ll l, ll r, int IND) {
    if (l == r) {
        res.push_back("0");
        return;
    }
    ll cur = l, ans = 1;
    for (int i = 17; i >= 0; i--) {
        ll nxtCur = nxt[cur][i];
        if (v[nxtCur].second <= v[r].first) {
            ans += sum[cur][i];
            cur = nxtCur;
        }
    }
    if (v[cur].second > v[r].second) {
        res.push_back("impossible");
        return;
    }
    if (v[r].first <= v[cur].second && v[cur].second <= v[r].second) {
        res.push_back(to_string(ans));
        return;
    }
    ans++;
    res.push_back("impossible");
    qr.push_back({v[cur].first, v[cur].second, v[r].first, v[r].second, ans, IND});
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    cin >> n >> q;
    v.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> v[i].first >> v[i].second;
        all.insert(v[i].first);
        all.insert(v[i].second);
    }
    ll cnt = 0;
    map<ll, ll> h;
    for (auto x : all) h[x] = cnt++;
    for (int i = 1; i <= n; i++) {
        v[i].first = h[v[i].first];
        v[i].second = h[v[i].second];
    }
    for (int i = 1; i <= n; i++) sgt.update(1, 0, cnt - 1, v[i].first, v[i].second, i);
    for (int i = 1; i <= n; i++) {
        Node ans = sgt.get(1, 0, cnt - 1, v[i].second);
        dg[i].push_back(ans.ind);
        g[i].push_back(ans.ind);
        g[ans.ind].push_back(i);
    }
    for (int i = 1; i <= n; i++) if (!visited[i]) dfs(i);
    memset(visited, 0, sizeof(visited));
    for (auto x : ord) if (!visited[x]) calc(x, x);
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        solve(l, r, i);
    }
    vector<ll> ADD[cnt + 10];
    vector<pair<ll, pair<ll, ll>>> GET[cnt + 10];
    for (int i = 0; i < qr.size(); i++) {
        auto x = qr[i];
        ADD[x.l1].push_back(x.r1);
        GET[x.r1].push_back({x.l2, {x.r2, i}});
    }
    for (int i = 0; i < cnt; i++) {
        for (auto x : ADD[i]) con.update(1, 0, cnt - 1, x, i);
        for (auto x : GET[i]) {
            ll ind = con.get(1, 0, cnt - 1, x.first, x.second.first);
            if (ind >= qr[x.second.second].l1) res[qr[x.second.second].ind] = to_string(qr[x.second.second].ans);
        }
    }
    for (int i = 0; i < q; i++) cout << res[i] << endl;
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:211:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  211 |     for (int i = 0; i < qr.size(); i++) {
      |                     ~~^~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30