Submission #157257

#TimeUsernameProblemLanguageResultExecution timeMemory
157257atoizTwo Dishes (JOI19_dishes)C++14
0 / 100
248 ms48088 KiB
#include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <string> #include <cstdio> #include <cmath> #include <cstdlib> #include <cmath> #include <climits> #include <cassert> #include <numeric> #include <tuple> #include <bitset> #include <unordered_map> #include <unordered_set> #include <map> #include <set> #include <queue> #include <ios> #include <iomanip> #include <random> #include <chrono> using namespace std; using ll = long long; #define FOR(i, a, b) for (int i = a; i <= b; ++i) #define FORA(i, a) for (auto &i : a) #define FORB(i, a, b) for (int i = a; i >= b; --i) #define SZ(a) ((int) a.size()); #define ALL(a) begin(a), end(a) const int MAXN = 1000007; const ll INF = 1e16; int N, M; ll A[MAXN], B[MAXN], S[MAXN], T[MAXN], P[MAXN], Q[MAXN]; vector<int> ids[MAXN]; ll lazy[MAXN], tree[MAXN]; void build(int root, int lo, int hi) { } void push(int root, int lo, int hi) { if (lo < hi) { tree[root << 1] += lazy[root]; tree[root << 1 | 1] += lazy[root]; lazy[root << 1] += lazy[root]; lazy[root << 1 | 1] += lazy[root]; } lazy[root] = 0; } void add(int l, int r, ll x, int root = 1, int lo = 0, int hi = M) { FOR(i, l, r) tree[i] += x; return; if (r < lo || hi < l) return; push(root, lo, hi); if (l <= lo && hi <= r) { lazy[root] += x; tree[root] += x; return; } int mid = (lo + hi) >> 1; add(l, r, x, root << 1, lo, mid); add(l, r, x, root << 1 | 1, mid + 1, hi); } void upd(int l, int r, ll x, int root = 1, int lo = 0, int hi = M) { FOR(i, l, r) tree[i] = max(tree[i], x); return; if (r < lo || hi < l) return; push(root, lo, hi); if (l <= lo && hi <= r) { tree[root] = max(tree[root], x); return; } int mid = (lo + hi) >> 1; upd(l, r, x, root << 1, lo, mid); upd(l, r, x, root << 1 | 1, mid + 1, hi); } ll get(int id, int root = 1, int lo = 0, int hi = M) { return tree[id]; push(root, lo, hi); if (lo == hi) return tree[root]; int mid = (lo + hi) >> 1; if (id <= mid) return max(tree[root], get(id, root << 1, lo, mid)); return max(tree[root], get(id, root << 1 | 1, mid + 1, hi)); } int read() { int ans = 0; bool pos = 1; register char ch = getchar(); for (; ch == ' ' || ch == '\n'; ch = getchar()); if (ch == '-') pos = 0, ch = getchar(); for (; 47 < ch && ch < 58; ch = getchar()) ans = ans * 10 + ch - 48; return (pos ? ans : -ans); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); N = read(), M = read(); FOR(i, 1, N) A[i] = A[i - 1] + read(), S[i] = read(), P[i] = read(); A[N + 1] = INF; FOR(i, 1, M) B[i] = B[i - 1] + read(), T[i] = read(), Q[i] = read(); B[M + 1] = INF; FOR(j, 1, M) ids[upper_bound(A, A + N + 1, T[j] - B[j]) - A].push_back(j); FOR(i, 1, N + 1) { int j = upper_bound(B, B + M + 1, S[i] - A[i]) - B - 1; if (j >= 0) add(0, j, P[i]); vector<int> &vec = ids[i]; FORA(id, vec) add(id, M, Q[id]); if (0 <= j && j < M) vec.insert(lower_bound(vec.begin(), vec.end(), j + 1), j + 1); FORA(id, vec) upd(id, M, get(id - 1)); // FOR(id, 1, M) tree[id] = max(tree[id], tree[id - 1]); // FOR(j, 0, M) { // cerr << i << ' ' << j << ": " << get(j) << endl; // } } cout << get(M) << endl; }

Compilation message (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:28:22: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define FOR(i, a, b) for (int i = a; i <= b; ++i)
                      ^
dishes.cpp:115:5: note: in expansion of macro 'FOR'
     FOR(i, 1, N) A[i] = A[i - 1] + read(), S[i] = read(), P[i] = read(); A[N + 1] = INF;
     ^~~
dishes.cpp:115:74: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     FOR(i, 1, N) A[i] = A[i - 1] + read(), S[i] = read(), P[i] = read(); A[N + 1] = INF;
                                                                          ^
dishes.cpp:28:22: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define FOR(i, a, b) for (int i = a; i <= b; ++i)
                      ^
dishes.cpp:116:5: note: in expansion of macro 'FOR'
     FOR(i, 1, M) B[i] = B[i - 1] + read(), T[i] = read(), Q[i] = read(); B[M + 1] = INF;
     ^~~
dishes.cpp:116:74: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     FOR(i, 1, M) B[i] = B[i - 1] + read(), T[i] = read(), Q[i] = read(); B[M + 1] = INF;
                                                                          ^
#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...