oj.uz

Submission #946659

# Submission time Handle Problem Language Result Execution time Memory
946659 2024-03-14T21:22:05 Z MilosMilutinovic Ants and Sugar (JOI22_sugar) C++14
22 / 100
 4000 ms 682316 KB 
#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
 
int q,l,k;
int t[500005],x[500005],a[500005];
ll b[1500005][2],sum,dp[12000005][3][2][2],lzy[12000005][2];
vector<int> xs;

void pull(int id){
	for(int x=0;x<2;x++) for(int y=0;y<2;y++) for(int c=0;c<3;c++) dp[id][c][x][y]=max(dp[id<<1][c][x][y],dp[id<<1|1][c][x][y]);
	for(int x1=0;x1<2;x1++){
		for(int y2=0;y2<2;y2++){
			for(int c1=0;c1<3;c1++){
				for(int c2=0;c2<3;c2++){
					dp[id][min(2,c1+c2)][x1][y2]=max(dp[id][min(2,c1+c2)][x1][y2],dp[id<<1][c1][x1][0]+dp[id<<1|1][c2][1][y2]);
					dp[id][min(2,c1+c2)][x1][y2]=max(dp[id][min(2,c1+c2)][x1][y2],dp[id<<1][c1][x1][1]+dp[id<<1|1][c2][0][y2]);
				}
			}
		}
	}
}

void upd1(int id,ll v){
	for(int c=0;c<3;c++){
		dp[id][c][0][0]-=v;
		dp[id][c][1][1]+=v;
	}
}

void upd2(int id,ll v){
	for(int x=0;x<2;x++){
		for(int y=0;y<2;y++){
			dp[id][1][x][y]-=v;
			dp[id][2][x][y]-=2*v;
		}
	}
}

void push(int id){
	if((id<<1|1)>6000000) return;
	if(lzy[id][0]!=0){
		upd1(id<<1,lzy[id][0]);
		upd1(id<<1|1,lzy[id][0]);
		lzy[id<<1][0]+=lzy[id][0];
		lzy[id<<1|1][0]+=lzy[id][0];
		lzy[id][0]=0;
	}
	if(lzy[id][1]!=0){
		upd2(id<<1,lzy[id][1]);
		upd2(id<<1|1,lzy[id][1]);
		lzy[id<<1][1]+=lzy[id][1];
		lzy[id<<1|1][1]+=lzy[id][1];
		lzy[id][1]=0;
	}
}

void build(int id,int l,int r){
	if(l==r){
		for(int x=0;x<2;x++){
			for(int y=0;y<2;y++){
				for(int c=0;c<3;c++){
					dp[id][c][x][y]=(ll)-1e18;
				}
			}
		}
		dp[id][0][0][0]=0;
		dp[id][1][1][1]=0;
		return;
	}
	int mid=(l+r)/2;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	pull(id);
}

void change(int id,int l,int r,int ql,int qr,int v){
	if(ql<=l&&r<=qr){
		upd1(id,v);
		lzy[id][0]+=v;
		push(id);
		return;
	}
	push(id);
	int mid=(l+r)/2;
	if(qr<=mid) change(id<<1,l,mid,ql,qr,v);
	else if(ql>mid) change(id<<1|1,mid+1,r,ql,qr,v);
	else change(id<<1,l,mid,ql,qr,v),change(id<<1|1,mid+1,r,ql,qr,v);
	pull(id);
}

void modify(int id,int l,int r,int ql,int qr,int v){
	if(ql<=l&&r<=qr){
		upd2(id,v);
		lzy[id][1]+=v;
		push(id);
		return;
	}
	push(id);
	int mid=(l+r)/2;
	if(qr<=mid) modify(id<<1,l,mid,ql,qr,v);
	else if(ql>mid) modify(id<<1|1,mid+1,r,ql,qr,v);
	else modify(id<<1,l,mid,ql,qr,v),modify(id<<1|1,mid+1,r,ql,qr,v);
	pull(id);
}

int main(){
	q=readint(); l=readint();
	for(int i=1;i<=q;i++){
		t[i]=readint(); x[i]=readint(); a[i]=readint();
	}
	for(int i=1;i<=q;i++){
		xs.pb(x[i]);
		xs.pb(x[i]-l);
		xs.pb(x[i]+l);
	}
	xs.pb((int)-1.00001e9);
	sort(xs.begin(),xs.end());
	xs.erase(unique(xs.begin(),xs.end()),xs.end());
	k=(int)xs.size();
	build(1,0,k-1);
	for(int i=1;i<=q;i++){
		if(t[i]==1){
			int idx=(int)(lower_bound(xs.begin(),xs.end(),x[i])-xs.begin());
			change(1,0,k-1,idx,k-1,a[i]);
			sum+=a[i];
		}else{
			int idx1=(int)(lower_bound(xs.begin(),xs.end(),x[i]+l)-xs.begin());
			change(1,0,k-1,idx1,k-1,-a[i]);
			int idx2=(int)(lower_bound(xs.begin(),xs.end(),x[i]-l)-xs.begin());
			modify(1,0,k-1,idx2,idx1-1,a[i]);
		}
		ll mx=0;
		for(int c=0;c<3;c++){
			chkmax(mx,dp[1][c][0][1]);
		}
		printf("%lld\n",sum-mx);
	}
	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 9 ms 12892 KB Output is correct
7 Correct 8 ms 12892 KB Output is correct
8 Correct 5 ms 8796 KB Output is correct
9 Correct 4 ms 8792 KB Output is correct
10 Correct 14 ms 17216 KB Output is correct
11 Correct 17 ms 17244 KB Output is correct
12 Correct 15 ms 16988 KB Output is correct
13 Correct 14 ms 16984 KB Output is correct
14 Correct 19 ms 16984 KB Output is correct
15 Correct 16 ms 17244 KB Output is correct
16 Correct 10 ms 17244 KB Output is correct
17 Correct 9 ms 16988 KB Output is correct
18 Correct 10 ms 17212 KB Output is correct
19 Correct 19 ms 16984 KB Output is correct
20 Correct 9 ms 15964 KB Output is correct
21 Correct 15 ms 17232 KB Output is correct
22 Correct 10 ms 16988 KB Output is correct
23 Correct 15 ms 17244 KB Output is correct
24 Correct 9 ms 16988 KB Output is correct
25 Correct 15 ms 17244 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 2159 ms 253320 KB Output is correct
5 Correct 933 ms 132868 KB Output is correct
6 Correct 2515 ms 254436 KB Output is correct
7 Correct 1004 ms 133116 KB Output is correct
8 Correct 2988 ms 258528 KB Output is correct
9 Correct 2101 ms 259396 KB Output is correct
10 Correct 2939 ms 258100 KB Output is correct
11 Correct 2060 ms 259212 KB Output is correct
12 Correct 869 ms 131616 KB Output is correct
13 Correct 1292 ms 248264 KB Output is correct
14 Correct 2059 ms 255524 KB Output is correct
15 Correct 2067 ms 254364 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 861 ms 131748 KB Output is correct
3 Correct 1205 ms 248248 KB Output is correct
4 Correct 2005 ms 255188 KB Output is correct
5 Correct 2053 ms 255604 KB Output is correct
6 Correct 2240 ms 251600 KB Output is correct
7 Correct 155 ms 67532 KB Output is correct
8 Correct 1116 ms 246376 KB Output is correct
9 Correct 1735 ms 248504 KB Output is correct
10 Correct 3460 ms 678168 KB Output is correct
11 Correct 3618 ms 677300 KB Output is correct
12 Correct 3571 ms 681472 KB Output is correct
13 Correct 3380 ms 682316 KB Output is correct
14 Correct 3526 ms 682064 KB Output is correct
15 Correct 3303 ms 677572 KB Output is correct
16 Correct 3423 ms 681572 KB Output is correct
17 Correct 3712 ms 617104 KB Output is correct
18 Execution timed out 4027 ms 681080 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 9 ms 12892 KB Output is correct
7 Correct 8 ms 12892 KB Output is correct
8 Correct 5 ms 8796 KB Output is correct
9 Correct 4 ms 8792 KB Output is correct
10 Correct 14 ms 17216 KB Output is correct
11 Correct 17 ms 17244 KB Output is correct
12 Correct 15 ms 16988 KB Output is correct
13 Correct 14 ms 16984 KB Output is correct
14 Correct 19 ms 16984 KB Output is correct
15 Correct 16 ms 17244 KB Output is correct
16 Correct 10 ms 17244 KB Output is correct
17 Correct 9 ms 16988 KB Output is correct
18 Correct 10 ms 17212 KB Output is correct
19 Correct 19 ms 16984 KB Output is correct
20 Correct 9 ms 15964 KB Output is correct
21 Correct 15 ms 17232 KB Output is correct
22 Correct 10 ms 16988 KB Output is correct
23 Correct 15 ms 17244 KB Output is correct
24 Correct 9 ms 16988 KB Output is correct
25 Correct 15 ms 17244 KB Output is correct
26 Correct 1 ms 8540 KB Output is correct
27 Correct 2 ms 8540 KB Output is correct
28 Correct 1 ms 8536 KB Output is correct
29 Correct 2159 ms 253320 KB Output is correct
30 Correct 933 ms 132868 KB Output is correct
31 Correct 2515 ms 254436 KB Output is correct
32 Correct 1004 ms 133116 KB Output is correct
33 Correct 2988 ms 258528 KB Output is correct
34 Correct 2101 ms 259396 KB Output is correct
35 Correct 2939 ms 258100 KB Output is correct
36 Correct 2060 ms 259212 KB Output is correct
37 Correct 869 ms 131616 KB Output is correct
38 Correct 1292 ms 248264 KB Output is correct
39 Correct 2059 ms 255524 KB Output is correct
40 Correct 2067 ms 254364 KB Output is correct
41 Correct 1 ms 8540 KB Output is correct
42 Correct 861 ms 131748 KB Output is correct
43 Correct 1205 ms 248248 KB Output is correct
44 Correct 2005 ms 255188 KB Output is correct
45 Correct 2053 ms 255604 KB Output is correct
46 Correct 2240 ms 251600 KB Output is correct
47 Correct 155 ms 67532 KB Output is correct
48 Correct 1116 ms 246376 KB Output is correct
49 Correct 1735 ms 248504 KB Output is correct
50 Correct 3460 ms 678168 KB Output is correct
51 Correct 3618 ms 677300 KB Output is correct
52 Correct 3571 ms 681472 KB Output is correct
53 Correct 3380 ms 682316 KB Output is correct
54 Correct 3526 ms 682064 KB Output is correct
55 Correct 3303 ms 677572 KB Output is correct
56 Correct 3423 ms 681572 KB Output is correct
57 Correct 3712 ms 617104 KB Output is correct
58 Execution timed out 4027 ms 681080 KB Time limit exceeded
59 Halted 0 ms 0 KB -