Submission #991830

#	Time	Username	Problem	Language	Result	Execution time	Memory
991830		modwwe	Bitaro's travel (JOI23_travel)	C++17	100 / 100	159 ms	45268 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(long long int, long long int, long long int, long long int, long long int, long long int)':
travel.cpp:77:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |       int mid=l+r>>1;
      |               ~^~
travel.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
travel.cpp:87:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |       int mid=l+r>>1;
      |               ~^~
travel.cpp: In function 'void solve1()':
travel.cpp:108:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |             int mid=l+r>>1;
      |                     ~^~
travel.cpp:119:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  119 |             int mid=l+r>>1;
      |                     ~^~
travel.cpp: In function 'void phongbeo()':
travel.cpp:137:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  137 |  for(int i=1;i<=n;i++)
      |  ^~~
travel.cpp:139:6: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  139 |      for(int i=2;i<=n;i++)
      |      ^~~
travel.cpp:141:6: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  141 |      for(int i=1;i<18;i++)
      |      ^~~
travel.cpp:144:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  144 |         build(1,1,n);
      |         ^~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 55 / 55