| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1106002 |
2024-10-28T17:05:07 Z |
VinhLuu |
Holiday (IOI14_holiday) |
C++17 |
|
413 ms |
9664 KB |
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define fi first
#define se second
#include "holiday.h"
using namespace std;
typedef pair<int,int> pii;
const int N = 1e5 + 5;
int n, S, K;
ll a[N];
ll st[N << 2], T[N << 2];
vector<ll> rrh;
int m, b[N];
void update(int i,int l,int r,int u,int x,int t){
if(l > r || r < u || u < l) return;
if(l == r){
T[i] += t;
st[i] += x * t;
return;
}
int mid = (l + r) / 2;
update(i << 1, l, mid, u, x, t);
update(i << 1|1, mid + 1, r, u, x, t);
st[i] = st[i << 1] + st[i << 1|1];
T[i] = T[i << 1] + T[i << 1|1];
}
ll wr, ret;
int query(int i,int l,int r,int u){
if(l > r || r < u || u < l) return 0;
if(l == r) return st[i];
int mid = (l + r) / 2;
return query(i << 1, l, mid, u) + query(i << 1|1, mid + 1, r, u);
}
void get(int i,int l,int r){
if(!wr) return;
if(l == r){
if(!T[i]) return;
ret += min(wr, T[i]) * (st[i] / T[i]);
wr -= min(wr, T[i]);
return;
}
if(T[i] <= wr){
wr -= T[i];
ret += st[i];
return;
}
int mid = (l + r) / 2;
if(T[i << 1|1] <= wr){
wr -= T[i << 1|1];
ret += st[i << 1|1];
if(wr) get(i << 1, l, mid);
}else{
get(i << 1|1, mid + 1, r);
}
}
void pre(){
for(int i = 1; i <= n; i ++) rrh.push_back(a[i]);
sort(all(rrh));
rrh.resize(unique(all(rrh)) - rrh.begin());
m = (int)rrh.size();
for(int i = 1; i <= n; i ++) b[i] = lower_bound(all(rrh), a[i]) - rrh.begin() + 1;
}
namespace AC{
ll ans = 0;
int le, ri, we;
void dfs(int l,int r,int pl,int pr){
if(l > r) return;
int mid = (l + r) / 2;
while(we < mid){
we++;
// cerr << we << " addrrr\n";
update(1, 1, m, b[we], a[we], 1);
}
while(we > mid){
// cerr << we << " subrrr\n";
update(1, 1, m, b[we], a[we], -1);
we--;
}
// cerr << mid << " " << pl << " " << pr << " " << le << " " << ri << " t\n";
while(le > pl){
le--;
// cerr << le << " addl\n";
update(1, 1, m, b[le], a[le], 1);
}
while(le < pl){
update(1, 1, m, b[le], a[le], -1);
// cerr << le << " subl\n";
le++;
}
// cerr << mid << " " << l << " " << r << " " << pl << " " << pr << " " << le << " " << ri << " " << we << " e\n";
// << " " << le << " " << ri << " " <<we << " " << mid<< " y\n";
ll tmp = 0, pos = pr;
while(le <= pr){
wr = K - min(mid - S, S - le) - (mid - le);
if(wr >= 0){
ret = 0;
int last = wr;
get(1, 1, m);
// cerr << last << " " << le << " " << ret << " k\n";
// for(int i = 1; i <= m; i ++) cerr << query(1, 1, m, i) << " ";
// cerr << "\n";
if(ret > tmp){
tmp = ret;
pos = le;
}
}
// cerr << le << " sub\n";
update(1, 1, m, b[le], a[le], -1);
le++;
}
// cerr << tmp << " " << pos << " ptptp\n";
ans = max(ans, tmp);
dfs(l, mid - 1, pl, pos);
dfs(mid + 1, r, pos, pr);
}
ll solve(){
ans = 0;
for(int i = S; i <= n; i ++){
update(1, 1, m, b[i], a[i], 1);
wr = K - (i - S);
if(wr < 0) continue;
ret = 0;
get(1, 1, m);
ans = max(ans, ret);
}
for(int i = S; i <= n; i ++) update(1, 1, m, b[i], a[i], -1);
we = S;
// cerr << we << " add\n";
update(1, 1, m, b[S], a[S], 1);
if(1 < S){
int mk = -1;
for(int i = S; i <= n; i ++){
wr = K - min(S - (S - 1), i - S) - (i - (S - 1));
if(wr < 0) break;
mk = i;
}
if(mk == -1) return ans;
le = 1, ri = 1;
for(int i = 1; i < S; i ++) update(1, 1, m, b[i], a[i], 1);
dfs(S, mk, 1, S - 1);
}
return ans;
}
}
ll findMaxAttraction(int _n, int start, int d, int attraction[]) {
n = _n;
S = start + 1;
K = d;
for(int i = 0; i < n; i ++) a[i + 1] = attraction[i];
pre();
return AC :: solve();
}
//#define lpv
#ifdef lpv
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "v"
if(fopen(task ".inp","r")){
freopen(task ".inp","r",stdin);
freopen(task ".out","w",stdout);
}
int _n, start, d;
int attraction[100000];
int i, n_s;
n_s = scanf("%d %d %d", &_n, &start, &d);
for (i = 0 ; i < _n; ++i) {
n_s = scanf("%d", &attraction[i]);
}
printf("%lld\n", findMaxAttraction(_n, start, d, attraction));
return 0;
}
#endif // lpv
Compilation message
holiday.cpp: In function 'void AC::dfs(int, int, int, int)':
holiday.cpp:117:13: warning: unused variable 'last' [-Wunused-variable]
117 | int last = wr;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4944 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4944 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4944 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4944 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4944 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4944 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4944 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
6868 KB |
Output is correct |
| 2 |
Correct |
10 ms |
6852 KB |
Output is correct |
| 3 |
Correct |
12 ms |
6852 KB |
Output is correct |
| 4 |
Correct |
12 ms |
6852 KB |
Output is correct |
| 5 |
Correct |
27 ms |
6852 KB |
Output is correct |
| 6 |
Correct |
9 ms |
5748 KB |
Output is correct |
| 7 |
Correct |
17 ms |
5832 KB |
Output is correct |
| 8 |
Correct |
19 ms |
6344 KB |
Output is correct |
| 9 |
Correct |
8 ms |
5324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4944 KB |
Output is correct |
| 4 |
Correct |
6 ms |
4956 KB |
Output is correct |
| 5 |
Correct |
7 ms |
4944 KB |
Output is correct |
| 6 |
Correct |
2 ms |
4940 KB |
Output is correct |
| 7 |
Correct |
2 ms |
5112 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4944 KB |
Output is correct |
| 9 |
Correct |
2 ms |
4944 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
7612 KB |
Output is correct |
| 2 |
Correct |
40 ms |
9432 KB |
Output is correct |
| 3 |
Correct |
158 ms |
8136 KB |
Output is correct |
| 4 |
Correct |
7 ms |
5112 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4944 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4944 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4944 KB |
Output is correct |
| 8 |
Correct |
392 ms |
9664 KB |
Output is correct |
| 9 |
Correct |
413 ms |
9660 KB |
Output is correct |
