| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 421083 |
2021-06-08T17:24:37 Z |
xt0r3 |
Holiday (IOI14_holiday) |
C++14 |
|
675 ms |
12392 KB |
#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
constexpr int N = 1 << 18;
long long t[N], dp[N];
bool bent[N];
int cut[N], n, d, cl, cr, id[N];
bool volt[N];
vector<long long> v;
struct FenwickTree{
int sz;//ez 2-hatvany
vector<long long> t;
FenwickTree(){}
FenwickTree(int _sz): sz(_sz){
t.assign(sz + 1, 0);//1-tol sz-ig
}
void add(int pos, long long val){
for(int i = pos; i <= sz; i += i & -i) t[i] += val;
}
long long get(int pos){
long long ret = 0;
for(int i = pos; i > 0; i -= i & -i) ret += t[i];
return ret;
}
int src(int l, int r, long long sum){
if(l == r) return l;
int m = (l + r) / 2;
if(t[m] >= sum){//nagy
return src(l, m, sum);
}
else{
return src(m + 1, r, sum - t[m]);
}
}
int src(long long sum){
return src(1, sz, sum);
}
};
FenwickTree cnt, sum;
int index(long long x){
return v.end() - lower_bound(v.begin(), v.end(), x);//1-tol indexelt a fenwick
}
long long val(int pos){
if(pos > v.size()) return 0;
return v[v.size() - pos];//pos az epp a v.end-tol visszafele van
}
void left(){
cnt.add(id[cl], -1);
sum.add(id[cl], -val(id[cl]));
cl++;
}
void right(){
cnt.add(id[cr], 1);
sum.add(id[cr], val(id[cr]));
cr++;
}
long long solve(int _N, int start, int D, int attraction[]) {
n = _N; d = D;
cnt = FenwickTree(N);
sum = FenwickTree(N);
//coordinate compression
v.resize(n);
for(int i = 0; i < n; i++) v[i] = attraction[i];
sort(v.begin(), v.end());
v.resize((int)(unique(v.begin(), v.end()) - v.begin()));
//cuts of endpoints
cut[start] = 1; //start 0-tol indexelve epp a start - 1 nalunk [start + 1, n] dp[i]: elmegyek a startbol i-be, aztan vissza cut[i]-ig
cut[n + 1] = n + 1;
volt[start] = volt[n + 1] = 1;
for(int i = 1; i <= n; i++){
id[i] = index(attraction[i - 1]);//id-k precompja
}
deque<pair<int, int> > uj = {{start, n + 1}}, regi;
while(!uj.empty()){
regi = uj;
uj.clear();
cl = 1;
cr = 1;
cnt = FenwickTree(N);
sum = FenwickTree(N);
while(!regi.empty()){//aktualis indexet megcsinaljuk
int l = regi.front().first, r = regi.front().second;
regi.pop_front();
int m = (l + r) / 2;
//cout << m << ' ' << l << ' ' << r << ' ' << cut[l] << ' ' << cut[r] << endl;
//system("PAUSE");
while(cr <= m){//beletesszuk
right();
}
//cout << "ITT" << endl;
while(cl < min(start + 1, cut[l])){//kivesszuk start ->
left();
}
//cout << "ITT" << endl;
for(int i = cut[l]; i <= min(m, cut[r]); i++){
long long rem = d - (2 * m - start - 1 - i);//ennyi marad a lepeseken tul - a start 0tol van indexelve
if(rem >= 0){
long long hol = cnt.src(rem);
long long levon = max(0ll, cnt.get(hol) - rem);//ennyiszer szerepel pluszban a faban egy ertek
long long most = sum.get(hol) - levon * val(hol);
if(dp[m] <= most){
dp[m] = most;
cut[m] = i;
}
}
if(i < min({start + 1, m, cut[r]})) left();//cut[r]-bol nem kell kilepni
}
if(cut[m] == 0) cut[m] = m;
//cout << m << ' ' << cut[m] << endl;
int nw = (l + m) / 2;
if(!volt[nw]){
volt[nw] = 1;
uj.push_back(make_pair(l, m));
}
nw = (m + r) / 2;
if(!volt[nw]){
volt[nw] = 1;
uj.push_back(make_pair(m, r));
}
}
}
return *max_element(dp, dp + n + 1);
}
long long findMaxAttraction(int _N, int start, int D, int attraction[]) {
long long ans1 = solve(_N, start, D, attraction);
reverse(attraction, attraction + _N);
start = _N - start - 1;
fill(volt, volt + _N, 0);
fill(cut, cut + _N, 0);
fill(dp, dp + _N, 0);
long long ans2 = solve(_N, start, D, attraction);
return max(ans1, ans2);
}
Compilation message
holiday.cpp: In function 'long long int val(int)':
holiday.cpp:55:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | if(pos > v.size()) return 0;
| ~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
6888 KB |
Output is correct |
| 2 |
Correct |
9 ms |
6884 KB |
Output is correct |
| 3 |
Correct |
10 ms |
6860 KB |
Output is correct |
| 4 |
Correct |
8 ms |
6828 KB |
Output is correct |
| 5 |
Correct |
9 ms |
6860 KB |
Output is correct |
| 6 |
Incorrect |
10 ms |
6860 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
265 ms |
11616 KB |
Output is correct |
| 2 |
Correct |
263 ms |
11880 KB |
Output is correct |
| 3 |
Correct |
254 ms |
11604 KB |
Output is correct |
| 4 |
Correct |
254 ms |
11604 KB |
Output is correct |
| 5 |
Correct |
231 ms |
11548 KB |
Output is correct |
| 6 |
Correct |
77 ms |
9704 KB |
Output is correct |
| 7 |
Correct |
141 ms |
10380 KB |
Output is correct |
| 8 |
Correct |
166 ms |
10732 KB |
Output is correct |
| 9 |
Correct |
58 ms |
9424 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
9020 KB |
Output is correct |
| 2 |
Correct |
19 ms |
9040 KB |
Output is correct |
| 3 |
Correct |
19 ms |
9024 KB |
Output is correct |
| 4 |
Correct |
28 ms |
9028 KB |
Output is correct |
| 5 |
Correct |
26 ms |
9024 KB |
Output is correct |
| 6 |
Correct |
17 ms |
8968 KB |
Output is correct |
| 7 |
Correct |
18 ms |
8952 KB |
Output is correct |
| 8 |
Correct |
18 ms |
8896 KB |
Output is correct |
| 9 |
Correct |
17 ms |
8860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
289 ms |
12084 KB |
Output is correct |
| 2 |
Correct |
197 ms |
12060 KB |
Output is correct |
| 3 |
Correct |
226 ms |
10504 KB |
Output is correct |
| 4 |
Correct |
26 ms |
9024 KB |
Output is correct |
| 5 |
Correct |
17 ms |
8896 KB |
Output is correct |
| 6 |
Correct |
18 ms |
8960 KB |
Output is correct |
| 7 |
Correct |
19 ms |
8968 KB |
Output is correct |
| 8 |
Correct |
675 ms |
12392 KB |
Output is correct |
| 9 |
Correct |
657 ms |
12312 KB |
Output is correct |
