Submission #1025988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025988		socpite	Holiday (IOI14_holiday)	C++17	100 / 100	314 ms	16188 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;

const int maxn = 3e5+5;
const long long INF = 1e18;

long long A[maxn];
long long dpfx[maxn], dsfx[maxn];
int s, N, D;
int pos[maxn];

long long FW[2][maxn];

void add(int idx, long long val){
    for(idx; idx <= N; idx += idx&(-idx)){
        FW[0][idx] += val;
        FW[1][idx]++;
    }
}

long long gt(int k){
    if(k < 0)return -INF;
    int pos = 0;
    long long sum = 0;
    for(int i = 17; i >= 0; i--){
        if(pos + (1<<i) > N)continue;
        if(k - FW[1][pos^(1<<i)] >= 0){
            pos^=(1<<i);
            k -= FW[1][pos];
            sum += FW[0][pos];
        }
    }
    return sum;
}

void solve_pfx(){
    queue<pair<pair<int, int>, pair<int, int>>> q;
    int prv = 0, ptr = 0;
    q.push({{0, D}, {s, 1}});
    while(!q.empty()){
        auto ele = q.front();
        q.pop();
        int l = ele.first.first, r = ele.first.second;
        if(l > r)continue;
        if(ele.second.second != prv){
            prv = ele.second.second;
            memset(FW, 0, sizeof(FW));
            ptr = 0;
            add(pos[s], A[s]);
        }
        int qr = ele.second.first;
        int mid = (l+r)>>1, best = ptr;
        dpfx[mid] = gt(mid - 2*ptr);
        while(ptr < qr){
            ptr++;
            add(pos[s - ptr], A[s - ptr]);
            long long tmp = gt(mid - 2*ptr);
            if(tmp > dpfx[mid]){
                dpfx[mid] = tmp;
                best = ptr;
            }
        }
        q.push({{l, mid-1}, {best, prv + 1}});
        q.push({{mid+1, r}, {qr, prv + 1}});
    }
}

void solve_sfx(){
    queue<pair<pair<int, int>, pair<int, int>>> q;
    int prv = 0, ptr = 0;
    q.push({{0, D}, {N - s - 1, 1}});
    while(!q.empty()){
        auto ele = q.front();
        q.pop();
        int l = ele.first.first, r = ele.first.second;
        if(l > r)continue;
        if(ele.second.second != prv){
            prv = ele.second.second;
            memset(FW, 0, sizeof(FW));
            ptr = 0;
        }
        int qr = ele.second.first;
        int mid = (l+r)>>1, best = ptr;
        dsfx[mid] = gt(mid - ptr);
        while(ptr < qr){
            ptr++;
            add(pos[s + ptr], A[s + ptr]);
            long long tmp = gt(mid - ptr);
            if(tmp > dsfx[mid]){
                dsfx[mid] = tmp;
                best = ptr;
            }
        }
        q.push({{l, mid-1}, {best, prv + 1}});
        q.push({{mid+1, r}, {qr, prv + 1}});
    }
}

long long solve(){
    solve_pfx();
    solve_sfx();
    long long ans = -INF;
    for(int i = 0; i <= D; i++){
        ans = max(ans, dpfx[i] + dsfx[D - i]);
    }
    return ans;
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    s = start;
    N = n;
    D = d;
    vector<pair<int, int>> vec;
    for(int i = 0; i < n; i++){
        A[i] = attraction[i];
        vec.push_back({A[i], i});
    }
    sort(vec.rbegin(), vec.rend());
    for(int i = 0; i < n; i++)pos[vec[i].second] = i+1;

    long long ans = solve();

    reverse(pos, pos + n);
    reverse(A, A+n);
    s = n - s - 1;
    ans = max(ans, solve());

    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'void add(int, long long int)':
holiday.cpp:16:9: warning: statement has no effect [-Wunused-value]
   16 |     for(idx; idx <= N; idx += idx&(-idx)){
      |         ^~~

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