| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 884829 |
2023-12-08T13:55:36 Z |
thienhx |
Holiday (IOI14_holiday) |
C++17 |
|
472 ms |
10572 KB |
#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using str = string;
using ld = long double;
using db = double;
///--------------------------------
#define F first
#define S second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define mem(f, x) memset(f, x, sizeof(f))
#define uniqueV(x) sort(all(x)), (x).resize(unique(all(x)) - x.begin())
template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }
///--------------------------------
#define PROBLEM "test"
const int MOD = 1e9 + 7; // 998244353;
const ll INF = 1e18;
const ld eps = 1e-9;
const ld PI = acos(-1);
const int dx[4]{0, 1, 0, -1}, dy[4]{1, 0, -1, 0}; // R D L U
const int ddx[4]{-1, 1, 1, -1}, ddy[4]{1, 1, -1, -1}; // UR DR DL UL
///--------------------------------
void precalc();
void solve();
// int main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// if (fopen(PROBLEM".inp", "r")) {
// freopen(PROBLEM".inp", "r", stdin);
// freopen(PROBLEM".out", "w", stdout);
// }
// constexpr bool MULTI_TEST = 0;
// // cout << 100000 << " " << 50000 << " " << 250000 << '\n';
// // for (int i = 0; i < 100000; i++)
// // cout << i + 1 << " ";
// // cout << '\n';
// int t = 1;
// if (MULTI_TEST) cin >> t;
// while (t--)
// solve();
// // cerr << setprecision(3) << fixed;
// // cerr << "[" << 1.0 * clock() / CLOCKS_PER_SEC << "s] ";
// }
///--------------------[PROBLEM SOLUTION]--------------------///
const int maxn = 1e5 + 35;
int fL[maxn * 2], fR[maxn * 2], cnt[maxn * 4];
ll dpL[maxn * 2], dpR[maxn * 2], seg[maxn * 4];
int val[maxn], ind[maxn];
int n, s, d, source, cInd;
vector<int> b;
void Update(int v, int tl, int tr, int l, int r, int x) {
if (l > r) return;
if (tl == l && tr == r) {
seg[v] += b[tl] * x;
cnt[v] += x;
return;
}
int mid = (tl + tr) >> 1;
if (r <= mid)
Update(v << 1, tl, mid, l, r, x);
else if (l > mid)
Update(v << 1 | 1, mid + 1, tr, l, r, x);
seg[v] = seg[v << 1] + seg[v << 1 | 1];
cnt[v] = cnt[v << 1] + cnt[v << 1 | 1];
}
ll Query(int v, int tl, int tr, int k) {
if (tl == tr)
return 1LL * b[tl] * min(cnt[v], k);
int mid = (tl + tr) >> 1;
if (cnt[v << 1 | 1] >= k) return Query(v << 1 | 1, mid + 1, tr, k);
else return seg[v << 1 | 1] + Query(v << 1, tl, mid, k - cnt[v << 1 | 1]);
}
void fixRangeL(int p) {
while (cInd < p)
Update(1, 0, n, ind[cInd], ind[cInd], -1), cInd++;
while (cInd > p)
cInd--, Update(1, 0, n, ind[cInd], ind[cInd], 1);
}
void fixRangeR(int p) {
while (cInd > p)
Update(1, 0, n, ind[cInd], ind[cInd], -1), cInd--;
while (cInd < p)
cInd++, Update(1, 0, n, ind[cInd], ind[cInd], 1);
}
//solve for dp[tl, tr]
void dncR(int tl, int tr, int opl, int opr) {
if (tl > tr) return;
int mid = (tl + tr) >> 1;
for (int i = opl; i <= opr; i++) {
if (mid >= (i - source)) {
fixRangeR(i);
if (maximize(dpR[mid], Query(1, 0, n, mid - (i - source))))
fR[mid] = i;
}
}
dncR(tl, mid - 1, opl, fR[mid]);
dncR(mid + 1, tr, fR[mid], opr);
}
void dncL(int tl, int tr, int opl, int opr) {
if (tl > tr) return;
int mid = (tl + tr) >> 1;
for (int i = opr; i >= opl; i--) {
if (mid >= (source - i)) {
fixRangeL(i);
if (maximize(dpL[mid], Query(1, 0, n, mid - (source - i))))
fL[mid] = i;
}
}
dncL(tl, mid - 1, fL[mid], opr);
dncL(mid + 1, tr, opl, fL[mid]);
}
ll findMaxAttraction(int _n, int _start, int _d, int _attraction[]) {
n = _n, d = _d, s = _start + 1;
for (int i = 1; i <= n; i++) {
val[i] = _attraction[i - 1];
b.pb(val[i]);
}
uniqueV(b);
for (int i = 1; i <= n; i++)
ind[i] = lb(all(b), val[i]) - b.begin();
while (b.size() < n + 1)
b.pb(0);
source = s; cInd = s - 1;
dncR(1, min(2 * (n - s + 1), d), s, n);
fixRangeR(s - 1);
source = s - 1; cInd = s;
dncL(1, min(2 * s, d), 1, s - 1);
ll res = dpR[d];
if (d) maximize(res, dpL[d - 1]);
for (int i = 1; i <= min(2 * (n - s + 1), d); i++) {
int need = i + (fR[i] - (s - 1));
if (d >= need)
maximize(res, dpR[i] + dpL[min(2 * n, d - need)]);
}
for (int i = 1; i <= min(2 * s, d); i++) {
int need = i + ((s - 1) - fL[i] + 2);
if (d >= need)
maximize(res, dpL[i] + dpR[min(2 * n, d - need)]);
}
return res;
}
void solve() {
}
Compilation message
holiday.cpp: In function 'll findMaxAttraction(int, int, int, int*)':
holiday.cpp:170:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
170 | while (b.size() < n + 1)
| ~~~~~~~~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 3 |
Correct |
1 ms |
5208 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4936 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4956 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
287 ms |
7920 KB |
Output is correct |
| 2 |
Correct |
290 ms |
5588 KB |
Output is correct |
| 3 |
Correct |
285 ms |
8140 KB |
Output is correct |
| 4 |
Correct |
287 ms |
8136 KB |
Output is correct |
| 5 |
Correct |
304 ms |
7364 KB |
Output is correct |
| 6 |
Correct |
81 ms |
5940 KB |
Output is correct |
| 7 |
Correct |
161 ms |
6372 KB |
Output is correct |
| 8 |
Correct |
192 ms |
6428 KB |
Output is correct |
| 9 |
Correct |
55 ms |
5552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
5 ms |
4956 KB |
Output is correct |
| 3 |
Correct |
7 ms |
5060 KB |
Output is correct |
| 4 |
Correct |
8 ms |
4956 KB |
Output is correct |
| 5 |
Correct |
7 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4956 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 8 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 9 |
Correct |
2 ms |
4956 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
279 ms |
7980 KB |
Output is correct |
| 2 |
Correct |
406 ms |
10572 KB |
Output is correct |
| 3 |
Correct |
89 ms |
5848 KB |
Output is correct |
| 4 |
Correct |
6 ms |
4956 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 6 |
Correct |
2 ms |
4984 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 8 |
Correct |
472 ms |
7896 KB |
Output is correct |
| 9 |
Correct |
468 ms |
7968 KB |
Output is correct |
