#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")
|
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
102 ms |
784464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
