| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 241570 |
2020-06-24T13:35:12 Z |
abacaba |
Holiday (IOI14_holiday) |
C++14 |
|
1911 ms |
8856 KB |
#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define emb emplace_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline T range(T l, T r) {
return uniform_int_distribution<T>(l, r)(rng);
}
inline void setin(string s) {
freopen(s.c_str(), "r", stdin);
}
inline void setout(string s) {
freopen(s.c_str(), "w", stdout);
}
template <typename T> void Min(T &a, T b) {
a = min(a, b);
}
template <typename T> void Max(T &a, T b) {
a = max(a, b);
}
const int inf = 1e9;
const int mod = 998244353;
const int D = 3e5 + 15;
const int N = 1e5 + 5;
int a[N];
vector <int> comp;
pair <ll, int> f[D], g[D];
bool used[N];
struct segment_tree {
ll sum[N << 2];
int cnt[N << 2];
segment_tree() {
memset(sum, 0, sizeof(sum));
memset(cnt, 0, sizeof(cnt));
}
void update(int v, int tl, int tr, int pos, int val) {
cnt[v] += val, sum[v] += comp[pos - 1] * val;
if(tl != tr) {
int mid = tl + tr >> 1;
if(pos <= mid)
update(v << 1, tl, mid, pos, val);
else
update(v << 1 | 1, mid + 1, tr, pos, val);
}
}
inline ll get_sum_of_k(int v, int tl, int tr, int k) {
if(k <= 0)
return 0;
int cur_cnt = cnt[v];
if(cur_cnt <= k)
return sum[v];
if(tl == tr)
return 1LL * k * comp[tl - 1];
int mid = tl + tr >> 1;
int cntr = cnt[v << 1 | 1];
return get_sum_of_k(v << 1, tl, mid, k - cntr) + get_sum_of_k(v << 1 | 1, mid + 1, tr, k);
}
} t;
inline int gt(int x) {
return lower_bound(comp.begin(), comp.end(), x) - comp.begin() + 1;
}
inline void add(int i) {
if(!used[i])
t.update(1, 1, comp.size(), gt(a[i]), 1);
used[i] = true;
}
inline void del(int i) {
if(used[i])
t.update(1, 1, comp.size(), gt(a[i]), -1);
used[i] = false;
}
inline void del(int l, int r) {
for(int i = l; i <= r; ++i)
del(i);
}
inline void add(int l, int r) {
for(int i = l; i <= r; ++i)
add(i);
}
void calc_f(int start, int l, int r, int opt_l, int opt_r, int coef) {
int mid = l + r >> 1;
f[mid] = {-1, -inf};
for(int i = opt_l; i <= opt_r; ++i) {
add(i);
Max(f[mid], mp(t.get_sum_of_k(1, 1, comp.size(), mid - coef * (i - start)), -i));
}
f[mid].se *= -1;
assert(f[mid].f != -1);
del(opt_l, opt_r);
if(l < mid)
calc_f(start, l, mid - 1, opt_l, f[mid].se, coef);
add(opt_l, f[mid].se);
if(mid < r)
calc_f(start, mid + 1, r, f[mid].se, opt_r, coef);
add(f[mid].se, opt_r);
}
void calc_g(int start, int l, int r, int opt_l, int opt_r, int coef = 1) {
int mid = l + r >> 1;
g[mid] = {-1, -inf};
for(int i = opt_r; i >= opt_l; --i) {
add(i);
Max(g[mid], mp(t.get_sum_of_k(1, 1, comp.size(), mid - coef * (start - 1 - i)), i));
}
assert(g[mid].f != -1);
del(opt_l, opt_r);
if(l < mid)
calc_g(start, l, mid - 1, g[mid].se, opt_r, coef);
add(g[mid].se, opt_r);
if(mid < r)
calc_g(start, mid + 1, r, opt_l, g[mid].se, coef);
add(opt_l, g[mid].se);
}
long long findMaxAttraction(int n, int start, int d, int attraction[]) {
for(int i = 0; i < n; ++i)
a[i+1] = attraction[i];
++start;
for(int i = 1; i <= n; ++i)
comp.pb(a[i]);
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
ll ans = 0;
for(int i = start; i <= n; ++i) {
add(i);
Max(ans, t.get_sum_of_k(1, 1, comp.size(), d - (i - start)));
}
del(start, n);
for(int i = start; i >= 1; --i) {
add(i);
Max(ans, t.get_sum_of_k(1, 1, comp.size(), d - (start - i)));
}
del(1, start);
if(start == 1 || start == n)
return ans;
calc_f(start, 0, d, start, n, 2);
del(start, n);
calc_g(start, 0, d, 1, start - 1, 1);
del(1, start - 1);
// for(int i = 0; i <= d; ++i)
// cout << i << ' ' << g[i].f << ' ' << g[i].se << endl;
// return -1;
for(int x = 0; x <= d; ++x) {
int i = f[x].se;
int lef = d - x - 1;
if(lef >= 0)
Max(ans, g[lef].f + f[x].f);
}
calc_f(start, 0, d, start, n, 1);
del(start, n);
calc_g(start, 0, d, 1, start - 1, 2);
for(int x = 0; x <= d; ++x) {
int i = g[x].se;
int lef = d - x - 2;
if(lef >= 0)
Max(ans, f[lef].f + g[x].f);
}
return ans;
}
Compilation message
holiday.cpp: In member function 'void segment_tree::update(int, int, int, int, int)':
holiday.cpp:81:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = tl + tr >> 1;
~~~^~~~
holiday.cpp: In member function 'long long int segment_tree::get_sum_of_k(int, int, int, int)':
holiday.cpp:99:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = tl + tr >> 1;
~~~^~~~
holiday.cpp: In function 'void calc_f(int, int, int, int, int, int)':
holiday.cpp:134:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
holiday.cpp: In function 'void calc_g(int, int, int, int, int, int)':
holiday.cpp:156:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:213:13: warning: unused variable 'i' [-Wunused-variable]
int i = f[x].se;
^
holiday.cpp:225:13: warning: unused variable 'i' [-Wunused-variable]
int i = g[x].se;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
4992 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5120 KB |
Output is correct |
| 3 |
Correct |
7 ms |
5120 KB |
Output is correct |
| 4 |
Correct |
7 ms |
4992 KB |
Output is correct |
| 5 |
Correct |
7 ms |
4992 KB |
Output is correct |
| 6 |
Correct |
8 ms |
5248 KB |
Output is correct |
| 7 |
Correct |
7 ms |
4992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
6652 KB |
Output is correct |
| 2 |
Correct |
19 ms |
6652 KB |
Output is correct |
| 3 |
Correct |
21 ms |
6652 KB |
Output is correct |
| 4 |
Correct |
19 ms |
6652 KB |
Output is correct |
| 5 |
Correct |
40 ms |
6652 KB |
Output is correct |
| 6 |
Correct |
15 ms |
5632 KB |
Output is correct |
| 7 |
Correct |
22 ms |
6016 KB |
Output is correct |
| 8 |
Correct |
26 ms |
6144 KB |
Output is correct |
| 9 |
Correct |
13 ms |
5504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
8 ms |
5120 KB |
Output is correct |
| 3 |
Correct |
8 ms |
5120 KB |
Output is correct |
| 4 |
Correct |
37 ms |
5248 KB |
Output is correct |
| 5 |
Correct |
34 ms |
5248 KB |
Output is correct |
| 6 |
Correct |
15 ms |
5120 KB |
Output is correct |
| 7 |
Correct |
13 ms |
5120 KB |
Output is correct |
| 8 |
Correct |
14 ms |
5120 KB |
Output is correct |
| 9 |
Correct |
11 ms |
5120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
7292 KB |
Output is correct |
| 2 |
Correct |
45 ms |
7288 KB |
Output is correct |
| 3 |
Correct |
657 ms |
6512 KB |
Output is correct |
| 4 |
Correct |
30 ms |
5120 KB |
Output is correct |
| 5 |
Correct |
13 ms |
5120 KB |
Output is correct |
| 6 |
Correct |
13 ms |
5120 KB |
Output is correct |
| 7 |
Correct |
11 ms |
5120 KB |
Output is correct |
| 8 |
Correct |
1911 ms |
8820 KB |
Output is correct |
| 9 |
Correct |
1888 ms |
8856 KB |
Output is correct |
