Submission #825068

#	Time	Username	Problem	Language	Result	Execution time	Memory
825068		Wael	Holiday (IOI14_holiday)	C++14	100 / 100	2416 ms	22768 KiB

holiday

#include<bits/stdc++.h>
#include "holiday.h"
//#include "grader.cpp"
using namespace std;
#define F first
#define S second
typedef long long ll;
int const M = 1e5 + 10 , N = 30e5 + 10;
int s[M] , cnt[N] , Left[N] , Right[N] , cur = 1 , L , R , k , Index;
ll Size = (1 << 30) , ans , sum[N] , dp[M];
 
void Add(ll i , ll node = 1 , ll lx = 1 , ll rx = Size) { 
    if(i == 0) return;
    if(lx == rx) {
        sum[node] += lx;
        ++cnt[node];
        return;
    } 
    int mid = (lx + rx) / 2;
    if(i <= mid) {
        if(Left[node] == 0) Left[node] = ++cur;
        Add(i , Left[node] , lx , mid);
    } else {
        if(Right[node] == 0) Right[node] = ++cur;
        Add(i , Right[node] , mid + 1 , rx);
    }
    sum[node] = sum[Left[node]] + sum[Right[node]];
    cnt[node] = cnt[Left[node]] + cnt[Right[node]];
}
 
void Remove(ll i , ll node = 1 , ll lx = 1 , ll rx = Size) {
    if(i == 0) return;
    if(lx == rx) {
        sum[node] -= lx;
        --cnt[node];
        return;
    } 
    ll mid = (lx + rx) / 2;
    if(i <= mid) {
        if(Left[node] == 0) Left[node] = ++cur;
        Remove(i , Left[node] , lx , mid);
    } else {
        if(Right[node] == 0) Right[node] = ++cur;
        Remove(i , Right[node] , mid + 1 , rx);
    }
    sum[node] = sum[Left[node]] + sum[Right[node]];
    cnt[node] = cnt[Left[node]] + cnt[Right[node]];
}
 
ll Get(ll need , ll node = 1 , ll lx = 1 , ll rx = Size) { //cout << need << " " << lx << endl;
    if(node == 0) return 0;
    if(need <= 0) return 0;
    if(lx == rx) return min(need , (ll)cnt[node]) * lx;
    ll mid = (lx + rx) / 2;
    if(cnt[Right[node]] >= need) {
        //cout << lx << " " << rx << " " << cnt[Right[node]] << endl;
        return Get(need , Right[node] , mid + 1 , rx);
    }
    else {
        need -= cnt[Right[node]];
        return sum[Right[node]] + Get(need , Left[node] , lx , mid);
    }
}
 
void Move(int l , int r) {
    if(l > r) swap(l , r);
 
    while(L < l) {
        Remove(s[L]);
        ++L;
    }
 
    while(L > l) {
        --L;
        Add(s[L]);
    }
 
    while(R < r) {
        ++R;
        Add(s[R]);
    }
 
    while(R > r) {
        Remove(s[R]);
        --R;
    }
}
 
void Divide(int l , int r , int i , int j) { 
    //cout << "in = " <<  l << " " << r << " " << i << " " << j << endl;
    if(i > j) return;
    int mid = (i + j) / 2;
 
    ll mx = 0 , Optimal = mid;
    for(int I = l ; I <= r ; ++I) {
        Move(mid , I);
        //cout << sum[1] << endl;
        int d = k;
        d -= abs(mid - Index);
        d -= abs(mid - I);
        //cout << "d = " << d << endl;
        ll res = Get(d);
        if(res > mx) {
            mx = res;
            dp[mid] = res;
            Optimal = I;
        }
    }
 
    ans = max ( ans , mx );
 
    //cout << "mid = " << mid << " " << dp[mid] << endl;
    Divide(l , Optimal , i , mid - 1);
    Divide(Optimal , r , mid + 1 , j);
}
 
long long int findMaxAttraction(int n, int start, int D , int attraction[]) {
    ++start;
    k = D; Index = start;
    for(int i = 1 ; i <= n ; ++i) s[i] = attraction[i - 1];
 
    int d = D;
    for(int i = start ; i <= n ; ++i) {
        Add(s[i]);
        ans = max(ans , Get(d));
        --d;
    }
    for(int i = start ; i <= n ; ++i) Remove(s[i]);
 
    d = D;
    for(int i = start ; i >= 1 ; --i) {
        Add(s[i]);
        ans = max(ans , Get(d));
        --d;
    }
    for(int i = 1 ; i <= start ; ++i) Remove(s[i]);
 
    if(start > 1 && start < n) Divide(1 , start - 1 , start + 1 , n);
    if(start > 1 && start < n) Divide(start + 1 , n , 1 , start - 1 );
 
    return ans;
}

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