oj.uz

Submission #992401

# Submission time Handle Problem Language Result Execution time Memory
992401 2024-06-04T11:51:42 Z shenfe1 Ants and Sugar (JOI22_sugar) C++17
16 / 100
 1519 ms 806908 KB 
#include <bits/stdc++.h>
 
#pragma optimize("Ofast")
#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 ll inf=1e18;
const int mod=998244353;
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,int mod){
  if(!n)return 1;
  if(n%2==1)return a*binpow(a,n-1,mod)%mod;
  int k=binpow(a,n/2,mod);
  return k*k%mod;
}
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int rnd(int l,int r){
  return rng()%(r-l+1)+l;
}
 
 
int q,L;
 
struct segtree{
  struct node{
    int dp[2][2][2];
    int addC,addCD;
    node(){
      addC=0;
      addCD=0;
      for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
          for(int k=0;k<2;k++){
            dp[i][j][k]=-inf;
          }
        }
      }
    }
  }t[MAX*20];
 
  node mrg(node a,node b){
    node res;
    for(int i=0;i<2;i++){
      for(int j=0;j<2;j++){
        for(int k=0;k<2;k++){
          res.dp[i][j][k]=max(res.dp[i][j][k],a.dp[i][j][k]);
          res.dp[i][j][k]=max(res.dp[i][j][k],b.dp[i][j][k]);
        }
      }
    }
    for(int i=0;i<2;i++){
      for(int j=0;j<2;j++){
        for(int m=0;m<2;m++){
          for(int k1=0;k1<2;k1++){
            for(int k2=0;k2<2;k2++){
              res.dp[i][j][min(1ll,k1+k2)]=max(res.dp[i][j][min(1ll,k1+k2)],a.dp[i][m][k1]+b.dp[(m^1)][j][k2]);
            }
          }
        }
      }
    }
    // cout<<res.dp[1][0][1]<<"\n";
    return res;
  }
 
  void pushCD(int v,int x){
    t[v].addCD+=x;
    for(int k=0;k<2;k++){
      t[v].dp[0][0][k]+=x;
      t[v].dp[1][1][k]-=x;
    }
  }
 
  void pushC(int v,int x){
    t[v].addC+=x;
    for(int i=0;i<2;i++){
      for(int j=0;j<2;j++){
        t[v].dp[i][j][1]+=x;
      }
    }
  }
 
  void push(int v){
    pushCD(2*v,t[v].addCD);
    pushCD(2*v+1,t[v].addCD);
    t[v].addCD=0;
    pushC(2*v,t[v].addC);
    pushC(2*v+1,t[v].addC);
    t[v].addC=0;
  }
 
  void build(int v,int tl,int tr){
    if(tl==tr){
      t[v].dp[1][1][0]=t[v].dp[0][0][1]=t[v].dp[1][0][1]=0;
      return;
    }
    int tm=(tl+tr)/2;
    build(2*v,tl,tm);
    build(2*v+1,tm+1,tr);
    t[v]=mrg(t[2*v],t[2*v+1]);
  }
 
  void updateCD(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){
      pushCD(v,x);
      return;
    }
    push(v);
    int tm=(tl+tr)/2;
    updateCD(2*v,tl,tm,l,r,x);
    updateCD(2*v+1,tm+1,tr,l,r,x);
    t[v]=mrg(t[2*v],t[2*v+1]);
  }
 
  void updateC(int v,int tl,int tr,int pos,int x){
    if(tl==tr){
      t[v].dp[0][0][1]+=x;
      t[v].dp[1][0][1]+=x;
      return;
    }
    push(v);
    int tm=(tl+tr)/2;
    if(pos<=tm)updateC(2*v,tl,tm,pos,x);
    else updateC(2*v+1,tm+1,tr,pos,x);
    t[v]=mrg(t[2*v],t[2*v+1]);
  }
 
  void updateC(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){
      pushC(v,x);
      return;
    }
    push(v);
    int tm=(tl+tr)/2;
    updateC(2*v,tl,tm,l,r,x);
    updateC(2*v+1,tm+1,tr,l,r,x);
    t[v]=mrg(t[2*v],t[2*v+1]);
  }
}T;
 
int t[MAX],x[MAX],a[MAX];
 
void solve(){
  cin>>q>>L;  
  vector<int> vec;
  for(int i=1;i<=q;i++){
    cin>>t[i]>>x[i]>>a[i];
    // vec.pb(x[i]);
    // vec.pb(x[i]-L);
    // vec.pb(x[i]+L);
    // vec.pb(x[i]+1);
    // vec.pb(x[i]-1);
  }
  for(int i=0;i<=q;i++)vec.pb(i);
  sort(all(vec));
  vec.erase(unique(all(vec)),vec.end());
  int sum=0;
  T.build(1,1,sz(vec));
  // cout<<T.t[1].dp[1][0][1]<<"\n";
  for(int i=1;i<=q;i++){
    if(t[i]==1){
      sum+=a[i];
      int pos=lb(all(vec),x[i])-vec.begin();
      T.updateC(1,1,sz(vec),pos,a[i]);
      T.updateCD(1,1,sz(vec),pos+1,sz(vec),a[i]);
    }
    else{
      int l=lb(all(vec),x[i]-L)-vec.begin();
      int r=ub(all(vec),x[i]+L)-vec.begin()-1;
      T.updateC(1,1,sz(vec),l,r,-a[i]);
      T.updateCD(1,1,sz(vec),r+1,sz(vec),-a[i]);
    }
    cout<<sum-max({T.t[1].dp[1][0][0],T.t[1].dp[1][0][1],0ll})<<"\n";
  }
}
 
signed main(){
  //  freopen("valleys.in","r",stdin);
  //  freopen("valleys.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

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 784468 KB Output is correct
2 Correct 103 ms 784464 KB Output is correct
3 Incorrect 116 ms 784468 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 784468 KB Output is correct
2 Correct 99 ms 784444 KB Output is correct
3 Correct 101 ms 784464 KB Output is correct
4 Correct 1045 ms 801016 KB Output is correct
5 Correct 558 ms 795808 KB Output is correct
6 Correct 1195 ms 803264 KB Output is correct
7 Correct 544 ms 795844 KB Output is correct
8 Correct 1519 ms 806152 KB Output is correct
9 Correct 1109 ms 806668 KB Output is correct
10 Correct 1454 ms 806324 KB Output is correct
11 Correct 1135 ms 806908 KB Output is correct
12 Correct 561 ms 793544 KB Output is correct
13 Correct 728 ms 796864 KB Output is correct
14 Correct 1127 ms 803436 KB Output is correct
15 Correct 1158 ms 803260 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 102 ms 784464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 784468 KB Output is correct
2 Correct 103 ms 784464 KB Output is correct
3 Incorrect 116 ms 784468 KB Output isn't correct
4 Halted 0 ms 0 KB -