oj.uz

Submission #950478

# Submission time Handle Problem Language Result Execution time Memory
950478 2024-03-20T10:50:31 Z vjudge1 Triple Jump (JOI19_jumps) C++17
100 / 100
 2532 ms 148268 KB 
#include <bits/stdc++.h>

#pragma optimize("Ofast,unroll-loops")
#pragma target("avx2")

using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mem(a,i) memset(a,i,sizeof(a))
#define sz(s) (int)s.size()
#define y1 yy
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound
#define gcd(a,b) __gcd(a,b)
#define in insert
#define int ll

const int MAX=5e5+10;
const int B=500;
const int maxB=1000;
const int N=104;
const int block=450;
const int inf=2e9;  
const int mod=1e9+7;
const int mod1=1e9+9;
const ld eps=1e-9;

int dx[8]={1,0,-1,0,1,-1,-1,1};
int dy[8]={0,1,0,-1,1,-1,1,-1};

int binpow(int a,int n){
  if(!n)return 1;
  if(n%2==1)return a*binpow(a,n-1)%mod;
  int k=binpow(a,n/2);
  return k*k%mod;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int l[MAX],r[MAX];
int n,q;
int a[MAX];
int ans[MAX];

struct segtree{
  int t[4*MAX];
  int d[4*MAX];
  int s[4*MAX];
  int add[4*MAX];
  
  segtree(){
    mem(t,0);
    mem(s,0);
    mem(d,0);
    mem(add,-1);
  }

  void build(int v,int tl,int tr,int (&a)[]){
    if(tl==tr){
      d[v]=a[tl];
      t[v]=a[tl];
      return;
    }
    int tm=(tl+tr)/2;
    build(2*v,tl,tm,a);
    build(2*v+1,tm+1,tr,a);
    t[v]=max(t[2*v],t[2*v+1]);
    d[v]=max(d[2*v],d[2*v+1]);
  }

  void push(int v){
    if(add[v]==-1)return;
    t[2*v]=add[v]+d[2*v];
    t[2*v+1]=add[v]+d[2*v+1];
    s[2*v]=s[2*v+1]=add[v];
    add[2*v]=add[2*v+1]=add[v];
    add[v]=-1;
  }

  void update(int v,int tl,int tr,int l,int r,int x){
    if(l>r||tl>r||l>tr)return;
    if(l<=tl&&tr<=r){
      t[v]=x+d[v];
      s[v]=x;
      add[v]=x;
      return;
    }
    push(v);
    int tm=(tl+tr)/2;
    update(2*v,tl,tm,l,r,x);
    update(2*v+1,tm+1,tr,l,r,x);
    s[v]=max(s[2*v],s[2*v+1]);
    t[v]=max(t[2*v],t[2*v+1]);
  }

  int get(int v,int tl,int tr,int l,int r){
    if(l>r||tl>r||l>tr)return 0;
    if(l<=tl&&tr<=r)return t[v];
    push(v);
    int tm=(tl+tr)/2;
    return max(get(2*v,tl,tm,l,r),get(2*v+1,tm+1,tr,l,r));
  }
}t;

vector<int> seg[MAX];
vector<pii> zap[MAX];

void solve(){
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>a[i];
  }
  t.build(1,1,n,a);
  stack<int> st;
  for(int i=1;i<=n;i++){
    while(!st.empty()&&a[i]>a[st.top()]){
      st.pop();
    }
    if(!st.empty())l[i]=st.top();
    st.push(i);
  }
  while(!st.empty())st.pop();
  for(int i=n;i>=1;i--){
    while(!st.empty()&&a[i]>a[st.top()]){
      st.pop();
    }
    if(!st.empty())r[i]=st.top();
    st.push(i);
  }
  for(int i=1;i<=n;i++){
    if(r[i]){
      // cout<<i<<" "<<r[i]<<"\n";
      seg[i].pb(r[i]);
    }
    if(l[i]){
      // cout<<l[i]<<" "<<i<<"\n";
      seg[l[i]].pb(i);
    }
  }
  cin>>q;
  for(int i=1;i<=q;i++){
    int l,r;
    cin>>l>>r;
    zap[l].pb({r,i});
  }
  for(int i=n;i>=1;i--){
    for(auto r:seg[i]){
      int r1=r+(r-i);
      if(r1<=n){
        int s=a[i]+a[r];
        int lef=r1,rig=n,res=-1;
        while(lef<=rig){
          int mid=(lef+rig)/2;
          if(t.get(1,1,n,mid,mid)-a[mid]<s){
            lef=mid+1;
            res=mid;
          }
          else rig=mid-1;
        }
        t.update(1,1,n,r1,res,s);
      }
    }
    for(auto [r,num]:zap[i]){
      ans[num]=t.get(1,1,n,i,r);
    }
  }
  for(int i=1;i<=q;i++)cout<<ans[i]<<"\n";
}

signed main(){
  // freopen("triangles.in","r",stdin);
  // freopen("triangles.out","w",stdout);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  // prec();
  int t=1;
  // cin>>t;
  while(t--){
    solve();
  }
}

Compilation message

jumps.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize("Ofast,unroll-loops")
      | 
jumps.cpp:4: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    4 | #pragma target("avx2")
      |

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 92760 KB Output is correct
2 Correct 14 ms 92764 KB Output is correct
3 Correct 14 ms 90716 KB Output is correct
4 Correct 14 ms 92976 KB Output is correct
5 Correct 15 ms 92764 KB Output is correct
6 Correct 16 ms 92764 KB Output is correct
7 Correct 15 ms 92760 KB Output is correct
8 Correct 15 ms 92916 KB Output is correct
9 Correct 15 ms 92764 KB Output is correct
10 Correct 15 ms 92764 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 92760 KB Output is correct
2 Correct 14 ms 92764 KB Output is correct
3 Correct 14 ms 90716 KB Output is correct
4 Correct 14 ms 92976 KB Output is correct
5 Correct 15 ms 92764 KB Output is correct
6 Correct 16 ms 92764 KB Output is correct
7 Correct 15 ms 92760 KB Output is correct
8 Correct 15 ms 92916 KB Output is correct
9 Correct 15 ms 92764 KB Output is correct
10 Correct 15 ms 92764 KB Output is correct
11 Correct 195 ms 113448 KB Output is correct
12 Correct 196 ms 111368 KB Output is correct
13 Correct 189 ms 113488 KB Output is correct
14 Correct 208 ms 113480 KB Output is correct
15 Correct 186 ms 113628 KB Output is correct
16 Correct 196 ms 113008 KB Output is correct
17 Correct 189 ms 112976 KB Output is correct
18 Correct 196 ms 112652 KB Output is correct
19 Correct 190 ms 113468 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 735 ms 106588 KB Output is correct
2 Correct 381 ms 107020 KB Output is correct
3 Correct 341 ms 105404 KB Output is correct
4 Correct 774 ms 106596 KB Output is correct
5 Correct 788 ms 106804 KB Output is correct
6 Correct 729 ms 106796 KB Output is correct
7 Correct 721 ms 106588 KB Output is correct
8 Correct 744 ms 106580 KB Output is correct
9 Correct 723 ms 106592 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 92760 KB Output is correct
2 Correct 14 ms 92764 KB Output is correct
3 Correct 14 ms 90716 KB Output is correct
4 Correct 14 ms 92976 KB Output is correct
5 Correct 15 ms 92764 KB Output is correct
6 Correct 16 ms 92764 KB Output is correct
7 Correct 15 ms 92760 KB Output is correct
8 Correct 15 ms 92916 KB Output is correct
9 Correct 15 ms 92764 KB Output is correct
10 Correct 15 ms 92764 KB Output is correct
11 Correct 195 ms 113448 KB Output is correct
12 Correct 196 ms 111368 KB Output is correct
13 Correct 189 ms 113488 KB Output is correct
14 Correct 208 ms 113480 KB Output is correct
15 Correct 186 ms 113628 KB Output is correct
16 Correct 196 ms 113008 KB Output is correct
17 Correct 189 ms 112976 KB Output is correct
18 Correct 196 ms 112652 KB Output is correct
19 Correct 190 ms 113468 KB Output is correct
20 Correct 735 ms 106588 KB Output is correct
21 Correct 381 ms 107020 KB Output is correct
22 Correct 341 ms 105404 KB Output is correct
23 Correct 774 ms 106596 KB Output is correct
24 Correct 788 ms 106804 KB Output is correct
25 Correct 729 ms 106796 KB Output is correct
26 Correct 721 ms 106588 KB Output is correct
27 Correct 744 ms 106580 KB Output is correct
28 Correct 723 ms 106592 KB Output is correct
29 Correct 2477 ms 140596 KB Output is correct
30 Correct 1504 ms 145280 KB Output is correct
31 Correct 1434 ms 141532 KB Output is correct
32 Correct 2532 ms 144496 KB Output is correct
33 Correct 2526 ms 144500 KB Output is correct
34 Correct 2471 ms 143220 KB Output is correct
35 Correct 2487 ms 142976 KB Output is correct
36 Correct 2466 ms 142976 KB Output is correct
37 Correct 2460 ms 143984 KB Output is correct
38 Correct 2266 ms 147356 KB Output is correct
39 Correct 2249 ms 147288 KB Output is correct
40 Correct 2238 ms 144808 KB Output is correct
41 Correct 2252 ms 144536 KB Output is correct
42 Correct 2219 ms 144548 KB Output is correct
43 Correct 2221 ms 145568 KB Output is correct
44 Correct 2336 ms 147372 KB Output is correct
45 Correct 2251 ms 147360 KB Output is correct
46 Correct 2236 ms 145232 KB Output is correct
47 Correct 2290 ms 144912 KB Output is correct
48 Correct 2290 ms 145060 KB Output is correct
49 Correct 2322 ms 146312 KB Output is correct
50 Correct 2348 ms 148268 KB Output is correct
51 Correct 2338 ms 147932 KB Output is correct
52 Correct 2333 ms 146040 KB Output is correct
53 Correct 2301 ms 146024 KB Output is correct
54 Correct 2368 ms 146036 KB Output is correct
55 Correct 2430 ms 146940 KB Output is correct