| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 145607 |
2019-08-20T13:43:32 Z |
maruii |
코알라 (JOI13_koala) |
C++14 |
|
129 ms |
8084 KB |
#include <bits/stdc++.h>
using namespace std;
#define eack emplace_back
#define all(x) (x).begin(), (x).end()
vector<int> xx;
const int SIZE = 1 << 17;
struct ST {
struct Node {
long long v, lazy;
} A[2 * SIZE];
int sz;
void init() {
for (int i = 0; i < 2 * SIZE; ++i) A[i].v = -4e18;
}
void lazydown(int nn, int ns, int m, int ne) {
A[nn << 1].v += A[nn].lazy;
A[nn << 1].lazy += A[nn].lazy;
A[nn << 1 | 1].v += A[nn].lazy;
A[nn << 1 | 1].lazy += A[nn].lazy;
A[nn].lazy = 0;
}
void updateP(int nn, int ns, int ne, int x, long long v) {
if (x > ne || x < ns) return;
auto &cur = A[nn];
if (ns == ne) {
cur.v = max(cur.v, v);
return;
}
int m = ns + ne >> 1;
lazydown(nn, ns, m, ne);
updateP(nn << 1, ns, m, x, v);
updateP(nn << 1 | 1, m + 1, ne, x, v);
cur.v = max(A[nn << 1].v, A[nn << 1 | 1].v);
}
void update(int nn, int ns, int ne, int s, int e, int v) {
if (ns > e || ne < s) return;
auto &cur = A[nn];
if (s <= ns && ne <= e) {
cur.v += v;
cur.lazy += v;
return;
}
int m = ns + ne >> 1;
lazydown(nn, ns, m, ne);
update(nn << 1, ns, m, s, e, v);
update(nn << 1 | 1, m + 1, ne, s, e, v);
cur.v = max(A[nn << 1].v, A[nn << 1 | 1].v);
}
void updateP(int x, int v) {
updateP(1, 0, sz, x, v);
}
void update(int s, int e, int v) {
update(1, 0, sz, s, e, v);
}
long long query() {
lazydown(1, 0, sz >> 1, sz);
return A[1].v;
}
} seg;
int T[100005], B[100005], S[100005];
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int K, M, D, A, N; cin >> K >> M >> D >> A >> N;
for (int i = 1; i <= N; ++i)
cin >> T[i] >> B[i];
T[0] = K; T[N + 1] = M;
for (int i = 0; i <= N + 1; ++i) xx.eack(T[i] % D);
sort(all(xx));
xx.erase(unique(all(xx)), xx.end());
for (int i = 0; i <= N + 1; ++i) {
S[i] = lower_bound(all(xx), T[i] % D) - xx.begin();
}
seg.init();
seg.sz = xx.size() - 1;
seg.updateP(S[0], 0);
long long t = 0;
for (int i = 1; i <= N + 1; ++i) {
seg.update(0, seg.sz, -1ll * (T[i] - T[i - 1]) / D * A);
if (S[i] >= S[i - 1]) seg.update(S[i - 1], S[i] - 1, -A);
else {
seg.update(S[i - 1], seg.sz, -A);
seg.update(0, S[i] - 1, -A);
}
t = seg.query() + B[i];
seg.updateP(S[i], t);
}
cout << t;
return 0;
}
Compilation message
koala.cpp: In member function 'void ST::updateP(int, int, int, int, long long int)':
koala.cpp:31:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = ns + ne >> 1;
~~~^~~~
koala.cpp: In member function 'void ST::update(int, int, int, int, int, int)':
koala.cpp:45:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = ns + ne >> 1;
~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
68 ms |
8028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
129 ms |
8084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
