# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
992033 |
2024-06-03T16:07:55 Z |
huutuan |
Holiday (IOI14_holiday) |
C++14 |
|
2463 ms |
8020 KB |
#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define int long long
template<class T, class U>
using ordered_set=tree<T, null_type, U, rb_tree_tag, tree_order_statistics_node_update>;
struct DS{
int count;
int sum;
ordered_set<pair<int, int>, greater<pair<int, int>>> st;
void clear(){
// cerr << "clear" << endl;
count=0;
sum=0;
st.clear();
}
DS (){
clear();
}
int size(){
return st.size();
}
void set_count(int new_count){
new_count=max(new_count, 0ll);
while (count<new_count){
if (size()>count) sum+=st.find_by_order(count)->first;
++count;
}
while (count>new_count){
--count;
if (size()>count) sum-=st.find_by_order(count)->first;
}
}
void insert(pair<int, int> x){
// cerr << "insert " << x.second << endl;
int id=st.order_of_key(x);
if (id<count){
sum+=x.first;
st.insert(x);
if (size()>count) sum-=st.find_by_order(count)->first;
}else st.insert(x);
}
void erase(pair<int, int> x){
// cerr << "erase " << x.second << endl;
int id=st.order_of_key(x);
if (id<count){
sum-=x.first;
st.erase(x);
if (size()>=count) sum+=st.find_by_order(count-1)->first;
}else st.erase(x);
}
} st;
const int N=1e5;
int a[N], n, start, d, ans;
void dnc(int l, int r, int optl, int optr){
if (l>r) return;
int mid=(l+r)>>1;
for (int i=mid; i<r; ++i) st.insert({a[i], i});
st.set_count(d-(start-mid)-(optl-mid));
int optmid=optl, optval=st.sum;
for (int i=optl+1; i<=optr; ++i){
st.set_count(d-(start-mid)-(i-mid));
st.insert({a[i], i});
if (optval<st.sum){
optmid=i;
optval=st.sum;
}
}
ans=max(ans, optval);
for (int i=mid; i<r; ++i) st.erase({a[i], i});
for (int i=optl+1; i<=optr; ++i) st.erase({a[i], i});
if (mid>0){
// r -> optl -> mid - 1 -> optl
for (int i=mid-1; i<r; ++i) st.insert({a[i], i});
dnc(l, mid-1, optl, optmid);
for (int i=mid-1; i<r; ++i) st.erase({a[i], i});
}
if (mid+1<n){
// r -> optl -> r -> optmid
for (int i=optl+1; i<=optmid; ++i) st.insert({a[i], i});
// r -> optmid
dnc(mid+1, r, optmid, optr);
for (int i=optl+1; i<=optmid; ++i) st.erase({a[i], i});
}
}
void solve(){
for (int l=start; l>=0; --l){
st.set_count(d-(start-l));
st.insert({a[l], l});
ans=max(ans, st.sum);
}
st.clear();
st.insert({a[start], start});
dnc(0, start, start, n-1);
st.clear();
}
int findMaxAttraction(int32_t _n, int32_t _start, int32_t _d, int32_t _a[]) {
n=_n; start=_start; d=_d;
for (int i=0; i<n; ++i) a[i]=_a[i];
solve();
reverse(a, a+n);
start=n-start-1;
solve();
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
0 ms |
604 KB |
Output is correct |
3 |
Correct |
0 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
0 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
692 KB |
Output is correct |
7 |
Correct |
0 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
831 ms |
7840 KB |
Output is correct |
2 |
Correct |
706 ms |
7848 KB |
Output is correct |
3 |
Correct |
759 ms |
8020 KB |
Output is correct |
4 |
Correct |
744 ms |
7848 KB |
Output is correct |
5 |
Correct |
923 ms |
7504 KB |
Output is correct |
6 |
Correct |
198 ms |
2652 KB |
Output is correct |
7 |
Correct |
501 ms |
4188 KB |
Output is correct |
8 |
Correct |
566 ms |
4956 KB |
Output is correct |
9 |
Correct |
132 ms |
2136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
1040 KB |
Output is correct |
2 |
Correct |
10 ms |
860 KB |
Output is correct |
3 |
Correct |
10 ms |
860 KB |
Output is correct |
4 |
Correct |
30 ms |
860 KB |
Output is correct |
5 |
Correct |
26 ms |
860 KB |
Output is correct |
6 |
Correct |
5 ms |
860 KB |
Output is correct |
7 |
Correct |
7 ms |
892 KB |
Output is correct |
8 |
Correct |
7 ms |
860 KB |
Output is correct |
9 |
Correct |
7 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
681 ms |
7844 KB |
Output is correct |
2 |
Correct |
756 ms |
8016 KB |
Output is correct |
3 |
Correct |
749 ms |
3372 KB |
Output is correct |
4 |
Correct |
23 ms |
860 KB |
Output is correct |
5 |
Correct |
7 ms |
860 KB |
Output is correct |
6 |
Correct |
7 ms |
888 KB |
Output is correct |
7 |
Correct |
7 ms |
860 KB |
Output is correct |
8 |
Correct |
2463 ms |
7076 KB |
Output is correct |
9 |
Correct |
2461 ms |
7108 KB |
Output is correct |