| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 288588 |
2020-09-01T16:27:31 Z |
egekabas |
Holiday (IOI14_holiday) |
C++14 |
|
1795 ms |
20704 KB |
//#include "grader.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
struct tree{
vector<ll> seg;
void init(ll n){
seg.clear();
seg.resize(4*n+9);
}
void upd(ll v, ll tl, ll tr, ll idx, ll val){
if(tl == idx && tr == idx){
seg[v] += val;
return;
}
if(idx <= (tl+tr)/2)
upd(2*v, tl, (tl+tr)/2, idx, val);
else
upd(2*v+1, (tl+tr)/2+1, tr, idx, val);
seg[v] = seg[2*v]+seg[2*v+1];
}
pll get(ll v, ll tl, ll tr, ll val){
if(tl == tr)
return {tl, max(0LL, seg[v]-val)};
if(seg[2*v+1] >= val)
return get(2*v+1, (tl+tr)/2+1, tr, val);
else
return get(2*v, tl, (tl+tr)/2, val-seg[2*v+1]);
}
};
struct bit{
ll n;
vector<ll> bit;
void init(ll sz){
bit.clear();
bit.resize(sz+1);
n = sz;
}
void upd(ll idx, ll val){
for(++idx; idx > 0; idx -= idx&(-idx))
bit[idx] += val;
}
ll get(ll idx){
ll ret = 0;
for(++idx; idx <= n; idx += idx&(-idx))
ret += bit[idx];
return ret;
}
};
vector<ll> mpp;
struct data{
tree tr;
bit bi;
ll n;
void init(ll N){
n = N;
tr.init(n);
bi.init(n);
}
void add(ll x){
tr.upd(1, 0, n-1, x, 1);
bi.upd(x, mpp[x]);
}
void erase(ll x){
tr.upd(1, 0, n-1, x, -1);
bi.upd(x, -mpp[x]);
}
ll get(ll cnt){
if(cnt <= 0) return cnt;
pii pi = tr.get(1, 0, n-1, cnt);
return bi.get(pi.ff)-pi.ss*mpp[pi.ff];
}
};
ll N, D;
vector<ll> v1, v2, v3, v4;
vector<ll> go1, come1, go2, come2;
data dt;
void opt(ll l, ll r, ll vl, ll vr, vector<ll> &v, data &dt, vector<ll> &ret, ll comeback){
if(v.empty()){
for(ll i = l; i <= r; ++i)
ret[i] = 0;
return;
}
if(l > r)
return;
ll m = (l+r)/2;
pii maxi = {-1e9, -1e9};
for(ll i = vl; i <= vr; ++i){
dt.add(v[i]);
if(comeback)
maxi = max(maxi, {dt.get(m-2*i), i});
else
maxi = max(maxi, {dt.get(m-i), i});
}
ll vm = maxi.ss;
ret[m] = maxi.ff;
for(ll i = vr; i >= vm; --i)
dt.erase(v[i]);
opt(m+1, r, vm, vr, v, dt, ret, comeback);
for(ll i = vm-1; i >= vl; --i)
dt.erase(v[i]);
opt(l, m-1, vl, vm, v, dt, ret, comeback);
}
ll getval(vector<ll> v, ll lim){
data dt;
dt.init(mpp.size());
ll ans = 0;
for(int i = 0; i < v.size(); ++i){
dt.add(v[i]);
ans = max(ans, dt.get(lim-i));
}
return ans;
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
N = n;
D = d;
for(ll i = 0; i < n; ++i)
mpp.pb(attraction[i]);
sort(all(mpp));
mpp.resize(unique(all(mpp))-mpp.begin());
for(ll i = 0; i < n; ++i)
attraction[i] = lower_bound(all(mpp), attraction[i])-mpp.begin();
for(ll i = start+1; i < n; ++i)
v1.pb(attraction[i]);
for(ll i = start; i < n; ++i)
v2.pb(attraction[i]);
for(ll i = start-1; i >= 0; --i)
v3.pb(attraction[i]);
for(ll i = start; i >= 0; --i)
v4.pb(attraction[i]);
dt.init(mpp.size());
go1.resize(d);
opt(0, d-1, 0, v1.size()-1, v1, dt, go1, 0);
dt.init(mpp.size());
come1.resize(d);
opt(0, d-1, 0, v2.size()-1, v2, dt, come1, 1);
dt.init(mpp.size());
go2.resize(d);
opt(0, d-1, 0, v3.size()-1, v3, dt, go2, 0);
dt.init(mpp.size());
come2.resize(d);
opt(0, d-1, 0, v4.size()-1, v4, dt, come2, 1);
for(ll i = 1; i < d; ++i){
go1[i] = max(go1[i], go1[i-1]);
come1[i] = max(come1[i], come1[i-1]);
go2[i] = max(go2[i], go2[i-1]);
come2[i] = max(come2[i], come2[i-1]);
}
ll ans = 0;
for(ll i = 0; i < d; ++i){
ans = max(ans, come1[i]+go2[d-i-1]);
ans = max(ans, come2[i]+go1[d-i-1]);
//cout << i << ' ' << come2[i] << ' ' << d-i-1 << ' ' << go1[d-i-1] << '\n';
}
ans = max(ans, getval(v2, d));
ans = max(ans, getval(v4, d));
return ans;
}
Compilation message
holiday.cpp: In function 'll getval(std::vector<long long int>, ll)':
holiday.cpp:121:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(int i = 0; i < v.size(); ++i){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
380 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
512 KB |
Output is correct |
| 7 |
Correct |
0 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
10464 KB |
Output is correct |
| 2 |
Correct |
86 ms |
10464 KB |
Output is correct |
| 3 |
Correct |
103 ms |
10464 KB |
Output is correct |
| 4 |
Correct |
96 ms |
10476 KB |
Output is correct |
| 5 |
Correct |
515 ms |
8040 KB |
Output is correct |
| 6 |
Correct |
208 ms |
7284 KB |
Output is correct |
| 7 |
Correct |
293 ms |
5232 KB |
Output is correct |
| 8 |
Correct |
343 ms |
5488 KB |
Output is correct |
| 9 |
Correct |
199 ms |
8820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
1016 KB |
Output is correct |
| 2 |
Correct |
3 ms |
768 KB |
Output is correct |
| 3 |
Correct |
27 ms |
896 KB |
Output is correct |
| 4 |
Correct |
27 ms |
760 KB |
Output is correct |
| 5 |
Correct |
24 ms |
768 KB |
Output is correct |
| 6 |
Correct |
7 ms |
512 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
6 ms |
384 KB |
Output is correct |
| 9 |
Correct |
4 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
12640 KB |
Output is correct |
| 2 |
Correct |
1645 ms |
20704 KB |
Output is correct |
| 3 |
Correct |
586 ms |
6288 KB |
Output is correct |
| 4 |
Correct |
21 ms |
640 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
6 ms |
512 KB |
Output is correct |
| 7 |
Correct |
4 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1795 ms |
13212 KB |
Output is correct |
| 9 |
Correct |
1770 ms |
12952 KB |
Output is correct |
