Submission #572081

#	Time	Username	Problem	Language	Result	Execution time	Memory
572081		Lobo	Holiday (IOI14_holiday)	C++17	100 / 100	464 ms	8728 KiB

holiday

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

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 1e5+10;

int n, S, D, mxv, dp[maxn], a[maxn], trq[4*maxn], trs[4*maxn], ccval[4*maxn];

void att(int no, int l, int r, int pos, int val) {
    if(l > pos || r < pos) return;
    if(l == r) {
        trq[no]+= val;
        trs[no]+= val*ccval[l];
        return;
    }
    int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
    att(f1,l,mid,pos,val);
    att(f2,mid+1,r,pos,val);
    trq[no] = trq[f1]+trq[f2];
    trs[no] = trs[f1]+trs[f2];
}

int find(int no, int l, int r, int val) {
    if(l == r) {
        return ccval[l]*val;
    }
    int f1 = 2*no;
    int f2 = 2*no+1;
    int mid = (l+r)/2;

    //tenta ir para esquerda e pegar a direita
    if(val-trq[f2] > 0) return trs[f2] + find(f1,l,mid,val-trq[f2]);
    else return find(f2,mid+1,r,val);
}

int L,R;
void sol(int l, int r, int opl, int opr) {
    if(l > r) return;
    int i = (l+r)/2;
    //coloca o L no mid e o R no opl-1
    while(L < i) {
        att(1,1,mxv,a[L],-1);
        L++;
    }
    while(L > i) {
        L--;
        att(1,1,mxv,a[L],+1);
    }
    while(R > opl) {
        att(1,1,mxv,a[R],-1);
        R--;
    }
    while(R < opl) {
        R++;
        att(1,1,mxv,a[R],+1);
    }

    int opi = -1;
    for(int j = opl; j <= opr; j++) {
        if(j != opl) {
            R++;
            att(1,1,mxv,a[R],+1);
        }
        int q = max(D-S+2*i-j,D-2*j+S+i);
        q = min(q,j-i+1);
        int val = find(1,1,mxv,q);
        if(val > dp[i]) {
            dp[i] = val;
            opi = j;
        }
    }
    sol(l,i-1,opl,opi);
    sol(i+1,r,opi,opr);
}

int findMaxAttraction(int32_t N, int32_t start, int32_t d, int32_t attraction[]) {
    n = N;
    D = d;
    S = start;
    vector<int> cc;
    for(int i = 0; i < n; i++) {
        a[i] = attraction[i];
        cc.pb(a[i]);
    }
    sort(all(cc));
    cc.erase(unique(all(cc)),cc.end());
    mxv = cc.size();
    for(int i = 0; i < n; i++) {
        dp[i] = -inf;
        int aux = a[i];
        a[i] = upper_bound(all(cc),a[i]) - cc.begin();
        ccval[a[i]] = aux;
    }

    L = S;
    R = S-1;
    sol(0,S,S,n-1);

    int ans = 0;
    for(int i = 0; i < n; i++) {
        ans = max(ans,dp[i]);
    }

    return ans;
}

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