oj.uz

Submission #363360

# Submission time Handle Problem Language Result Execution time Memory
363360 2021-02-05T17:47:41 Z denkendoemeer Railway Trip (JOI17_railway_trip) C++14
100 / 100
 280 ms 18924 KB 
#include<bits/stdc++.h>
using namespace std;
pair<int,int>maxi[25][100005];
int v[100005],st[100005];
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,k,q,i;
    scanf("%d%d%d",&n,&k,&q);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);
    int u=0;
    maxi[0][1].first=1;
    for(i=1;i<=n;i++){
        while(u && v[st[u]]<=v[i])
            maxi[0][st[u]].second=i,u--;
        st[++u]=i;
    }
    u=0;
    maxi[0][n].second=n;
    for(i=n;i>=1;i--){
        while(u && v[st[u]]<=v[i])
            maxi[0][st[u]].first=i,u--;
        st[++u]=i;
    }
    int j;
    for(i=1;i<20;i++){
        for(j=1;j<=n;j++){
            int x=maxi[i-1][j].first,y=maxi[i-1][j].second;
            maxi[i][j]=make_pair(min(maxi[i-1][x].first,maxi[i-1][y].first),max(maxi[i-1][x].second,maxi[i-1][y].second));
        }
    }
    for(i=1;i<=q;i++){
        int l,r,ans=0;
        scanf("%d%d",&l,&r);
        if (l>r)
            swap(l,r);
        int x,y;
        x=y=l;
        int j;
        for(j=19;j>=0;j--){
            if (max(maxi[j][x].second,maxi[j][y].second)>=r)
                continue;
            int x2,y2;
            x2=min(maxi[j][x].first,maxi[j][y].first);
            y2=max(maxi[j][x].second,maxi[j][y].second);
            x=x2;
            y=y2;
            ans=ans+(1<<j);
        }
        l=y;
        x=y=r;
        for(j=19;j>=0;j--){
            if (min(maxi[j][x].first,maxi[j][y].first)<=l)
                continue;
            int x2,y2;
            x2=min(maxi[j][x].first,maxi[j][y].first);
            y2=max(maxi[j][x].second,maxi[j][y].second);
            x=x2;
            y=y2;
            ans=ans+(1<<j);
        }
        printf("%d\n",ans);
    }
return 0;
}

Compilation message

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   10 |     scanf("%d%d%d",&n,&k,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
railway_trip.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   12 |         scanf("%d",&v[i]);
      |         ~~~~~^~~~~~~~~~~~
railway_trip.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |         scanf("%d%d",&l,&r);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 24 ms 16620 KB Output is correct
3 Correct 27 ms 16620 KB Output is correct
4 Correct 25 ms 16620 KB Output is correct
5 Correct 25 ms 16620 KB Output is correct
6 Correct 25 ms 16748 KB Output is correct
7 Correct 28 ms 17004 KB Output is correct
8 Correct 22 ms 16620 KB Output is correct
9 Correct 25 ms 17004 KB Output is correct
10 Correct 24 ms 16876 KB Output is correct
11 Correct 30 ms 17004 KB Output is correct
12 Correct 26 ms 17004 KB Output is correct
13 Correct 25 ms 17004 KB Output is correct
14 Correct 26 ms 17004 KB Output is correct
15 Correct 26 ms 17004 KB Output is correct
16 Correct 28 ms 17004 KB Output is correct
17 Correct 27 ms 17004 KB Output is correct
18 Correct 26 ms 17004 KB Output is correct
19 Correct 27 ms 17004 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 18284 KB Output is correct
2 Correct 205 ms 18284 KB Output is correct
3 Correct 203 ms 18284 KB Output is correct
4 Correct 202 ms 18284 KB Output is correct
5 Correct 199 ms 18284 KB Output is correct
6 Correct 204 ms 18316 KB Output is correct
7 Correct 197 ms 18284 KB Output is correct
8 Correct 222 ms 18284 KB Output is correct
9 Correct 280 ms 18468 KB Output is correct
10 Correct 268 ms 18284 KB Output is correct
11 Correct 270 ms 18412 KB Output is correct
12 Correct 268 ms 18284 KB Output is correct
13 Correct 272 ms 18420 KB Output is correct
14 Correct 218 ms 18284 KB Output is correct
15 Correct 184 ms 18156 KB Output is correct
16 Correct 175 ms 18232 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 18540 KB Output is correct
2 Correct 149 ms 18540 KB Output is correct
3 Correct 148 ms 18284 KB Output is correct
4 Correct 151 ms 18412 KB Output is correct
5 Correct 267 ms 18296 KB Output is correct
6 Correct 215 ms 18796 KB Output is correct
7 Correct 219 ms 18796 KB Output is correct
8 Correct 225 ms 18540 KB Output is correct
9 Correct 211 ms 18796 KB Output is correct
10 Correct 210 ms 18796 KB Output is correct
11 Correct 218 ms 18668 KB Output is correct
12 Correct 210 ms 18668 KB Output is correct
13 Correct 216 ms 18668 KB Output is correct
14 Correct 220 ms 18924 KB Output is correct
15 Correct 219 ms 18796 KB Output is correct
16 Correct 218 ms 18924 KB Output is correct
17 Correct 176 ms 18668 KB Output is correct
18 Correct 199 ms 18796 KB Output is correct
19 Correct 190 ms 18796 KB Output is correct
20 Correct 158 ms 18540 KB Output is correct
21 Correct 144 ms 18412 KB Output is correct
22 Correct 144 ms 18412 KB Output is correct
23 Correct 144 ms 18412 KB Output is correct