oj.uz

Submission #649698

# Submission time Handle Problem Language Result Execution time Memory
649698 2022-10-11T08:45:58 Z ToroTN Event Hopping (BOI22_events) C++14
20 / 100
 138 ms 16036 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)-2e9,(int)-2e9};
    }
    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({-2e9,-2e9,-2e9});
    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,-2e9,-2e9))-v.begin()-1;
        num=query(1,1,n,i,it).Y;
        ex[i]=it;
        //printf("itnum=%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)
            {
                if(y!=p[y][i])
                {
                    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 212 KB Output is correct
2 Correct 110 ms 15552 KB Output is correct
3 Correct 116 ms 15540 KB Output is correct
4 Correct 129 ms 15508 KB Output is correct
5 Correct 119 ms 15632 KB Output is correct
6 Correct 126 ms 15668 KB Output is correct
7 Correct 114 ms 15656 KB Output is correct
8 Incorrect 101 ms 16012 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 2 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Incorrect 1 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 2 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Incorrect 1 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 2 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Incorrect 1 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 122 ms 15572 KB Output is correct
2 Correct 138 ms 15516 KB Output is correct
3 Correct 111 ms 15560 KB Output is correct
4 Correct 94 ms 16036 KB Output is correct
5 Correct 115 ms 15884 KB Output is correct
6 Correct 136 ms 15640 KB Output is correct
7 Correct 132 ms 15720 KB Output is correct
8 Correct 111 ms 15824 KB Output is correct
9 Correct 58 ms 14888 KB Output is correct
10 Correct 103 ms 15304 KB Output is correct
11 Correct 100 ms 15076 KB Output is correct
12 Correct 103 ms 15388 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 110 ms 15552 KB Output is correct
3 Correct 116 ms 15540 KB Output is correct
4 Correct 129 ms 15508 KB Output is correct
5 Correct 119 ms 15632 KB Output is correct
6 Correct 126 ms 15668 KB Output is correct
7 Correct 114 ms 15656 KB Output is correct
8 Incorrect 101 ms 16012 KB Output isn't correct
9 Halted 0 ms 0 KB -