Submission #1075904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075904		hcng	Event Hopping (BOI22_events)	C++14	100 / 100	45 ms	23136 KiB

events

#include <bits/stdc++.h>
using namespace std;

char *p1, *p2, buf[1<<20];
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline int read() {int x=0;char c=gc();while(!isdigit(c))c=gc();while(isdigit(c))x=x*10+c-'0',c=gc();return x;}
#define pc(c) putchar(c)
void write(int x) {if(x>9)write(x/10);pc('0'+x%10);}

int n, q;
int mp[100010];
struct Int {
    int l, r, id;
} a[100010];
int ST[100010][20], fa[100010][20], lg2[100010];

inline int get(int x, int y) {
    return a[x].l <= a[y].l? x : y;
}

inline int query(int l, int r) {
    int d = r - l + 1;
    return get(ST[l][lg2[d]], ST[r - (1 << lg2[d]) + 1][lg2[d]]);
}

int main() {
    n = read(), q = read();
    for (int i = 1; i <= n; i++) {
        a[i].l = read(), a[i].r = read(), a[i].id = i;
    }
    sort(a + 1, a + 1 + n, [](Int &a, Int &b){return a.r < b.r || (a.r == b.r && a.l < b.l);});
    lg2[0] = -1;
    for (int i = 1; i <= n; i++) {
        mp[a[i].id] = i;
        ST[i][0] = i;
        lg2[i] = lg2[i - 1] + (i == (i & -i));
    }
    for (int i = 1; i < 20; i++) {
        for (int j = 1; j + (1 << i - 1) <= n; j++) {
            ST[j][i] = get(ST[j][i - 1], ST[j + (1 << i - 1)][i - 1]);
        }
    }
    for (int i = 1; i <= n; i++) {
        int L = 1, R = i;
        while (L < R) {
            int M = L + R >> 1;
            if (a[i].l <= a[M].r) R = M;
            else L = M + 1;
        }
        if (L != i) fa[i][0] = query(L, i - 1);
        else fa[i][0] = 0;
        // cerr << a[i].l << ' ' << a[i].r << ' ' << fa[i][0] << endl;
    }
    for (int i = 1; i < 20; i++) {
        for (int j = 1; j <= n; j++) {
            fa[j][i] = fa[fa[j][i - 1]][i - 1];
        }
    }
    a[0].l = -1;
    while (q--) {
        int s = read(), t = read();
        s = mp[s], t = mp[t];
        if (s == t) {
            puts("0");
            continue;
        }
        if (a[s].r > a[t].r) {
            puts("impossible");
            continue;
        }
        if (a[t].l <= a[s].r) {
            puts("1");
            continue;
        }
        int ans = 0;
        for (int i = 19; i >= 0; i--) {
            if (a[fa[t][i]].l > a[s].r) t = fa[t][i], ans += 1 << i;
        }
        t = fa[t][0];
        if (!t) {
            puts("impossible");
            continue;
        }
        write(ans + 2); pc('\n');
    }
    return 0;
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:39:37: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   39 |         for (int j = 1; j + (1 << i - 1) <= n; j++) {
      |                                   ~~^~~
events.cpp:40:57: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   40 |             ST[j][i] = get(ST[j][i - 1], ST[j + (1 << i - 1)][i - 1]);
      |                                                       ~~^~~
events.cpp:46:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |             int M = L + R >> 1;
      |                     ~~^~~

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