| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 794266 |
2023-07-26T11:45:56 Z |
Ronin13 |
Holiday (IOI14_holiday) |
C++17 |
|
1843 ms |
36912 KB |
#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 400001;
struct node{
ll ones, sum;
node(){
ones = sum = 0;
}
}t[4 * nmax];
void update(int v, int l, int r, int pos, int val){
if(l > pos || r < pos)
return;
if(l == r){
if(val == 0) t[v].sum = t[v].ones = 0;
else t[v].sum = val, t[v].ones = 1;
return;
}
int m = (l + r) / 2;
update(2 * v, l, m, pos, val);
update(2 * v+ 1, m + 1, r, pos, val);
t[v].ones = t[2 * v].ones + t[2 * v + 1].ones;
t[v].sum = t[2 * v].sum + t[2 * v + 1].sum;
}
ll getfirst(int v, int l, int r, int val, ll sum = 0){
if(l == r){
return sum;
}
int m = (l + r) / 2;
if(t[2 * v].ones <= val){
return
getfirst(2 * v + 1, m + 1,r, val - t[2 * v].ones, sum + t[2 * v].sum);
}
return getfirst(2 * v, l, m, val, sum);
}
int s;
int d;
int n;
ll ans[nmax][4];
ll pos[nmax], val[nmax];
void divi1(int l, int r, int optl, int optr, int ind){
if(l > r)
return;
int m = (l + r) / 2;
ll cur = 0, opti;
cur = -1e18;
for(int i = optr; i >= optl; i--){
ll x = s - i;
x *= ind / 2 + 1;
update(1, 0, n, pos[i], val[i]);
if(m < x) continue;
if(cur < getfirst(1, 0, n, m - x)){
cur = getfirst(1, 0, n, m - x);
opti = i;
}
}
for(int i = optr; i >= optl; i--)
update(1, 0, n, pos[i], 0);
ans[m][ind] = cur;
divi1(l, m - 1, opti, optr, ind);
for(int i = optr; i > opti; --i)
update(1, 0, n, pos[i], val[i]);
divi1(m + 1, r, optl, opti, ind);
for(int i = optr; i > opti; --i)
update(1, 0, n, pos[i], 0);
}
//win wasvla dabrunebis gareshe
void divi2(int l, int r, int optl, int optr, int ind){
if(l > r)
return;
int m = (l + r) / 2;
ll cur = -1e18, opti;
for(int i = optl; i <= optr; i++){
int x = i - s;
x *= (ind / 2 + 1);
// cout << x << ' ';
update(1, 0, n, pos[i], val[i]);
if(m < x) continue;
ll y = getfirst(1, 0, n, m - x);
if(y > cur)
cur = y, opti = i;
}
for(int i = optl; i <= optr; i++)
update(1, 0, n, pos[i], 0);
ans[m][ind] = cur;
divi2(l, m - 1, optl, opti, ind);
for(int i = optl; i < opti; i++){
update(1, 0, n ,pos[i], val[i]);
}
divi2(m + 1, r, opti, optr, ind);
for(int i = optl; i < opti; i++)
update(1, 0, n, pos[i], 0);
}
long long int findMaxAttraction(int N, int start, int d, int a[]) {
n = N;
pii b[n + 1];
s = start;
for(int i= 0; i < n; i++){
val[i] = a[i];
b[i] = {a[i], i};
if(i == s) b[i].f = 0;
}
sort(b, b + n);
reverse(b, b + n);
for(int i = 0; i < n; ++i)
pos[b[i].s] = i;
val[s] = 0;
divi2(0, d, s, n - 1, 3);
divi1(0, d, 0, s, 0);
divi1(0, d, 0, s, 2);
divi2(0, d, s, n - 1, 1);
//cout << t[1].sum;
ll res = 0;
for(int i = 0; i <= d; i++){
res = max(res, ans[i][3] + ans[d - i][0]);
res = max(res, ans[i][2] + ans[d - i][1]);
if(i < d){
ll x = max(x, ans[i][3]+ ans[d - i - 1][0]);
x = max(ans[i][2] + ans[d - i - 1][1], x);
res = max(res, x + a[s]);
}
}
return res;
}
Compilation message
holiday.cpp: In function 'void divi1(int, int, int, int, int)':
holiday.cpp:59:17: warning: 'opti' may be used uninitialized in this function [-Wmaybe-uninitialized]
59 | ll cur = 0, opti;
| ^~~~
holiday.cpp: In function 'void divi2(int, int, int, int, int)':
holiday.cpp:86:21: warning: 'opti' may be used uninitialized in this function [-Wmaybe-uninitialized]
86 | ll cur = -1e18, opti;
| ^~~~
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:138:16: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
138 | ll x = max(x, ans[i][3]+ ans[d - i - 1][0]);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
25684 KB |
Output is correct |
| 2 |
Correct |
11 ms |
25744 KB |
Output is correct |
| 3 |
Correct |
10 ms |
25728 KB |
Output is correct |
| 4 |
Correct |
10 ms |
25684 KB |
Output is correct |
| 5 |
Correct |
10 ms |
25744 KB |
Output is correct |
| 6 |
Correct |
10 ms |
25676 KB |
Output is correct |
| 7 |
Correct |
10 ms |
25712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1693 ms |
34556 KB |
Output is correct |
| 2 |
Correct |
1327 ms |
34608 KB |
Output is correct |
| 3 |
Correct |
1638 ms |
34492 KB |
Output is correct |
| 4 |
Correct |
1311 ms |
34532 KB |
Output is correct |
| 5 |
Correct |
1626 ms |
32260 KB |
Output is correct |
| 6 |
Correct |
676 ms |
32208 KB |
Output is correct |
| 7 |
Correct |
892 ms |
29916 KB |
Output is correct |
| 8 |
Correct |
1043 ms |
30008 KB |
Output is correct |
| 9 |
Correct |
570 ms |
33740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
25988 KB |
Output is correct |
| 2 |
Correct |
39 ms |
26064 KB |
Output is correct |
| 3 |
Correct |
39 ms |
26036 KB |
Output is correct |
| 4 |
Correct |
36 ms |
25920 KB |
Output is correct |
| 5 |
Correct |
34 ms |
25940 KB |
Output is correct |
| 6 |
Correct |
15 ms |
25788 KB |
Output is correct |
| 7 |
Correct |
15 ms |
25784 KB |
Output is correct |
| 8 |
Correct |
15 ms |
25792 KB |
Output is correct |
| 9 |
Correct |
15 ms |
25748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1777 ms |
36804 KB |
Output is correct |
| 2 |
Correct |
1843 ms |
36912 KB |
Output is correct |
| 3 |
Correct |
492 ms |
27488 KB |
Output is correct |
| 4 |
Correct |
32 ms |
25960 KB |
Output is correct |
| 5 |
Correct |
15 ms |
25780 KB |
Output is correct |
| 6 |
Correct |
15 ms |
25684 KB |
Output is correct |
| 7 |
Correct |
15 ms |
25804 KB |
Output is correct |
| 8 |
Correct |
1617 ms |
30484 KB |
Output is correct |
| 9 |
Correct |
1601 ms |
30480 KB |
Output is correct |
