oj.uz

Submission #649635

# Submission time Handle Problem Language Result Execution time Memory
649635 2022-10-11T07:27:43 Z ToroTN Event Hopping (BOI22_events) C++14
20 / 100
 213 ms 19164 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define X first
#define Y second
pair<int,int> seg[400005];
int n,t,s[100005],e[100005],l,r,x,y,idx[100005],it,p[100005][25],num,ex[100005],ans;
vector<tuple<int,int,int> > v;
void build(int tree,int st,int ed)
{
    int md=(st+ed)/2;
    if(st==ed)
    {
        seg[tree]={get<1>(v[st]),st};
        return;
    }
    build(2*tree,st,md);
    build(2*tree+1,md+1,ed);
    seg[tree]=max(seg[2*tree],seg[2*tree+1]);
}
pair<int,int> query(int tree,int st,int ed,int l,int r)
{
    int md=(st+ed)/2;
    if(st>r||ed<l)
    {
        return {(int)-1e9,(int)-1e9};
    }
    if(st>=l&&ed<=r)return seg[tree];
    return max(query(2*tree,st,md,l,r),query(2*tree+1,md+1,ed,l,r));
}
int main()
{
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&s[i],&e[i]);
        v.pb({-e[i],-s[i],i});
    }
    v.pb({-1e9,-1e9,-1e9});
    sort(v.begin(),v.end());
    for(int i=1;i<=n;i++)
    {
        idx[get<2>(v[i])]=i;
        l=get<0>(v[i]);
        r=get<1>(v[i]);
        //printf("%d %d %d\n",l,r,i);
    }
    build(1,1,n);
    for(int i=1;i<=n;i++)
    {
        it=lower_bound(v.begin(),v.end(),make_tuple(get<1>(v[i])+1,-1e9,-1e9))-v.begin()-1;
        num=query(1,1,n,i,it).Y;
        ex[i]=it;
        //printf("%d %d\n",it,num);
        p[i][0]=num;
    }
    for(int i=1;i<=20;i++)
    {
        for(int j=1;j<=n;j++)
        {
            p[j][i]=p[p[j][i-1]][i-1];
        }
    }
    while(t--)
    {
        scanf("%d%d",&x,&y);
        if(e[x]>e[y])
        {
            printf("impossible\n");
            continue;
        }
        x=idx[x];
        y=idx[y];
        ans=0;
        for(int i=20;i>=0;i--)
        {
            if(p[y][i]<x)
            {
                y=p[y][i];
                ans+=(1<<i);
            }
        }
        if(x==y)
        {
            printf("0\n");
            continue;
        }
        if(x<=ex[y])
        {
            printf("%d\n",ans+1);
        }else
        {
            printf("impossible\n");
        }
    }
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%d%d",&n,&t);
      |     ~~~~~^~~~~~~~~~~~~~
events.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         scanf("%d%d",&s[i],&e[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~
events.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 114 ms 18676 KB Output is correct
3 Correct 112 ms 18668 KB Output is correct
4 Correct 148 ms 18672 KB Output is correct
5 Correct 112 ms 18704 KB Output is correct
6 Correct 117 ms 18728 KB Output is correct
7 Correct 111 ms 18728 KB Output is correct
8 Incorrect 108 ms 19116 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 452 KB Output is correct
5 Correct 2 ms 448 KB Output is correct
6 Incorrect 2 ms 468 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 452 KB Output is correct
5 Correct 2 ms 448 KB Output is correct
6 Incorrect 2 ms 468 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 452 KB Output is correct
5 Correct 2 ms 448 KB Output is correct
6 Incorrect 2 ms 468 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 18684 KB Output is correct
2 Correct 115 ms 18700 KB Output is correct
3 Correct 121 ms 18656 KB Output is correct
4 Correct 107 ms 19164 KB Output is correct
5 Correct 201 ms 18956 KB Output is correct
6 Correct 138 ms 18720 KB Output is correct
7 Correct 213 ms 18736 KB Output is correct
8 Correct 126 ms 18880 KB Output is correct
9 Correct 66 ms 16860 KB Output is correct
10 Correct 130 ms 18448 KB Output is correct
11 Correct 172 ms 18216 KB Output is correct
12 Correct 116 ms 18364 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 114 ms 18676 KB Output is correct
3 Correct 112 ms 18668 KB Output is correct
4 Correct 148 ms 18672 KB Output is correct
5 Correct 112 ms 18704 KB Output is correct
6 Correct 117 ms 18728 KB Output is correct
7 Correct 111 ms 18728 KB Output is correct
8 Incorrect 108 ms 19116 KB Output isn't correct
9 Halted 0 ms 0 KB -