oj.uz

Submission #991833

# Submission time Handle Problem Language Result Execution time Memory
991833 2024-06-03T08:30:26 Z modwwe Bitaro's travel (JOI23_travel) C++17
100 / 100
 163 ms 22220 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
//#define int long long
//#define ll long long
#define down cout<<'\n';
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
void phongbeo();
const int mod2=998244353;
const int  mod1=998244353;
struct icd
{
    int a,b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,b,c,d;
};
struct ie
{
    int a,b,c, d,e,f;

};
int n,m,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l;
int  i,s10,s12;
int el=29;
main()
{
#ifndef ONLINE_JUDGE
//fin(task),fou(task);
#endif
    NHP
    /// cin>>s1;
    ///modwwe
    phongbeo();
}
int t[800001];
int st[18][200001];
int a[200001];
int dp[200001];
void build(int node,int l,int r)
{
    t[node]=-1;
    if(l==r)
    {
        t[node]=0;
        return;
    }
}
void ff(int x)
{
    for(int i=x*2; i<=x*2+1; i++)
        t[i]=t[x];
    t[x]=-1;
}
void upd(int node,int l,int r,int l1,int r1,int c)
{
    if(l>r1||r<l1) return;
    if(l>=l1&&r<=r1)
    {
        t[node]=c;
        return;
    }
    int mid=l+r>>1;
    if(t[node]!=-1)
        ff(node);
    upd(node<<1,l,mid,l1,r1,c);
    upd(node<<1|1,mid+1,r,l1,r1,c);
}
int get(int node,int l,int r,int l1,int r1)
{
    if(l>r1||r<l1) return 0;
    if(l>=l1&&r<=r1) return t[node];
    int mid=l+r>>1;
    if(t[node]!=-1)
        ff(node);
    return get(node<<1,l,mid,l1,r1)+get(node<<1|1,mid+1,r,l1,r1);
}
int get_rmq(int l,int r)
{
    int k=log2(r-l+1);
    return max(st[k][l],st[k][r-(1<<k)+1]);
}
void solve1()
{
    dp[n]=0;
///x<=y<=z
///y-x<=z-y
///2y<=z+x
    for(int i=n-1; i>=2; --i)
    {
        l=1;
        r=i-1;
        while(l<=r)
        {
            int mid=l+r>>1;
            if(2*a[i]<=a[i+1]+a[mid])r=mid-1;
            else l=mid+1;
        }
        r++;
        s2=r;
        l=2;
        ///ax-a(x-1)>a(i+1)-ax
        ///2ax-a(x-1)>a(i+1)
        while(l<=r)
        {
            int mid=l+r>>1;
            if(get_rmq(mid,s2)>a[i+1]) l=mid+1;
            else r=mid-1;
        }
        s5=(a[i]-a[r])*2;
        s4=get(1,1,n,r-1,r-1);
        dp[i]=s5+s4;
        if(r==1)
            dp[i]=dp[i]-a[n]+a[1];
        upd(1,1,n,s2,n,dp[i]);
        dp[i]+=a[n]-a[i];

    }
}
vector<int> v;
void phongbeo()
{
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>a[i],v.pb(a[i]);
    for(int i=2; i<=n; i++)
        st[0][i]=a[i]*2-a[i-1];
    for(int i=1; i<18; i++)
        for(int j=1; j<=n; j++)
            st[i][j]=max(st[i-1][j],st[i-1][j+(1<<(i-1))]);
    build(1,1,n);
    solve1();
    s6=a[n]-a[1];
    cin>>m;
    for(int i=1; i<=m; i++)
    {
        cin>>l;
        dem=0;
        if(l>=a[n])
        {
            // cout<<l,down
            dem=l-a[n];
            l=n-1;
        }
        else if(l<=a[1])
        {
            dem=a[1]-l;
            l=0;
        }
        else
        {
            s2=lower_bound(v.begin(),v.end(),l)-v.begin();
            s3=v[s2];
            s4=v[s2-1];
            dem=min(l-s4,s3-l);
            if(l-s4>s3-l)
            {
                l=s2;
            }
            else
                l=s2-1;
        }
        cout<<dem+dp[l+1]+s6,down//<<" cucu",down

    }
}

Compilation message

travel.cpp:45:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   45 | main()
      | ^~~~
travel.cpp: In function 'void upd(int, int, int, int, int, int)':
travel.cpp:82:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |     int mid=l+r>>1;
      |             ~^~
travel.cpp: In function 'int get(int, int, int, int, int)':
travel.cpp:92:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |     int mid=l+r>>1;
      |             ~^~
travel.cpp: In function 'void solve1()':
travel.cpp:114:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |             int mid=l+r>>1;
      |                     ~^~
travel.cpp:125:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  125 |             int mid=l+r>>1;
      |                     ~^~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Correct 2 ms 16732 KB Output is correct
5 Correct 2 ms 16732 KB Output is correct
6 Correct 2 ms 16732 KB Output is correct
7 Correct 2 ms 16732 KB Output is correct
8 Correct 1 ms 16732 KB Output is correct
9 Correct 2 ms 16732 KB Output is correct
10 Correct 2 ms 16732 KB Output is correct
11 Correct 2 ms 16732 KB Output is correct
12 Correct 2 ms 16732 KB Output is correct
13 Correct 2 ms 16732 KB Output is correct
14 Correct 2 ms 16732 KB Output is correct
15 Correct 2 ms 16728 KB Output is correct
16 Correct 2 ms 16732 KB Output is correct
17 Correct 100 ms 19860 KB Output is correct
18 Correct 103 ms 19824 KB Output is correct
19 Correct 100 ms 19860 KB Output is correct
20 Correct 97 ms 19912 KB Output is correct
21 Correct 92 ms 19920 KB Output is correct
22 Correct 100 ms 19920 KB Output is correct
23 Correct 93 ms 19920 KB Output is correct
24 Correct 85 ms 19916 KB Output is correct
25 Correct 82 ms 19856 KB Output is correct
26 Correct 84 ms 19916 KB Output is correct
27 Correct 85 ms 19912 KB Output is correct
28 Correct 81 ms 19872 KB Output is correct
29 Correct 94 ms 19912 KB Output is correct
30 Correct 97 ms 19916 KB Output is correct
31 Correct 91 ms 19924 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Correct 2 ms 16732 KB Output is correct
5 Correct 2 ms 16728 KB Output is correct
6 Correct 2 ms 16732 KB Output is correct
7 Correct 107 ms 21376 KB Output is correct
8 Correct 117 ms 21196 KB Output is correct
9 Correct 108 ms 21396 KB Output is correct
10 Correct 116 ms 21376 KB Output is correct
11 Correct 139 ms 21192 KB Output is correct
12 Correct 118 ms 21384 KB Output is correct
13 Correct 29 ms 18692 KB Output is correct
14 Correct 19 ms 17376 KB Output is correct
15 Correct 140 ms 21636 KB Output is correct
16 Correct 132 ms 21648 KB Output is correct
17 Correct 136 ms 21632 KB Output is correct
18 Correct 33 ms 18664 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16732 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 2 ms 16732 KB Output is correct
4 Correct 2 ms 16732 KB Output is correct
5 Correct 2 ms 16732 KB Output is correct
6 Correct 2 ms 16732 KB Output is correct
7 Correct 2 ms 16732 KB Output is correct
8 Correct 1 ms 16732 KB Output is correct
9 Correct 2 ms 16732 KB Output is correct
10 Correct 2 ms 16732 KB Output is correct
11 Correct 2 ms 16732 KB Output is correct
12 Correct 2 ms 16732 KB Output is correct
13 Correct 2 ms 16732 KB Output is correct
14 Correct 2 ms 16732 KB Output is correct
15 Correct 2 ms 16728 KB Output is correct
16 Correct 2 ms 16732 KB Output is correct
17 Correct 100 ms 19860 KB Output is correct
18 Correct 103 ms 19824 KB Output is correct
19 Correct 100 ms 19860 KB Output is correct
20 Correct 97 ms 19912 KB Output is correct
21 Correct 92 ms 19920 KB Output is correct
22 Correct 100 ms 19920 KB Output is correct
23 Correct 93 ms 19920 KB Output is correct
24 Correct 85 ms 19916 KB Output is correct
25 Correct 82 ms 19856 KB Output is correct
26 Correct 84 ms 19916 KB Output is correct
27 Correct 85 ms 19912 KB Output is correct
28 Correct 81 ms 19872 KB Output is correct
29 Correct 94 ms 19912 KB Output is correct
30 Correct 97 ms 19916 KB Output is correct
31 Correct 91 ms 19924 KB Output is correct
32 Correct 2 ms 16732 KB Output is correct
33 Correct 2 ms 16732 KB Output is correct
34 Correct 2 ms 16732 KB Output is correct
35 Correct 2 ms 16732 KB Output is correct
36 Correct 2 ms 16728 KB Output is correct
37 Correct 2 ms 16732 KB Output is correct
38 Correct 107 ms 21376 KB Output is correct
39 Correct 117 ms 21196 KB Output is correct
40 Correct 108 ms 21396 KB Output is correct
41 Correct 116 ms 21376 KB Output is correct
42 Correct 139 ms 21192 KB Output is correct
43 Correct 118 ms 21384 KB Output is correct
44 Correct 29 ms 18692 KB Output is correct
45 Correct 19 ms 17376 KB Output is correct
46 Correct 140 ms 21636 KB Output is correct
47 Correct 132 ms 21648 KB Output is correct
48 Correct 136 ms 21632 KB Output is correct
49 Correct 33 ms 18664 KB Output is correct
50 Correct 163 ms 22204 KB Output is correct
51 Correct 153 ms 22220 KB Output is correct
52 Correct 152 ms 22140 KB Output is correct
53 Correct 148 ms 22144 KB Output is correct
54 Correct 149 ms 22160 KB Output is correct
55 Correct 142 ms 22140 KB Output is correct
56 Correct 134 ms 21908 KB Output is correct
57 Correct 136 ms 22092 KB Output is correct
58 Correct 143 ms 22144 KB Output is correct