oj.uz

Submission #992388

# Submission time Handle Problem Language Result Execution time Memory
992388 2024-06-04T11:15:48 Z shenfe1 Ants and Sugar (JOI22_sugar) C++17
0 / 100
 1601 ms 834592 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=1e12;
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]=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;
      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);
  }
  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 145 ms 784468 KB Output is correct
2 Correct 147 ms 784512 KB Output is correct
3 Correct 153 ms 784408 KB Output is correct
4 Correct 149 ms 784464 KB Output is correct
5 Correct 169 ms 784472 KB Output is correct
6 Incorrect 159 ms 784720 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 784464 KB Output is correct
2 Correct 158 ms 784464 KB Output is correct
3 Correct 163 ms 784724 KB Output is correct
4 Correct 1284 ms 819060 KB Output is correct
5 Correct 650 ms 809912 KB Output is correct
6 Correct 1391 ms 834384 KB Output is correct
7 Correct 658 ms 809920 KB Output is correct
8 Correct 1601 ms 834292 KB Output is correct
9 Correct 1284 ms 834592 KB Output is correct
10 Correct 1585 ms 834456 KB Output is correct
11 Correct 1269 ms 834468 KB Output is correct
12 Incorrect 593 ms 809916 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 784464 KB Output is correct
2 Incorrect 617 ms 809992 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 784468 KB Output is correct
2 Correct 147 ms 784512 KB Output is correct
3 Correct 153 ms 784408 KB Output is correct
4 Correct 149 ms 784464 KB Output is correct
5 Correct 169 ms 784472 KB Output is correct
6 Incorrect 159 ms 784720 KB Output isn't correct
7 Halted 0 ms 0 KB -