Submission #203406

#TimeUsernameProblemLanguageResultExecution timeMemory
203406dennisstarTwo Dishes (JOI19_dishes)C++17
0 / 100
704 ms76672 KiB
#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 (stderr)

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];
                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...