oj.uz

답안 #203410

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
203410 2020-02-20T14:27:53 Z dennisstar Two Dishes (JOI19_dishes) C++17
0 / 100
 10000 ms 28252 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<int, ll> pil;
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<pair<int, pil> > qu;

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.eb(i, pil(I, P[i]));
	}qu.eb(N+1, pil(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.eb(J+1, pil(i-1, -Q[i])), im+=Q[i];
	}
	sort(all(qu));
	for (int i=1, j=0; i<=N+1; i++) {
		for (int k=j; k<qu.size()&&qu[k].fi==i; j++) {
			auto l=qu[k].se; upd1(1, 0, M, 0, l.fi, l.se);
		}
		for (; j<qu.size()&&qu[j].fi==i; j++) {
			auto l=qu[j].se; upd2(1, 0, M, l.fi+1, M, get(1, 0, M, l.fi));
		}
	}
	printf("%lld\n", get(1, 0, M, M)+im);
	return 0;
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:62:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int k=j; k<qu.size()&&qu[k].fi==i; j++) {
                 ~^~~~~~~~~~
dishes.cpp:65:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (; j<qu.size()&&qu[j].fi==i; j++) {
          ~^~~~~~~~~~
dishes.cpp:48: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:49: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:50: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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10031 ms 28252 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10044 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10044 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10044 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10044 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10044 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10031 ms 28252 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10031 ms 28252 KB Time limit exceeded
2 Halted 0 ms 0 KB -