Submission #102083

#	Time	Username	Problem	Language	Result	Execution time	Memory
102083		ainta	Two Dishes (JOI19_dishes)	C++17	100 / 100	8164 ms	217548 KiB

dishes

#include<cstdio>
#include<algorithm>
#include<map>
#define N_ 1010000
#define SZ (1<<20)
#define pii pair<int,int>
using namespace std;
struct Input {
	int a;
	long long t, c;
}A[N_], B[N_];
long long SA[N_], SB[N_], res;
int n, m, cnt;
struct Tree {
	long long Mx[SZ + SZ], K[SZ + SZ], INF = 1e18;
	void Add2(int nd, long long x) {
		Mx[nd] += x;
		K[nd] += x;
	}
	void Spread(int nd) {
		Add2(nd * 2, K[nd]);
		Add2(nd * 2 + 1, K[nd]);
		K[nd] = 0;
	}
	void UDT(int nd) {
		Mx[nd] = max(Mx[nd * 2], Mx[nd * 2 + 1]);
	}
	void Add(int nd, int b, int e, int s, int l, long long x) {
		if (s > l)return;
		if (b == s && e == l) {
			Add2(nd, x);
			return;
		}
		Spread(nd);
		int m = (b + e) >> 1;
		if (s <= m)Add(nd * 2, b, m, s, min(m, l), x);
		if (l > m)Add(nd * 2 + 1, m + 1, e, max(m + 1, s), l, x);
		UDT(nd);
	}
	long long Max(int nd, int b, int e, int s, int l) {
		if (s > l)return -INF;
		if (b == s && e == l) return Mx[nd];
		Spread(nd);
		int m = (b + e) >> 1;
		long long r = -INF;
		if (s <= m)r = max(r, Max(nd * 2, b, m, s, min(m, l)));
		if (l > m)r = max(r, Max(nd * 2 + 1, m + 1, e, max(m + 1, s), l));
		return r;
	}
	void Put(int nd, int b, int e, int x, long long y) {
		if (b == e) {
			if (Mx[nd] < y) {
				Mx[nd] = y, K[nd] = y;
			}
			return;
		}
		Spread(nd);
		int m = (b + e) >> 1;
		if (x <= m)Put(nd * 2, b, m, x, y);
		else Put(nd * 2 + 1, m + 1, e, x, y);
		UDT(nd);
	}
}TT;
int main() {
	int i, j;
	scanf("%d%d", &n, &m);
	for (i = 1; i <= n; i++) {
		scanf("%d%lld%lld", &A[i].a, &A[i].t, &A[i].c);
		SA[i] = SA[i - 1] + A[i].a;
	}
	for (i = 1; i <= m; i++) {
		scanf("%d%lld%lld", &B[i].a, &B[i].t, &B[i].c);
		SB[i] = SB[i - 1] + B[i].a;
	}
	long long ss = 0;
	map<pii, int>Map;
	for (i = 1; i <= n; i++) {
		if (SA[i] > A[i].t) continue;
		if (SA[i] + SB[m] <= A[i].t) {
			ss += A[i].c;
			continue;
		}
		int pv = lower_bound(SB + 1, SB + m + 1, A[i].t - SA[i] + 1) - SB;
		pv--;
		Map[{i - 1, -(pv + 1)}] += A[i].c;
	}
	for (i = 1; i <= m; i++) {
		if (SB[i] > B[i].t) continue;
		if (SB[i] + SA[n] <= B[i].t) {
			ss += B[i].c;
			continue;
		}
		int pv = lower_bound(SA + 1, SA + n + 1, B[i].t - SB[i] + 1) - SA;
		pv--;
		ss += B[i].c;
		Map[{pv, -i}] -= B[i].c;
	}
	for (auto &tp : Map) {
		int x = tp.first.first, y = -tp.first.second, c = tp.second;
		long long t = TT.Max(1, 0, SZ - 1, 0, y - 1);
		TT.Put(1, 0, SZ - 1, y, t);
		TT.Add(1, 0, SZ - 1, 0, y - 1, c);
	}
	printf("%lld\n", TT.Max(1, 0, SZ - 1, 0, SZ - 1) + ss);
}

Compilation message (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:99:7: warning: unused variable 'x' [-Wunused-variable]
   int x = tp.first.first, y = -tp.first.second, c = tp.second;
       ^
dishes.cpp:65:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
dishes.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
dishes.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%lld%lld", &A[i].a, &A[i].t, &A[i].c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%lld%lld", &B[i].a, &B[i].t, &B[i].c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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