oj.uz

Submission #992391

# Submission time Handle Problem Language Result Execution time Memory
992391 2024-06-04T11:19:37 Z shenfe1 Ants and Sugar (JOI22_sugar) C++17
0 / 100
 1870 ms 806844 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);
  }
  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 136 ms 784400 KB Output is correct
2 Correct 126 ms 784488 KB Output is correct
3 Incorrect 123 ms 784464 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 784464 KB Output is correct
2 Correct 135 ms 784464 KB Output is correct
3 Correct 147 ms 784472 KB Output is correct
4 Correct 1379 ms 800932 KB Output is correct
5 Correct 769 ms 795848 KB Output is correct
6 Correct 1521 ms 803156 KB Output is correct
7 Correct 801 ms 795964 KB Output is correct
8 Correct 1870 ms 806180 KB Output is correct
9 Correct 1476 ms 806712 KB Output is correct
10 Correct 1806 ms 806292 KB Output is correct
11 Correct 1587 ms 806844 KB Output is correct
12 Incorrect 722 ms 796104 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 127 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 136 ms 784400 KB Output is correct
2 Correct 126 ms 784488 KB Output is correct
3 Incorrect 123 ms 784464 KB Output isn't correct
4 Halted 0 ms 0 KB -