oj.uz

Submission #573145

# Submission time Handle Problem Language Result Execution time Memory
573145 2022-06-06T04:47:53 Z dennisstar Ants and Sugar (JOI22_sugar) C++17
0 / 100
 315 ms 36504 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct node {
	ll sum, lmin, rmin, mn, a[2];
};

node operator +(node l, node r) {
	node rt;
	ll md=l.a[1];
	rt.sum=l.sum+r.sum-md;
	rt.lmin=min(l.lmin+r.mn, l.sum+r.lmin-md);
	rt.rmin=min(r.rmin+l.mn, r.sum+l.rmin-md);
	rt.mn=min(l.mn+r.mn, l.rmin+r.lmin-md);
	rt.a[0]=l.a[0], rt.a[1]=r.a[1];
	return rt;
}

node st[1<<20];

void upd1(int i, int s, int e, int t, int ty, int v) {
	if (t<s||t>e) return ;
	if (s==e) {
		st[i].sum+=v;
		st[i].a[ty]+=v;
		st[i].lmin=st[i].rmin=st[i].sum;
		st[i].mn=min(0ll, st[i].sum);
		return ;
	}
	int m=(s+e)/2;
	if (t<=m) upd1(i*2, s, m, t, ty, v);
	else upd1(i*2+1, m+1, e, t, ty, v);
	st[i]=st[i*2]+st[i*2+1];
}

void upd2(int i, int s, int e, int t, int v) {
	if (s==e) {
		st[i].sum-=v;
		st[i].lmin=st[i].rmin=st[i].sum;
		st[i].mn=min(0ll, st[i].sum);
		return ;
	}
	int m=(s+e)/2;
	if (t<=m) upd2(i*2, s, m, t, v);
	else upd2(i*2+1, m+1, e, t, v);
	st[i]=st[i*2]+st[i*2+1];
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int q, l;
	cin>>q>>l;
	ll sum=0;
	for (int l=0; l<q; l++) {
		int t, x, a;
		cin>>t>>x>>a;
		x++;
		if (t==1) upd1(1, 1, (q+1)/2, x/2, 1, a), upd1(1, 1, (q+1)/2, x/2+1, 0, a);
		else sum+=a, upd2(1, 1, (q+1)/2, (x+1)/2, a);
		cout<<sum+st[1].mn<<'\n';
	}

	return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Incorrect 315 ms 36504 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -