| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 157257 |
2019-10-10T08:50:03 Z |
atoiz |
Two Dishes (JOI19_dishes) |
C++14 |
|
248 ms |
48088 KB |
#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
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 time |
Memory |
Grader output |
| 1 |
Incorrect |
248 ms |
48088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
248 ms |
48088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
248 ms |
48088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
