| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 432672 |
2021-06-18T12:18:39 Z |
dreezy |
Holiday (IOI14_holiday) |
C++17 |
|
1664 ms |
38340 KB |
#include <bits/stdc++.h>
#include"holiday.h"
using namespace std;
#define ll long long
#define pill pair<int,ll>
#define pi pair<int,int>
#define f first
#define s second
#define mp make_pair
/***********************/
struct SegTree{
vector<pill> st;
vector<int> minmax;
int sz;
void init(int n, bool right){
sz = n;
st.assign(n*4, {0,0ll});
if(right)
minmax.assign(n*4, 0);
else
minmax.assign(n*4, 1e9);
}
void updactive(int n, int l, int r, int ind, int val){
if(l == r){
st[n].f = val;
return;
}
int mid = (l + r)/2;
if(mid >= ind)
updactive(2*n+1, l, mid, ind, val);
else
updactive(2*n + 2, mid + 1, r, ind, val);
st[n].f = st[2*n+1].f + st[2*n+2].f;
}
void updval(int n, int l, int r, int ind, int val){
if(l == r){
st[n].s = val;
return;
}
int mid = (l + r)/2;
if(mid >= ind)
updval(2*n+1, l, mid, ind, val);
else
updval(2*n + 2, mid + 1, r, ind, val);
st[n].s = st[2*n+1].s + st[2*n+2].s;
}
void updmin(int n, int l, int r, int ind, int val){
if(l == r){
minmax[n] = val;
return;
}
int mid = (l + r)/2;
if(mid >= ind)
updmin(2*n + 1, l, mid, ind , val);
else
updmin(2*n+2, mid + 1, r, ind , val);
minmax[n] = min(minmax[2* n +1], minmax[2*n + 2]);
}
void updmax(int n, int l, int r, int ind, int val){
if(l == r){
minmax[n] = val;
return;
}
int mid = (l + r)/2;
if(mid >= ind)
updmax(2*n + 1, l, mid, ind , val);
else
updmax(2*n+2, mid + 1, r, ind , val);
minmax[n] = max(minmax[2* n +1], minmax[2*n + 2]);
}
void activate(int ind,int city, int val, bool right){
updactive(0,0,sz, ind, 1);
updval(0,0,sz, ind, val);
if(right)
updmax(0,0,sz,ind,city);
else
updmin(0,0,sz,ind, city);
}
int getfirst(int n, int l, int r, int val){
if(l == r) return l;
int mid = (l + r)/2;
if(st[2*n+1].f >= val )
return getfirst(2*n+1, l, mid, val);
return getfirst(2*n+ 2, mid + 1, r, val - st[2*n+1].f);
}
int getfirst(int val){
int target = st[0].f - val +1;
if(target <=0)
return 0;
return getfirst(0, 0, sz, target);
}
ll qrysum(int n, int l, int r, int s, int e){
if(s<= l and e >= r) return st[n].s;
ll ans = 0;
int mid = (l + r)/2;
if( mid >= s)
ans += qrysum(2*n+1, l, mid, s, e);
if(mid < e)
ans+=qrysum(2*n+2, mid + 1, r, s,e);
return ans;
}
int getmin(int n, int l, int r, int s, int e){
if(s<= l and e >= r) return minmax[n];
int ans = 1e9;
int mid = (l + r)/2;
if( mid >= s)
ans = min(getmin(2*n+1, l, mid, s, e), ans);
if(mid < e)
ans = min(getmin(2*n+2, mid + 1, r, s,e), ans);
return ans;
}
int getmax(int n, int l, int r, int s, int e){
if(s<= l and e >= r) return minmax[n];
int ans = -1;
int mid = (l + r)/2;
if( mid >= s)
ans = max(getmax(2*n+1, l, mid, s, e), ans);
if(mid < e)
ans = max(getmax(2*n+2, mid + 1, r, s,e),ans);
return ans;
}
pair<ll, int> getlargest(int rng, bool right){
int lower = getfirst(rng);
//cout << lower<<endl;
ll res = qrysum(0, 0,sz, lower, sz );
if(right)
return {res, getmax(0, 0,sz, lower,sz)};
return {res, getmin(0, 0,sz, lower,sz)};
}
};
vector<int> inds;
int n;
int start;
vector<ll> dpright;
vector<int> minright;
vector<int> attraction;
SegTree stright;
vector<int> lvlactive;
int cnt = 0;
void dcright(int s_, int e_, int l_, int r_, int lvl_){
cnt = 0;
priority_queue<pair<pair<int,int>,tuple<int,int,int,int,int>>> pq;
pq.push({{-lvl_,cnt--},{s_, e_, l_, r_,lvl_} });
int curlevel = -1;
while(pq.size()){
int st, e, l, r, lvl;
tie(st, e,l,r,lvl) = pq.top().s;
pq.pop();
if(e < st || l > r) continue;
if(lvl > curlevel){
curlevel = lvl;
stright.init(n,true);
}
//cout <<lvl<<", "<<lvlactive[lvl]<< ": "<< st<<", "<<e<<": "<<l<<", "<<r<<endl;
for(int i = lvlactive[lvl]; i < l; i++)
stright.activate(inds[i],i, attraction[i], true);
lvlactive[lvl] = l -1;
int days = (st + e)/2;
for(int right = l; right <=r; right++){
stright.activate(inds[right],right, attraction[right], true);
int dist = right - start;
if(days - dist < 0){
break;
}
pair<ll, int> res = stright.getlargest(days - dist, true);
if(days - dist == 0) res.s = right;
//if(days == 2) cout << res.f<<", "<<res.s<<", "<<dist<<endl;
if(res.f > dpright[days]){
dpright[days] = res.f;
minright[days] = res.s;
}
else if(res.f == dpright[days]){
minright[days] = min(minright[days], res.s);
}
lvlactive[lvl] = right;
}
pq.push({{-(lvl +1), cnt--},{st, days -1, l, minright[days], lvl+1}});
pq.push({{-(lvl+1), cnt--}, {days+1, e, minright[days], r, lvl+1}});
}
//dcright(s, days -1, l, minright[days], lvl+1);
//dcright(days +1, e, minright[days], r,lvl+1);
}
vector<ll> dpleft;
vector<int> maxleft;
SegTree stleft;
void dcleft(int s_, int e_, int l_, int r_, int lvl_){
cnt = 0;
//cout << maxleft[days]<<", "<<dpleft[days]<<endl;
priority_queue<pair<pair<int,int>,tuple<int,int,int,int,int>>> pq;
pq.push({{-lvl_,cnt--},{s_, e_, l_, r_,lvl_} });
int curlevel = -1;
while(pq.size()){
int st, e, l, r, lvl;
tie(st, e,l,r,lvl) = pq.top().s;
pq.pop();
if(e < st || l > r) continue;
if(lvl > curlevel){
curlevel = lvl;
stleft.init(n,false);
}
//cout <<lvl<<", "<<lvlactive[lvl]<< ": "<< st<<", "<<e<<": "<<l<<", "<<r<<endl;
for(int i = lvlactive[lvl]; i > r; i--)
stleft.activate(inds[i],i, attraction[i], false);
int days = (st + e)/2;
for(int left = r; left >=l; left--){
stleft.activate(inds[left],left, attraction[left], false);
int dist = start - left;
if(days - dist < 0) break;
pair<ll, int> res = stleft.getlargest(days - dist,false);
if(days - dist == 0) res.s = left;
//if(days == 4) cout << dist<<"!"<<res.f<<endl;
//if(e == 1) cout << dist<<", "<<res<endl;
if(res.f > dpleft[days]){
dpleft[days] = res.f;
maxleft[days] = res.s;
}
else if(res.f == dpleft[days]){
maxleft[days] = max(maxleft[days], res.s);
}
lvlactive[lvl] = left;
}
pq.push({{-(lvl +1), cnt--},{st, days -1, maxleft[days],r, lvl+1}});
pq.push({{-(lvl+1), cnt--}, {days+1, e, l, maxleft[days], lvl+1}});
//dcleft(s, days -1, maxleft[days],r, lvl+1);
//dcleft(days +1, e,l, maxleft[days],lvl+1);
}
}
long long int findMaxAttraction(int n_, int start_, int d, int attractions[]) {
n = n_;
start = start_;
attraction.assign(n,0);
for(int i =0; i<n; i++) attraction[i] = attractions[i];
vector<pi> cities(n);
for(int i =0; i<n; i++){
cities[i] = {attraction[i], i};
}
sort(cities.begin(), cities.end());
inds.assign(n, 0);
for(int i= 0; i<n;i++)
inds[cities[i].s] = i;
dpright.assign(d+1, 0);
minright.assign(d + 1, 1e9);
lvlactive.assign(30,start);
dcright(1, d, start, n -1, 0);
dpleft.assign(d+1, 0);
maxleft.assign(d + 1, 0);
lvlactive.assign(30,start-1);
dcleft(1, d,0, start-1, 0);
ll ans = 0;
for(int daysright = 0; daysright <= d; daysright++){
int distright = daysright == 0 ? 0: minright[daysright] - start;
int daysleft = max(0,d - daysright - distright);
//cout<< daysleft<<", "<<daysright<<", "<<distright<<": "<<dpleft[daysleft]<<", "<<dpright[daysright]<<endl;
ans = max(ans,dpleft[daysleft] + dpright[daysright] );
}
//cout <<endl;
for(int daysleft = 0; daysleft <= d; daysleft++){
int distleft = daysleft == 0 ? 0: start - maxleft[daysleft] ;
int daysright = max(0,d - daysleft - distleft);
//cout<< daysleft<<", "<<daysright<<", "<<maxleft[daysleft]<<": "<<dpleft[daysleft]<<", "<<endl;
//cout << dpright.size()<<": "<<dpright[daysright]<<endl;
ans = max(ans,dpleft[daysleft] + dpright[daysright] );
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
588 KB |
Output is correct |
| 2 |
Correct |
1 ms |
588 KB |
Output is correct |
| 3 |
Correct |
1 ms |
624 KB |
Output is correct |
| 4 |
Correct |
1 ms |
588 KB |
Output is correct |
| 5 |
Correct |
1 ms |
588 KB |
Output is correct |
| 6 |
Correct |
1 ms |
588 KB |
Output is correct |
| 7 |
Correct |
1 ms |
588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1163 ms |
19928 KB |
Output is correct |
| 2 |
Correct |
765 ms |
19904 KB |
Output is correct |
| 3 |
Correct |
1086 ms |
19856 KB |
Output is correct |
| 4 |
Correct |
724 ms |
19824 KB |
Output is correct |
| 5 |
Correct |
1514 ms |
14800 KB |
Output is correct |
| 6 |
Correct |
523 ms |
9200 KB |
Output is correct |
| 7 |
Correct |
773 ms |
8508 KB |
Output is correct |
| 8 |
Correct |
903 ms |
9724 KB |
Output is correct |
| 9 |
Correct |
396 ms |
12652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
1716 KB |
Output is correct |
| 2 |
Correct |
31 ms |
1664 KB |
Output is correct |
| 3 |
Correct |
25 ms |
1696 KB |
Output is correct |
| 4 |
Correct |
25 ms |
1408 KB |
Output is correct |
| 5 |
Correct |
24 ms |
1288 KB |
Output is correct |
| 6 |
Correct |
7 ms |
844 KB |
Output is correct |
| 7 |
Correct |
5 ms |
844 KB |
Output is correct |
| 8 |
Correct |
5 ms |
844 KB |
Output is correct |
| 9 |
Correct |
5 ms |
892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1232 ms |
38340 KB |
Output is correct |
| 2 |
Correct |
1421 ms |
21164 KB |
Output is correct |
| 3 |
Correct |
276 ms |
9440 KB |
Output is correct |
| 4 |
Correct |
16 ms |
1276 KB |
Output is correct |
| 5 |
Correct |
5 ms |
844 KB |
Output is correct |
| 6 |
Correct |
6 ms |
844 KB |
Output is correct |
| 7 |
Correct |
6 ms |
844 KB |
Output is correct |
| 8 |
Correct |
1664 ms |
22548 KB |
Output is correct |
| 9 |
Correct |
1618 ms |
22676 KB |
Output is correct |
