oj.uz

Submission #992400

# Submission time Handle Problem Language Result Execution time Memory
992400 2024-06-04T11:50:03 Z shenfe1 Ants and Sugar (JOI22_sugar) C++17
16 / 100
 1855 ms 812572 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]=0;
      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]);
      for(int j=l;j<=r;j++)T.updateC(1,1,sz(vec),j,-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 105 ms 784556 KB Output is correct
2 Correct 97 ms 784516 KB Output is correct
3 Incorrect 96 ms 784464 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 104 ms 784464 KB Output is correct
2 Correct 94 ms 784496 KB Output is correct
3 Correct 108 ms 784336 KB Output is correct
4 Correct 1333 ms 800888 KB Output is correct
5 Correct 734 ms 795844 KB Output is correct
6 Correct 1444 ms 803264 KB Output is correct
7 Correct 757 ms 795848 KB Output is correct
8 Correct 1664 ms 806212 KB Output is correct
9 Correct 1434 ms 806792 KB Output is correct
10 Correct 1855 ms 806128 KB Output is correct
11 Correct 1512 ms 806596 KB Output is correct
12 Correct 664 ms 793540 KB Output is correct
13 Correct 928 ms 802768 KB Output is correct
14 Correct 1442 ms 812480 KB Output is correct
15 Correct 1515 ms 812572 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 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 105 ms 784556 KB Output is correct
2 Correct 97 ms 784516 KB Output is correct
3 Incorrect 96 ms 784464 KB Output isn't correct
4 Halted 0 ms 0 KB -