oj.uz

Submission #992403

# Submission time Handle Problem Language Result Execution time Memory
992403 2024-06-04T11:52:24 Z shenfe1 Ants and Sugar (JOI22_sugar) C++17
100 / 100
 2336 ms 836000 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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 784468 KB Output is correct
2 Correct 119 ms 784524 KB Output is correct
3 Correct 118 ms 784396 KB Output is correct
4 Correct 108 ms 784464 KB Output is correct
5 Correct 106 ms 784472 KB Output is correct
6 Correct 106 ms 784720 KB Output is correct
7 Correct 107 ms 784720 KB Output is correct
8 Correct 104 ms 784724 KB Output is correct
9 Correct 109 ms 784720 KB Output is correct
10 Correct 119 ms 784976 KB Output is correct
11 Correct 111 ms 784808 KB Output is correct
12 Correct 113 ms 784900 KB Output is correct
13 Correct 116 ms 785176 KB Output is correct
14 Correct 109 ms 784720 KB Output is correct
15 Correct 141 ms 784888 KB Output is correct
16 Correct 110 ms 784932 KB Output is correct
17 Correct 125 ms 784728 KB Output is correct
18 Correct 109 ms 784724 KB Output is correct
19 Correct 119 ms 784832 KB Output is correct
20 Correct 111 ms 784960 KB Output is correct
21 Correct 112 ms 784992 KB Output is correct
22 Correct 110 ms 784856 KB Output is correct
23 Correct 109 ms 784792 KB Output is correct
24 Correct 110 ms 784720 KB Output is correct
25 Correct 113 ms 784976 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 784468 KB Output is correct
2 Correct 102 ms 784428 KB Output is correct
3 Correct 107 ms 784480 KB Output is correct
4 Correct 1123 ms 812260 KB Output is correct
5 Correct 617 ms 806024 KB Output is correct
6 Correct 1333 ms 826524 KB Output is correct
7 Correct 606 ms 806064 KB Output is correct
8 Correct 1554 ms 826520 KB Output is correct
9 Correct 1209 ms 826532 KB Output is correct
10 Correct 1521 ms 826524 KB Output is correct
11 Correct 1215 ms 826528 KB Output is correct
12 Correct 591 ms 805840 KB Output is correct
13 Correct 786 ms 806556 KB Output is correct
14 Correct 1176 ms 826520 KB Output is correct
15 Correct 1175 ms 826672 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 784520 KB Output is correct
2 Correct 598 ms 805956 KB Output is correct
3 Correct 799 ms 812020 KB Output is correct
4 Correct 1199 ms 834432 KB Output is correct
5 Correct 1253 ms 834564 KB Output is correct
6 Correct 1257 ms 820048 KB Output is correct
7 Correct 196 ms 787924 KB Output is correct
8 Correct 703 ms 802740 KB Output is correct
9 Correct 962 ms 811508 KB Output is correct
10 Correct 2062 ms 835736 KB Output is correct
11 Correct 2100 ms 835740 KB Output is correct
12 Correct 2149 ms 835608 KB Output is correct
13 Correct 2005 ms 835744 KB Output is correct
14 Correct 2029 ms 835744 KB Output is correct
15 Correct 2037 ms 836000 KB Output is correct
16 Correct 2136 ms 835744 KB Output is correct
17 Correct 2120 ms 835744 KB Output is correct
18 Correct 2202 ms 835776 KB Output is correct
19 Correct 2152 ms 835744 KB Output is correct
20 Correct 2242 ms 835744 KB Output is correct
21 Correct 2148 ms 835744 KB Output is correct
22 Correct 2335 ms 835804 KB Output is correct
23 Correct 2241 ms 835748 KB Output is correct
24 Correct 2197 ms 835596 KB Output is correct
25 Correct 2336 ms 835568 KB Output is correct

Subtask #4
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 784468 KB Output is correct
2 Correct 119 ms 784524 KB Output is correct
3 Correct 118 ms 784396 KB Output is correct
4 Correct 108 ms 784464 KB Output is correct
5 Correct 106 ms 784472 KB Output is correct
6 Correct 106 ms 784720 KB Output is correct
7 Correct 107 ms 784720 KB Output is correct
8 Correct 104 ms 784724 KB Output is correct
9 Correct 109 ms 784720 KB Output is correct
10 Correct 119 ms 784976 KB Output is correct
11 Correct 111 ms 784808 KB Output is correct
12 Correct 113 ms 784900 KB Output is correct
13 Correct 116 ms 785176 KB Output is correct
14 Correct 109 ms 784720 KB Output is correct
15 Correct 141 ms 784888 KB Output is correct
16 Correct 110 ms 784932 KB Output is correct
17 Correct 125 ms 784728 KB Output is correct
18 Correct 109 ms 784724 KB Output is correct
19 Correct 119 ms 784832 KB Output is correct
20 Correct 111 ms 784960 KB Output is correct
21 Correct 112 ms 784992 KB Output is correct
22 Correct 110 ms 784856 KB Output is correct
23 Correct 109 ms 784792 KB Output is correct
24 Correct 110 ms 784720 KB Output is correct
25 Correct 113 ms 784976 KB Output is correct
26 Correct 104 ms 784468 KB Output is correct
27 Correct 102 ms 784428 KB Output is correct
28 Correct 107 ms 784480 KB Output is correct
29 Correct 1123 ms 812260 KB Output is correct
30 Correct 617 ms 806024 KB Output is correct
31 Correct 1333 ms 826524 KB Output is correct
32 Correct 606 ms 806064 KB Output is correct
33 Correct 1554 ms 826520 KB Output is correct
34 Correct 1209 ms 826532 KB Output is correct
35 Correct 1521 ms 826524 KB Output is correct
36 Correct 1215 ms 826528 KB Output is correct
37 Correct 591 ms 805840 KB Output is correct
38 Correct 786 ms 806556 KB Output is correct
39 Correct 1176 ms 826520 KB Output is correct
40 Correct 1175 ms 826672 KB Output is correct
41 Correct 110 ms 784520 KB Output is correct
42 Correct 598 ms 805956 KB Output is correct
43 Correct 799 ms 812020 KB Output is correct
44 Correct 1199 ms 834432 KB Output is correct
45 Correct 1253 ms 834564 KB Output is correct
46 Correct 1257 ms 820048 KB Output is correct
47 Correct 196 ms 787924 KB Output is correct
48 Correct 703 ms 802740 KB Output is correct
49 Correct 962 ms 811508 KB Output is correct
50 Correct 2062 ms 835736 KB Output is correct
51 Correct 2100 ms 835740 KB Output is correct
52 Correct 2149 ms 835608 KB Output is correct
53 Correct 2005 ms 835744 KB Output is correct
54 Correct 2029 ms 835744 KB Output is correct
55 Correct 2037 ms 836000 KB Output is correct
56 Correct 2136 ms 835744 KB Output is correct
57 Correct 2120 ms 835744 KB Output is correct
58 Correct 2202 ms 835776 KB Output is correct
59 Correct 2152 ms 835744 KB Output is correct
60 Correct 2242 ms 835744 KB Output is correct
61 Correct 2148 ms 835744 KB Output is correct
62 Correct 2335 ms 835804 KB Output is correct
63 Correct 2241 ms 835748 KB Output is correct
64 Correct 2197 ms 835596 KB Output is correct
65 Correct 2336 ms 835568 KB Output is correct
66 Correct 925 ms 812036 KB Output is correct
67 Correct 1075 ms 817208 KB Output is correct
68 Correct 1344 ms 822880 KB Output is correct
69 Correct 1274 ms 819668 KB Output is correct
70 Correct 2189 ms 835740 KB Output is correct
71 Correct 2164 ms 835744 KB Output is correct
72 Correct 2147 ms 835740 KB Output is correct
73 Correct 2097 ms 835740 KB Output is correct
74 Correct 2323 ms 835708 KB Output is correct
75 Correct 2095 ms 835644 KB Output is correct
76 Correct 1833 ms 835572 KB Output is correct
77 Correct 1901 ms 835744 KB Output is correct
78 Correct 1897 ms 835744 KB Output is correct
79 Correct 2106 ms 835744 KB Output is correct
80 Correct 1970 ms 835740 KB Output is correct
81 Correct 2169 ms 835736 KB Output is correct
82 Correct 2041 ms 835768 KB Output is correct
83 Correct 2259 ms 835740 KB Output is correct
84 Correct 1947 ms 835744 KB Output is correct
85 Correct 2293 ms 835596 KB Output is correct
86 Correct 2003 ms 835744 KB Output is correct
87 Correct 2233 ms 835576 KB Output is correct
88 Correct 2016 ms 835744 KB Output is correct
89 Correct 2057 ms 835744 KB Output is correct