제출 #1243877

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243877		AlperenT_	나일강 (IOI24_nile)	C++20	100 / 100	391 ms	64864 KiB

nile

#include "nile.h"
#include <bits/stdc++.h> 
#pragma GCC optimize("O3,unroll-loops") 
#pragma GCC target("avx2") 
#define pb push_back
#define F first
#define pii pair<int,int> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long 
using namespace std ;
const ll maxn = 1e5 + 100 , inf = 1e18 , mod = 998244353;
ll dp[maxn] ;int d;
vector <int> up[maxn] , up2[maxn] ;
vector <pii> vec , que;
vector <ll> ans ;

struct node{
  ll a[2][2][2][2] ;
  node(){
    rep(a0,0,1)rep(a1,0,1)rep(a2,0,1)rep(a3,0,1)a[a0][a1][a2][a3] = 0; 
  }
};
inline void mx(ll &x , ll y){
  x = max(x,y) ;
}
node seg[4*maxn] ;

void upd(int x,int p = 1 , int l = 0 , int r= sz(vec)-1){
  int mid = (l+r)/2 , pl=p<<1 , pr=p<<1|1;
  if(x > r || x < l)return ;
  if(l == r){
  rep(i,0,1)rep(j,0,1)rep(k,0,1)rep(z,0,1)seg[p].a[i][j][k][z] = -inf ;
    seg[p].a[0][0][0][1]= 0 ;
    seg[p].a[1][0][0][0]= 0 ;
    seg[p].a[0][0][0][0]= 0 ;
    return; 
  }
  upd(x,pl,l,mid);upd(x,pr,mid+1,r); 
  rep(i1,0,1){
    rep(j1,0,1){
      rep(i2,0,1){
        rep(j2,0,1){
          seg[p].a[i1][j1][i2][j2] = max(0ll ,seg[pl].a[i1][j1][0][0] + seg[pr].a[0][0][i2][j2]) ;
          if(vec[mid+1].F-vec[mid].F <= d){
            ll w = vec[mid].S + vec[mid+1].S;
           // if(l==0 && r==2 && i1+j2+j1+i2==0)cout <<vec[mid].S << " " << vec[mid+1].S <<"<--\n"; 
            mx(seg[p].a[i1][j1][i2][j2],seg[pl].a[i1][j1][0][1] + seg[pr].a[1][0][i2][j2] + w);
            mx(seg[p].a[i1][j1][i2][j2],seg[pl].a[i1][j1][0][1] + seg[pr].a[1][0][i2][j2] + w);
          }
          if(mid+1 != r && vec[mid+2].F-vec[mid].F <= d){
            ll w = vec[mid].S + vec[mid+2].S;
            mx(seg[p].a[i1][j1][i2][j2],seg[pl].a[i1][j1][0][1] + seg[pr].a[0][1][i2][j2] + w);
            mx(seg[p].a[i1][j1][i2][j2],seg[pl].a[i1][j1][0][1] + seg[pr].a[0][1][i2][j2] + w);
          }
          if(l!=mid && vec[mid+1].F-vec[mid-1].F <= d){
            ll w = vec[mid-1].S + vec[mid+1].S;
        //    if(l==0 && r==4 && i1+j2+j1+i2==0)cout <<seg[pl].a[i1][j1][1][0] << " " << seg[pr].a[1][0][i2][j2] <<"<--\n"; 
            mx(seg[p].a[i1][j1][i2][j2],seg[pl].a[i1][j1][1][0] + seg[pr].a[1][0][i2][j2] + w);
            mx(seg[p].a[i1][j1][i2][j2],seg[pl].a[i1][j1][1][0] + seg[pr].a[1][0][i2][j2] + w);
          }
        }
      }
    }
  }
  if(r-l+1==2){
    rep(i1,0,1){
    rep(j1,0,1){
      rep(i2,0,1){
        rep(j2,0,1){
          if(i1+i2==2 || j2+j1==2)seg[p].a[i1][j1][i2][j2] = -inf ;
        }}}}
  }
  if(r-l+1==3){
rep(i1,0,1){
    rep(j1,0,1){
      rep(i2,0,1){
        rep(j2,0,1){
          if(j1+i2==2)seg[p].a[i1][j1][i2][j2] = -inf ;
        }}}}
  }
}

std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,std::vector<int> B, std::vector<int> E) {
  int n =  sz(W) ;
  ll sm =0 ; 
  rep(i , 0 ,n-1){
    vec.pb({W[i] , A[i]-B[i]}) ; 
    sm += A[i]; 
  }
  rep(i , 0 ,sz(E)-1){
    que.pb({E[i] , i}) ;
    ans.pb(0);
  }
  sort(all(vec));
  sort(all(que));
  rep(i , 0 , n-2){
    int x =lower_bound(all(que) , (pii){vec[i+1].F-vec[i].F , -1}) - que.begin() ;
    up[x].pb(i); 
    if(i!=n-2){
      x =lower_bound(all(que) , (pii){vec[i+2].F-vec[i].F ,-1}) - que.begin(); 
      up2[x].pb(i);
    }
  }
  d = que[0].F ;
  rep(i , 0 ,n-1)upd(i) ;
//  rep(i,0,1)rep(j,0,1)rep(k,0,1)rep(z,0,1)cout << seg[2].a[i][j][k][z] ;
//  cout << '\n' ;
  rep(i , 0 ,sz(que)-1){
    ll mx = seg[1].a[0][0][0][0] ;
//    cout << d << " " << sm << " " << mx << "\n"; 
    ans[que[i].S] = sm - mx ;
    if(i == sz(que)-1)break ;
    d = que[i+1].F ;  
    for(int x : up[i+1])upd(x);
    for(int x : up2[i+1])upd(x);
  }
  return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15
• Subtask 7: 18 / 18