Submission #612549

#	Time	Username	Problem	Language	Result	Execution time	Memory
612549		hibiki	Event Hopping (BOI22_events)	C++11	100 / 100	869 ms	54464 KiB

events

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

#define pb push_back
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()

int n, q;
int pw2[20];
pair<int,int> a[100005];
int spa[100005][20];

set<int> re;
vector<int> re2;
map<int, int> en, de;
struct node
{
    pair<int, int> mn = {2e9, -1};
    node *l = NULL, *r = NULL;
} *root;

node* build(int l, int r)
{
    node *ptr = new node();
    if(l == r) return ptr;
    int mid = (l + r) / 2;
    ptr->l = build(l, mid);
    ptr->r = build(mid + 1, r);
    return ptr;
}

void up(node *ptr, int l, int r, pair<int, int> val, int po)
{
    ptr->mn = min(ptr->mn, val);
    if(l == r) return ;
    int mid = (l + r) / 2;
    if(po <= mid) up(ptr->l, l, mid, val, po);
    else up(ptr->r, mid + 1, r, val, po);
}

pair<int, int> que(node *ptr, int l, int r, int ll, int rr)
{
    if(ll <= l && r <= rr) return ptr->mn;
    if(r < ll || rr < l) return {2e9, -1};
    int mid = (l + r) / 2;
    return min(que(ptr->l, l, mid, ll, rr), que(ptr->r, mid + 1, r, ll, rr));
}

int main()
{
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    pw2[0] = 1;
    for(int i = 1; i < 20; i++)
        pw2[i] = pw2[i - 1] * 2;
    scanf("%d %d", &n, &q);
    for(int i = 0; i < n; i++)
    {
        scanf("%d %d", &a[i].f, &a[i].s);
        re.insert(a[i].f);
        re.insert(a[i].s);
    }
    for(auto val: re)
    {
        en[val] = sz(re2);
        de[sz(re2)] = val;
        re2.pb(val);
    }
    root = build(0, sz(re2));
    for(int i = 0; i < n; i++)
        up(root, 0, sz(re2), {a[i].f, i}, en[a[i].s]);
    for(int i = 0; i < n; i++)
    {
        pair<int, int> ret = que(root, 0, sz(re2), en[a[i].f], en[a[i].s]);
        if(ret.s == i || ret.f == a[i].f)
            spa[i][0] = -1;
        else
            spa[i][0] = ret.s;
        // printf("p: %d %d\n",i, spa[i][0]);
    }

    for(int j = 1; j < 20; j++)
        for(int i = 0; i < n; i++)
            if(spa[i][j - 1] != -1)
                spa[i][j] = spa[spa[i][j - 1]][j - 1];
            else
                spa[i][j] = -1;

    for(int i = 0; i < q; i++)
    {
        int s, t;
        scanf("%d %d", &s, &t);
        s--, t--;
        if(s == t)
            printf("0\n");
        else if(a[t].f <= a[s].s && a[s].s <= a[t].s)
            printf("1\n");
        else if(a[s].s > a[t].s)
            printf("impossible\n");
        else
        {
            int ans = 0, cur = t;
            for(int j = 19; j >= 0; j--)
            {
                if(spa[cur][j] != -1 && a[s].s < a[spa[cur][j]].f)
                {
                    ans += pw2[j];
                    cur = spa[cur][j];
                }
            }
            if(spa[cur][0] != -1 && a[spa[cur][0]].f <= a[s].s)
                printf("%d\n", ans + 2);
            else
                printf("impossible\n");
        }
    }
    return 0;
}

/*
8 5
1 2
3 4
1 5
6 7
5 10
10 20
15 20
999999999 1000000000
1 6
1 7
2 4
3 3
5 8
*/

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
events.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%d %d", &a[i].f, &a[i].s);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         scanf("%d %d", &s, &t);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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