oj.uz

Submission #203406

# Submission time Handle Problem Language Result Execution time Memory
203406 2020-02-20T13:53:08 Z dennisstar Two Dishes (JOI19_dishes) C++17
0 / 100
 704 ms 76672 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define eb emplace_back
#define all(V) (V).begin(), (V).end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll INF = 1ll<<60;

ll F[1<<21], lz1[1<<21], lz2[1<<21];
inline void spread(int i) {
	F[i]=max(F[i]+lz1[i], lz2[i]);
	if (i<(1<<20)) for (auto &j:{i*2, i*2+1}) lz1[j]+=lz1[i], lz2[j]+=lz1[i], lz2[j]=max(lz2[j], lz2[i]);
	lz1[i]=0, lz2[i]=-INF;
}
inline void upd1(int i, int s, int e, int ts, int te, ll v) {
	spread(i);
	if (e<ts||te<s||te<ts) return ;
	if (ts<=s&&e<=te) { lz1[i]+=v, lz2[i]+=v; spread(i); return ; }
	int md=(s+e)/2;
	upd1(i*2, s, md, ts, te, v); upd1(i*2+1, md+1, e, ts, te, v);
	F[i]=max(F[i*2], F[i*2+1]);
}
inline void upd2(int i, int s, int e, int ts, int te, ll v) {
	spread(i);
	if (e<ts||te<s||te<ts) return ;
	if (ts<=s&&e<=te) { lz2[i]=v; spread(i); return ; }
	int md=(s+e)/2;
	upd2(i*2, s, md, ts, te, v); upd2(i*2+1, md+1, e, ts, te, v);
	F[i]=max(F[i*2], F[i*2+1]);
}
inline ll get(int i, int s, int e, int t) {
	spread(i);
	if (s==e) return F[i];
	int md=(s+e)/2;
	if (t<=md) return get(i*2, s, md, t);
	else return get(i*2+1, md+1, e, t);
}

int N, M;
ll A[1<<20], B[1<<20], S[1<<20], T[1<<20], P[1<<20], Q[1<<20];
vector<pll> qu[1<<20];

inline void add(ll lb, ll v, ll ub) {
	upd1(1, 1, M+1, 1, lb+1, v);
	upd2(1, 1, M+1, lb+2, ub+1, get(1, 1, M+1, ub+1));
}

int main() {
	scanf("%d %d", &N, &M);
	for (int i=1; i<=N; i++) scanf("%lld %lld %lld", &A[i], &S[i], &P[i]), A[i]+=A[i-1];
	for (int i=1; i<=M; i++) scanf("%lld %lld %lld", &B[i], &T[i], &Q[i]), B[i]+=B[i-1];
	for (int i=1; i<=N; i++) {
		int I=upper_bound(B, B+M+1, S[i]-A[i])-B-1;
		if (I>=0) qu[i].eb(I, P[i]);
	}qu[N+1].eb(M-1, -INF);
	ll im=0;
	for (int i=1; i<=M; i++) {
		int J=upper_bound(A, A+N+1, T[i]-B[i])-A-1;
		if (J>=0) qu[J+1].eb(i-1, -Q[i]), im+=Q[i];
	}
	for (int i=1; i<=N+1; i++) {
		sort(all(qu[i]));
		for (int j=0; j<qu[i].size(); j++)
			add(qu[i][j].fi, qu[i][j].se, j+1<qu[i].size()?qu[i][j+1].fi:M);
	}
	printf("%lld\n", get(1, 1, M+1, M+1)+im);
	return 0;
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:67:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<qu[i].size(); j++)
                 ~^~~~~~~~~~~~~
dishes.cpp:68:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    add(qu[i][j].fi, qu[i][j].se, j+1<qu[i].size()?qu[i][j+1].fi:M);
                                  ~~~^~~~~~~~~~~~~
dishes.cpp:53: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:54:71: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=1; i<=N; i++) scanf("%lld %lld %lld", &A[i], &S[i], &P[i]), A[i]+=A[i-1];
                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
dishes.cpp:55:71: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=1; i<=M; i++) scanf("%lld %lld %lld", &B[i], &T[i], &Q[i]), B[i]+=B[i-1];
                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24952 KB Output is correct
2 Correct 19 ms 24952 KB Output is correct
3 Correct 20 ms 25080 KB Output is correct
4 Incorrect 19 ms 24948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24952 KB Output is correct
2 Correct 19 ms 24952 KB Output is correct
3 Correct 20 ms 25080 KB Output is correct
4 Incorrect 19 ms 24948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24952 KB Output is correct
2 Correct 19 ms 24952 KB Output is correct
3 Correct 20 ms 25080 KB Output is correct
4 Incorrect 19 ms 24948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24952 KB Output is correct
2 Correct 19 ms 24952 KB Output is correct
3 Correct 20 ms 25080 KB Output is correct
4 Incorrect 19 ms 24948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24952 KB Output is correct
2 Correct 19 ms 24952 KB Output is correct
3 Correct 20 ms 25080 KB Output is correct
4 Incorrect 19 ms 24948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

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

Subtask #8
0 / 9.0

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