oj.uz

Submission #729017

# Submission time Handle Problem Language Result Execution time Memory
729017 2023-04-23T11:54:32 Z MilosMilutinovic Bitaro's travel (JOI23_travel) C++14
100 / 100
 483 ms 46972 KB 
#include <bits/stdc++.h>
using namespace std;
 
int n,x[200005],q,mxl[200005][25],mxr[200005][25],logs[200005];
 
int findbst(int s)
{
    int idx=lower_bound(x+1,x+n+1,s)-x;
    idx=max(idx,1);idx=min(idx,n);
    if(abs(x[idx]-s)<abs(x[max(idx-1,1)]-s)) return idx;
    else return max(idx-1,1);
}
 
int getL(int l,int r)
{
    int k=logs[r-l+1];
    return max(mxl[l][k],mxl[r-(1<<k)+1][k]);
}
int getR(int l,int r)
{
    int k=logs[r-l+1];
    return max(mxr[l][k],mxr[r-(1<<k)+1][k]);
}
 
signed main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&x[i]);
    for(int i=2;i<=n;i++) logs[i]=logs[i>>1]+1;
    for(int i=2;i<=n;i++) mxl[i][0]=2*x[i]-x[i-1];
    for(int i=1;i<n;i++) mxr[i][0]=x[i+1]-2*x[i];
    for(int j=1;j<25;j++)
        for(int i=2;i+(1<<j)<=n+1;i++)
            mxl[i][j]=max(mxl[i][j-1],mxl[i+(1<<(j-1))][j-1]);
    for(int j=1;j<25;j++)
        for(int i=1;i+(1<<j)<=n;i++)
            mxr[i][j]=max(mxr[i][j-1],mxr[i+(1<<(j-1))][j-1]);
    scanf("%d",&q);
    while(q--)
    {
        int s;scanf("%d",&s);
        int l=findbst(s),r=l,idx=l;
        long long ans=abs(s-x[l]);
        while(l!=1||r!=n)
        {
            if(l==1)
            {
                ans+=abs(x[idx]-x[n]);r=n;break;
            }
            if(r==n)
            {
                ans+=abs(x[1]-x[idx]);l=1;break;
            }
            if(l==idx)
            {
                int low=2,high=l,p=l;
                while(low<=high)
                {
                    int mid=(low+high)/2;
                    if(getL(mid,l)-x[r+1]<=0) p=mid-1,high=mid-1;
                    else low=mid+1;
                }
                ans+=x[l]-x[p];l=p;
                ans+=x[r+1]-x[p];idx=r+1;r=idx;
            }
            else
            {
                assert(r==idx);
                int low=r,high=n-1,p=r;
                while(low<=high)
                {
                    int mid=(low+high)/2;
                    if(getR(r,mid)+x[l-1]<0) p=mid+1,low=mid+1;
                    else high=mid-1;
                }
                ans+=x[p]-x[r];r=p;
                ans+=x[p]-x[l-1];idx=l-1;l=idx;
            }
        }
        printf("%lld\n",ans);
    }
}

Compilation message

travel.cpp: In function 'int main()':
travel.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
travel.cpp:28:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     for(int i=1;i<=n;i++)scanf("%d",&x[i]);
      |                          ~~~~~^~~~~~~~~~~~
travel.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
travel.cpp:41:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         int s;scanf("%d",&s);
      |               ~~~~~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 712 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 1 ms 724 KB Output is correct
16 Correct 1 ms 724 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 712 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 1 ms 724 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 90 ms 41292 KB Output is correct
18 Correct 97 ms 41528 KB Output is correct
19 Correct 92 ms 42408 KB Output is correct
20 Correct 89 ms 41816 KB Output is correct
21 Correct 98 ms 41644 KB Output is correct
22 Correct 99 ms 42628 KB Output is correct
23 Correct 115 ms 42340 KB Output is correct
24 Correct 102 ms 41964 KB Output is correct
25 Correct 107 ms 42388 KB Output is correct
26 Correct 89 ms 42204 KB Output is correct
27 Correct 88 ms 41572 KB Output is correct
28 Correct 125 ms 42448 KB Output is correct
29 Correct 93 ms 41456 KB Output is correct
30 Correct 99 ms 41436 KB Output is correct
31 Correct 91 ms 41996 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 237 ms 44704 KB Output is correct
8 Correct 210 ms 44660 KB Output is correct
9 Correct 232 ms 44540 KB Output is correct
10 Correct 206 ms 44720 KB Output is correct
11 Correct 200 ms 44572 KB Output is correct
12 Correct 237 ms 44760 KB Output is correct
13 Correct 56 ms 3092 KB Output is correct
14 Correct 42 ms 1276 KB Output is correct
15 Correct 254 ms 43352 KB Output is correct
16 Correct 250 ms 45268 KB Output is correct
17 Correct 236 ms 45664 KB Output is correct
18 Correct 56 ms 3800 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 712 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 1 ms 724 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 90 ms 41292 KB Output is correct
18 Correct 97 ms 41528 KB Output is correct
19 Correct 92 ms 42408 KB Output is correct
20 Correct 89 ms 41816 KB Output is correct
21 Correct 98 ms 41644 KB Output is correct
22 Correct 99 ms 42628 KB Output is correct
23 Correct 115 ms 42340 KB Output is correct
24 Correct 102 ms 41964 KB Output is correct
25 Correct 107 ms 42388 KB Output is correct
26 Correct 89 ms 42204 KB Output is correct
27 Correct 88 ms 41572 KB Output is correct
28 Correct 125 ms 42448 KB Output is correct
29 Correct 93 ms 41456 KB Output is correct
30 Correct 99 ms 41436 KB Output is correct
31 Correct 91 ms 41996 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 237 ms 44704 KB Output is correct
39 Correct 210 ms 44660 KB Output is correct
40 Correct 232 ms 44540 KB Output is correct
41 Correct 206 ms 44720 KB Output is correct
42 Correct 200 ms 44572 KB Output is correct
43 Correct 237 ms 44760 KB Output is correct
44 Correct 56 ms 3092 KB Output is correct
45 Correct 42 ms 1276 KB Output is correct
46 Correct 254 ms 43352 KB Output is correct
47 Correct 250 ms 45268 KB Output is correct
48 Correct 236 ms 45664 KB Output is correct
49 Correct 56 ms 3800 KB Output is correct
50 Correct 483 ms 46972 KB Output is correct
51 Correct 451 ms 46736 KB Output is correct
52 Correct 400 ms 46940 KB Output is correct
53 Correct 417 ms 45204 KB Output is correct
54 Correct 350 ms 46876 KB Output is correct
55 Correct 349 ms 46928 KB Output is correct
56 Correct 214 ms 46180 KB Output is correct
57 Correct 219 ms 46464 KB Output is correct
58 Correct 201 ms 46824 KB Output is correct