Submission #991833

#	Time	Username	Problem	Language	Result	Execution time	Memory
991833		modwwe	Bitaro's travel (JOI23_travel)	C++17	100 / 100	163 ms	22220 KiB

travel

#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 (stderr)

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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 55 / 55