Submission #123460

#	Time	Username	Problem	Language	Result	Execution time	Memory
123460		youngyojun	Two Dishes (JOI19_dishes)	C++11	100 / 100	8205 ms	191964 KiB

dishes

#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define rb(x) ((x)&(-(x)))
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
const int MAXN = 1000055;
const int MAXM = 1000055;
 
struct BIT {
	ll d[MAXN];
 
	void upd(int x, ll r) {
		for(x += 5; x < MAXN; x += rb(x))
			d[x] += r;
	}
	ll get(int x) {
		ll r = 0; for(x += 5; x; x -= rb(x))
			r += d[x];
		return r;
	}
	ll get(int s, int e) { return s > e ? 0 : get(e) - get(s-1); }
} bit;

struct NOD {
	NOD(int i, int s, int e) : i(i), s(s), e(e) {}
	int i, s, e;
};

struct SEG {
	ll ds[MAXN*3];
	bitset<MAXN*3> dz;
 
	void prop(int i, int s, int e) {
		if(dz[i]) {
			ds[i] = 0;
			if(s != e) dz[i<<1] = dz[i<<1|1] = true;
			dz[i] = false;
			return;
		}
		if(s == e) return;
		ds[i] = 0;
		if(!dz[i<<1]) ds[i] += ds[i<<1];
		if(!dz[i<<1|1]) ds[i] += ds[i<<1|1];
	}
	void cal(int i) { ds[i] = ds[i<<1] + ds[i<<1|1]; }
	void updz(int i, int s, int e, int p, int q) {
		prop(i, s, e); if(q < p || e < p || q < s) return;
		if(p <= s && e <= q) {
			dz[i] = true;
			prop(i, s, e);
			return;
		}
		int m = (s+e) >> 1;
		updz(i<<1, s, m, p, q);
		updz(i<<1|1, m+1, e, p, q);
		cal(i);
	}
	void updp(int i, int s, int e, int x, ll r) {
		prop(i, s, e); if(x < s || e < x) return;
		if(s == e) {
			ds[i] = r;
			return;
		}
		int m = (s+e) >> 1;
		updp(i<<1, s, m, x, r);
		updp(i<<1|1, m+1, e, x, r);
		ds[i] = ds[i<<1] + ds[i<<1|1];
	}
	void upddx(int i, int s, int e, int x, ll r) {
		prop(i, s, e); if(x < s || e < x) return;
		if(s == e) {
			ds[i] += r;
			return;
		}
		int m = (s+e) >> 1;
		upddx(i<<1, s, m, x, r);
		upddx(i<<1|1, m+1, e, x, r);
		cal(i);
	}
	ll get(int i, int s, int e, int p, int q) {
		prop(i, s, e); if(q < p || e < p || q < s) return 0;
		if(p <= s && e <= q) return ds[i];
		int m = (s+e) >> 1;
		ll ret = get(i<<1, s, m, p, q) + get(i<<1|1, m+1, e, p, q);
		cal(i);
		return ret;
	}
	ll get(int i, int s, int e, int x) { return get(1, s, e, x, x); }

	void getNodes(vector<NOD> &V, int i, int s, int e, int p, int q) {
		prop(i, s, e); if(q < p || e < p || q < s) return;
		if(p <= s && e <= q) {
			V.eb(i, s, e);
			return;
		}
		int m = (s+e) >> 1;
		getNodes(V, i<<1, s, m, p, q);
		getNodes(V, i<<1|1, m+1, e, p, q);
	}
	int getX(int i, int s, int e, ll lft) {
		prop(i, s, e); if(s == e) return s;
		int m = (s+e) >> 1;
		int ret;
		if(lft < ds[i<<1]) {
			ret = getX(i<<1, s, m, lft);
			prop(i<<1|1, m+1, e);
		} else {
			prop(i<<1, s, m);
			ret = getX(i<<1|1, m+1, e, lft - ds[i<<1]);
		}
		cal(i);
		return ret;
	}
} seg;

vector<pii> PopEV[MAXM];
vector<pii> PushEV[MAXM];

ll SA[MAXN], SB[MAXM];
int FI[MAXN], GI[MAXM];

ll C[MAXN], D[MAXM];
int A[MAXN], B[MAXM];
int E[MAXN], F[MAXM];

ll Delta;
int N, M;

int fndX(int s, ll K) {
	vector<NOD> V;
	seg.getNodes(V, 1, 1, N, s, N);
	ll sum = 0;
	for(auto &v : V) {
		ll t = seg.ds[v.i];
		if(K <= sum+t) return seg.getX(v.i, v.s, v.e, K-sum);
		sum += t;
	}
	return N+1;
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> M;
	for(int i = 1; i <= N; i++)
		cin >> A[i] >> C[i] >> E[i];
	for(int i = 1; i <= M; i++)
		cin >> B[i] >> D[i] >> F[i];
	
	for(int i = 1; i <= N; i++) SA[i] = SA[i-1] + A[i];
	for(int i = 1; i <= M; i++) SB[i] = SB[i-1] + B[i];

	for(int i = 1; i <= N; i++)
		FI[i] = int(upper_bound(SB, SB+M+1, C[i]-SA[i])-SB) - 1;
	for(int i = 1; i <= M; i++)
		GI[i] = int(upper_bound(SA, SA+N+1, D[i]-SB[i])-SA) - 1;

	for(int i = 1; i <= N; i++) if(0 <= FI[i] && E[i]) {
		if(0 < E[i]) {
			PopEV[FI[i]+1].eb(i, E[i]);
			bit.upd(i, E[i]);
		} else {
			Delta += E[i];
			if(FI[i] < M) PushEV[FI[i]+1].eb(i-1, -E[i]);
		}
	}
	for(int i = 1; i <= M; i++) if(0 <= GI[i] && F[i]) {
		if(0 < F[i]) PushEV[i].eb(GI[i], F[i]);
		else {
			Delta += F[i];
			if(GI[i] < N) {
				PopEV[i].eb(GI[i]+1, -F[i]);
				bit.upd(GI[i]+1, -F[i]);
			}
		}
	}
	
	for(int j = 1; j <= M; j++) {
		for(auto &ev : PopEV[j]) {
			int i, ei; tie(i, ei) = ev;
			bit.upd(i, -ei);
			seg.upddx(1, 1, N, i, ei);
		}

		for(auto &ev : PushEV[j]) {
			int i, ei; tie(i, ei) = ev;
			Delta += ei;
			int s = fndX(i+1, ei);
			ll t = seg.get(1, 1, N, i+1, s-1);
			seg.updz(1, 1, N, i+1, s-1);
			if(s <= N) seg.upddx(1, 1, N, s, t-ei);
		}
	}

	cout << bit.get(1, N) + seg.get(1, 1, N, 1, N) + Delta << endl;
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 17 / 17
• Subtask 8: 9 / 9