Submission #1208411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208411		PenguinsAreCute	Ants and Sugar (JOI22_sugar)	C++17	16 / 100	956 ms	44836 KiB

sugar

#include <bits/stdc++.h>
using namespace std;
#define all(v) begin(v),end(v)
#define pb push_back
using ii = pair<int,int>;
struct dat {
	long long gr[2][2];
	dat() {memset(gr,0,sizeof(gr));}
	dat(long long _gr[2][2]) {memcpy(gr,_gr,sizeof(gr));}
	dat(long long _x) {gr[0][1]=gr[1][0]=1e18;gr[0][0]=0;gr[1][1]=_x;}
	dat operator + (dat b) {
		long long ans[2][2];
		ans[0][0]=ans[0][1]=ans[1][0]=ans[1][1]=1e18;
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				for(int k=0;k<2;k++)
					for(int l=0;l<2;l++)
						if(j||k)
							ans[i][l] = min(ans[i][l], gr[i][j] + b.gr[k][l]);
		return dat(ans);
	}
	long long toll() {
		long long ans = 1e18;
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				ans = min(ans, gr[i][j]);
		return ans;
	}
};
struct segtree {
	int n;
	vector<dat> seg;
	segtree(int _n): n(_n), seg(2*_n, dat(0LL)) {}
	void up(int x, dat v) {
		for(seg[x+=n]=v;x>>=1;)
			seg[x] = seg[x<<1] + seg[x<<1|1];
	}
	dat qry() {return seg[1];}
};
int main() {
	segtree s(1<<19);
	int q, l;
	cin >> q >> l;
	long long cnt[q];
	memset(cnt,0,sizeof(cnt));
	while(q--) {
		int t, y, x;
		cin >> t >> x >> y;
		cnt[x] += y;
		s.up(x,dat(cnt[x]));
		dat res = s.qry();
		cout << s.qry().toll() << "\n";
	}
}

• Subtask 1: 0 / 6
• Subtask 2: 16 / 16
• Subtask 3: 0 / 26
• Subtask 4: 0 / 52