Submission #612513

#	Time	Username	Problem	Language	Result	Execution time	Memory
612513		hibiki	Event Hopping (BOI22_events)	C++11	0 / 100	85 ms	11252 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];
vector<pair<pair<int, int>, int> > ev;

int main()
{
    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);
        ev.pb({{a[i].s, a[i].f}, i});
    }
    sort(all(ev));
    priority_queue<pair<pair<int,int>, int> > pq;
    for(int i = 0; i < n; i++)
    {
        while(!pq.empty() && pq.top().f.s < ev[i].f.s)
            pq.pop();
        if(!pq.empty() && -pq.top().f.f < ev[i].f.s)
            spa[ev[i].s][0] = pq.top().s;
        else
            spa[ev[i].s][0] = -1;
        pq.push({{-ev[i].f.s, ev[i].f.f}, ev[i].s});
        // printf("p: %d %d\n",ev[i].s, spa[ev[i].s][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];

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

Compilation message (stderr)

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

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