Submission #249517

#	Time	Username	Problem	Language	Result	Execution time	Memory
249517		Mercenary	Holiday (IOI14_holiday)	C++14	100 / 100	1488 ms	7548 KiB

holiday

#include "holiday.h"
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int n , a[maxn];

ll s[maxn * 4];
int cnt[maxn * 4];
ll res = 0;
int order[maxn] , d , id[maxn];
int st = 0;

void flip(int x , int l , int r , int pos){
    if(l == r){
//        cout << pos << " " << a[id[l]] << endl;
        if(cnt[x] == 0)cnt[x] = 1 , s[x] = a[order[l]];
        else cnt[x] = 0 , s[x] = 0;
        return;
    }
    int mid = l + r >> 1;
    if(pos <= mid)flip(x * 2 , l , mid , pos);
    else flip(x * 2 + 1 , mid + 1 , r , pos);
    s[x] = s[x * 2] + s[x * 2 + 1];
    cnt[x] = cnt[x * 2] + cnt[x * 2 + 1];
}
ll get(int x , int l , int r , int k){
    if(cnt[x] <= k)return s[x];
    if(l == r || k <= 0)return 0;
    ll sum = 0;
    int mid = l + r >> 1;
    sum += get(x * 2 + 1 , mid + 1 , r , min(k , cnt[x * 2 + 1]));
    k -= min(k , cnt[x * 2 + 1]);
    sum += get(x * 2 , l , mid , k);
    return sum;
}
void flip(int pos){flip(1,1,n,pos);}
ll get(int k){return get(1,1,n,k);};

int L = 1 , R = 0;
void correct(int l , int r){
    while(L < l)flip(id[L++]);
    while(L > l)flip(id[--L]);
    while(R < r)flip(id[++R]);
    while(R > r)flip(id[R--]);
}

void solve(int l , int r , int optl , int optr){
    if(l > r)return;
    int mid = l + r >> 1;
    pair<ll,int> best = mp(-1,-1);
    for(int i = optl ; i <= mid && i <= optr ; ++i){
        correct(i , mid);
        best = max(best , mp(get(d - (mid - i) - (mid - st)) , i));
//        cout << i << " " << mid << " " << cnt[1] << " " << d - (mid - i) - (mid - st) << " " << get(d - (mid - i) - (mid - st)) << endl;
    }
    res = max(res,best.first);
    solve(l , mid - 1 , optl , best.second);
    solve(mid + 1 , r , best.second,optr);
}

void Try(){
    L = 1 , R = 0;
    memset(cnt,0,sizeof cnt);
    memset(s,0,sizeof s);
    iota(order + 1 , order + n + 1 ,1);
    sort(order + 1 , order + n + 1 ,[&](const int x , const int y){return a[x] < a[y];});
//    for(int i = 1 ; i <= n ; ++i)cout << order[i] << " ";cout << endl;
    for(int i = 1 ; i <= n ; ++i)id[order[i]] = i;
    solve(st , n , 1 , n);
}

ll findMaxAttraction(int _n, int start, int _d, int attraction[]) {
    n = _n;
    st = start + 1;d = _d;
    for(int i = 1 ; i <= n ; ++i)a[i] = attraction[i - 1];
    Try();
    for(int i = 1 ; i <= n ; ++i)a[i] = attraction[n - i];
    st = n - start;
    Try();
    return res;
}

//static int N, start, D, A[100005];
//
//int main() {
//    scanf("%d%d%d", &N, &start, &D);
//    for ( int i = 0; i < N; i++ ) scanf("%d", &A[i]);
//    printf("%lld\n", findMaxAttraction(N, start, D, A));
//}

Compilation message (stderr)

holiday.cpp: In function 'void flip(int, int, int, int)':
holiday.cpp:23:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
holiday.cpp: In function 'll get(int, int, int, int)':
holiday.cpp:33:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
holiday.cpp: In function 'void solve(int, int, int, int)':
holiday.cpp:52:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53