oj.uz

답안 #123434

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
123434 2019-07-01T12:41:35 Z youngyojun Two Dishes (JOI19_dishes) C++11
0 / 100
 2346 ms 76452 KB 
#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 bool debug = 0;

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 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);
		ds[i] = ds[i<<1] + ds[i<<1|1];
	}
	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);
		ds[i] = ds[i<<1] + ds[i<<1|1];
	}
	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);
		ds[i] = ds[i<<1] + ds[i<<1|1];
		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);
		// TODO
	}
} 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 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]].eb(i, -E[i]);
		}
	}
	for(int i = 1; i <= M; i++) if(0 <= GI[i] && F[i]) {
		if(0 < F[i]) PushEV[i-1].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]);
			}
		}
	}
	
	if(debug) {
		printf("N=%d, M=%d\n", N, M);
		for(int i = 1; i <= N; i++) printf("%d ", FI[i]);
		puts("");
		for(int i = 1; i <= M; i++) printf("%d ", GI[i]);
		puts("");
	}
	
	for(int j = 1; j <= M; j++) {
		for(auto &ev : PushEV[j-1]) {
			int i, ei; tie(i, ei) = ev;
			Delta += ei;
			int s = i+1, e = N+1; for(int m; s < e;) {
				m = (s+e) >> 1;
				if(seg.get(1, 1, N, i+1, m) < ei) s = m+1;
				else e = m;
			}
			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);
		}

		for(auto &ev : PopEV[j]) {
			int i, ei; tie(i, ei) = ev;
			bit.upd(i, -ei);
			seg.upddx(1, 1, N, i, ei);
			if(debug) {
				printf("j=%d, pop %d %d\n", j, i, ei);
			}
		}

		if(debug) {
			printf("j=%d / %lld\n", j, Delta);
			for(int i = 1; i <= N; i++) printf("%lld ", bit.get(i, i));
			puts("");
			for(int i = 1; i <= N; i++) printf("%lld ", seg.get(1, 1, N, i));
			puts("");
		}
	}

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

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2346 ms 76252 KB Output is correct
2 Incorrect 1961 ms 76452 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 47784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 47784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 47784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 47784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 47784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2346 ms 76252 KB Output is correct
2 Incorrect 1961 ms 76452 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2346 ms 76252 KB Output is correct
2 Incorrect 1961 ms 76452 KB Output isn't correct
3 Halted 0 ms 0 KB -