# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
37082 |
2017-12-21T05:38:17 Z |
petil |
Holiday (IOI14_holiday) |
C++14 |
|
1879 ms |
20064 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll Ldir[350005], Rdir[350005], ans;
int n, st, d, vi[100005], po[100005];
struct BIT{
vector<int> cnt;
vector<ll>tree;
BIT(){}
BIT(int V) :cnt(4*V), tree(4*V){
fill(cnt.begin(), cnt.end() ,0);
fill(tree.begin(), tree.end(), 0);
}
void update(int x, int L, int R, int idx, int val){
if(idx<L || R < idx)return;
if(L==R && L==idx){
if(val<0){
cnt[x] = tree[x] = 0;
}
else{
cnt[x] =1 ;tree[x] = val;
}
return;
}
int mid = (L+R)>>1;
if(idx <=mid) update(x+x, L, mid, idx, val);
else update(x+x+1, mid+1, R, idx, val);
cnt[x] = cnt[x+x] + cnt[x+x+1];
tree[x] = tree[x+x] + tree[x+x+1];
}
ll query(int x, int L , int R, int topk){
if(topk==0)return 0;
if(L==R)return tree[x];
int mid = (L+R)>>1;
if(cnt[x+x] <=topk){
return tree[x+x] + query(x+x+1, mid+1, R, topk - cnt[x+x]);
}
else{
return query(x+x, L, mid, topk);
}
}
}bit;
void dp1(int LT, int RT, int c1, int c2, ll dir[])
{
if(LT>RT)return;
int T = (LT+RT)>>1;
dir[T] = -1;
int cc = -1;
for(int i=c1; i<=c2; i++){
bit.update(1, 1, n, po[i], vi[i]);
int tp = T - (i-st);
tp = max(tp, 0);
ll ss = bit.query(1, 1, n, tp);
if(dir[T] < ss){
dir[T] = ss; cc = i;
}
}
for(int i=c1; i<=c2; i++)bit.update(1,1, n, po[i], -1);
if(LT==RT)return;
dp1(LT, T-1, c1, cc, dir);
for(int i = c1; i<cc; i++)bit.update(1,1, n, po[i], vi[i]);
dp1(T+1, RT, cc, c2, dir);
for(int i = c1; i<cc; i++)bit.update(1,1, n, po[i], -1);
}
void dp2(int LT, int RT, int c1, int c2, ll dir[]){
if(LT>RT)return;
int T = (LT+RT)>>1;
dir[T] = -1;
int cc = -1;
for(int i=c1; i>=c2; i--){
bit.update(1, 1, n, po[i], vi[i]);
int tp = T - 2*(st-i);
tp = max(tp, 0);
ll ss = bit.query(1, 1, n, tp);
if(dir[T] < ss){
dir[T]= ss; cc = i;
}
}
for(int i=c1; i>=c2; i--){
bit.update(1, 1, n, po[i], -1);
}
dp2(LT, T-1, c1, cc, dir);
for(int i=c1; i>cc; i--){
bit.update(1, 1, n, po[i], vi[i]);
}
dp2(T+1, RT, cc, c2, dir);
for(int i=c1; i>cc; i--){
bit.update(1, 1, n, po[i], -1);
}
}
void go()
{
vector<pair<int, int> >tmp;
for(int i=1 ;i<=n; i++){
tmp.push_back({-vi[i], i});
}
sort(tmp.begin(), tmp.end());
for(int i=0; i<tmp.size() ;i++){
po[tmp[i].second] = i+1;
}
bit = BIT(n+5);
dp1(1, d, st, n, Rdir);
if(st>1){
bit = BIT(n+5);
dp2(1, d, st-1, 1, Ldir);
}
else{
for(int i=0; i<=d; i++)Ldir[i] = 0;
}
for(int i=0; i<=d; i++){
ans = max(ans, Ldir[i] + Rdir[d-i]);
/// cout<<i<<" " <<Ldir[i] <<" "<< Rdir[i]<<endl;
}
}
//FILE *fi = freopen("sample-4.in", "r", stdin);
ll findMaxAttraction(int N, int start, int dd, int attr[]){
n = N;
st = start;++st;
d = dd;
for(int i=0; i<n; i++){
vi[i+1] = attr[i];
}
ans=0;
go();
reverse(vi+1, vi+n+1);
st = n+1- st;
go();
return ans;
}
Compilation message
holiday.cpp: In function 'void go()':
holiday.cpp:104:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<tmp.size() ;i++){
^
grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
int i, n_s;
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
8552 KB |
Output is correct |
2 |
Correct |
0 ms |
8548 KB |
Output is correct |
3 |
Correct |
0 ms |
8552 KB |
Output is correct |
4 |
Correct |
0 ms |
8548 KB |
Output is correct |
5 |
Correct |
0 ms |
8552 KB |
Output is correct |
6 |
Correct |
0 ms |
8548 KB |
Output is correct |
7 |
Correct |
0 ms |
8556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1483 ms |
20064 KB |
Output is correct |
2 |
Correct |
1339 ms |
20064 KB |
Output is correct |
3 |
Correct |
1513 ms |
20056 KB |
Output is correct |
4 |
Correct |
1333 ms |
20056 KB |
Output is correct |
5 |
Correct |
1873 ms |
19268 KB |
Output is correct |
6 |
Correct |
606 ms |
11776 KB |
Output is correct |
7 |
Correct |
909 ms |
14440 KB |
Output is correct |
8 |
Correct |
996 ms |
15456 KB |
Output is correct |
9 |
Correct |
476 ms |
11024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
8980 KB |
Output is correct |
2 |
Correct |
19 ms |
8976 KB |
Output is correct |
3 |
Correct |
23 ms |
8976 KB |
Output is correct |
4 |
Correct |
26 ms |
8956 KB |
Output is correct |
5 |
Correct |
26 ms |
8856 KB |
Output is correct |
6 |
Correct |
3 ms |
8688 KB |
Output is correct |
7 |
Correct |
3 ms |
8688 KB |
Output is correct |
8 |
Correct |
3 ms |
8692 KB |
Output is correct |
9 |
Correct |
3 ms |
8688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1526 ms |
20060 KB |
Output is correct |
2 |
Correct |
1579 ms |
20060 KB |
Output is correct |
3 |
Correct |
549 ms |
13868 KB |
Output is correct |
4 |
Correct |
16 ms |
8952 KB |
Output is correct |
5 |
Correct |
3 ms |
8692 KB |
Output is correct |
6 |
Correct |
3 ms |
8692 KB |
Output is correct |
7 |
Correct |
3 ms |
8688 KB |
Output is correct |
8 |
Correct |
1879 ms |
20052 KB |
Output is correct |
9 |
Correct |
1879 ms |
20052 KB |
Output is correct |