Submission #756673

#	Time	Username	Problem	Language	Result	Execution time	Memory
756673		ByeWorld	Holiday (IOI14_holiday)	C++14	100 / 100	2645 ms	36760 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int MAXN = 1e5+10;
const int INF = 1e9;
typedef pair<ll,ll> pii;

int val[MAXN];
struct node {
    int l, r, mid; ll sum, cnt; 
    node *le, *ri;
    void bd(int l2, int r2){
        l = l2; r = r2; mid = (l+r)/2;
        sum = 0; cnt = 0;
        if(l==r) return;
        le = new node(); le->bd(l, mid);
        ri = new node(); ri->bd(mid+1, r);
    }
    ll que(int w){
        if(w<=0) return 0;
        if(cnt <= w) return sum;
        if(l == r) return 1ll*val[l]*w;
        if(ri->cnt >= w) return ri->que(w);
        return le->que(w - ri->cnt) + ri->que(ri->cnt);
    }
    pii upd(int x, int p){
        if(r<x || x<l) return {sum, cnt};
        if(l==r && l==x){
            sum += 1ll*val[x]*p; cnt += p;
            return {sum, cnt};
        }
        pii lupd = le->upd(x, p); pii rupd = ri->upd(x, p);
        sum = lupd.fi + rupd.fi; cnt = lupd.se + rupd.se;
        return {sum, cnt}; 
    }
} A;

int n, sta, d;
int a[MAXN];
map<int,int> idx;
ll ret = 0;
int le = 1, ri = 0;

void setlr(int l,int r){
    while(le < l){
        A.upd(idx[a[le++]], -1);
    } //mid-1, out
    while(le > l){
        A.upd(idx[a[--le]], 1);
    } //mid, in
    while(ri < r){
        A.upd(idx[a[++ri]], 1);
    } //optl, in
    while(ri > r){
        A.upd(idx[a[ri--]], -1);
    } //optr+1, out
}

void solve(int l, int r, int optl, int optr){
    if(l > r) return;
    int mid = (l+r)/2, opt;
    ll dp = -INF; //cari value mid
    // mid - le udh ke build
    if(ri-optl <= optr-ri){
        for(int i=optl; i<=optr; i++){
            setlr(mid,i);
            // mid - i
            // d-(sta-mid)-(i-mid)
            ll can = A.que(d-sta + 2*mid - i);
            //cout << mid << ' ' << i << ' ' << can << "que\n";
            if(dp < can){
                dp = can;
                opt = i;
            }
        }
        solve(mid+1, r, opt, optr); solve(l, mid-1, optl, opt); 
    } else {
        for(int i=optr; i>=optl; i--){
            setlr(mid,i);
            ll can = A.que(d-sta + 2*mid - i);
            //cout << mid << ' ' << i << ' ' << can << "que\n";
            if(dp <= can){
                dp = can;
                opt = i;
            }
        }
        solve(l, mid-1, optl, opt); solve(mid+1, r, opt, optr); 
    }
    //cout << mid << ' '<< opt << ' ' << dp << "dp\n";
    ret = max(ret, dp);
}

long long int findMaxAttraction(int N, int start, int D, int X[]) {
	n = N; sta = start; d = D;
    sta++;
    set <int> s;
	for(int i=0; i<=n-1; i++){
        a[i+1] = X[i];
        s.insert(a[i+1]);
    }
    int index = 0;
    for(auto in : s){
        idx[in] = ++index;
        val[index] = in;
        //cout << in << ' ' << index << "ind\n";
    }
    
    //cout << "\nA\n";
    le = sta; ri = sta-1;
    A.bd(1, MAXN);
    solve(1, sta, sta, n);

	for(int i=1; i<n-i+1; i++) swap(a[i], a[n-i+1]);
	sta = n-sta+1;
    //cout << "\nB\n";
    le = sta; ri = sta-1;
	A.bd(1, MAXN);
    solve(1, sta, sta, n);

	return ret;
}

Compilation message (stderr)

holiday.cpp: In function 'void solve(int, int, int, int)':
holiday.cpp:90:42: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   90 |         solve(l, mid-1, optl, opt); solve(mid+1, r, opt, optr);
      |                                     ~~~~~^~~~~~~~~~~~~~~~~~~~~

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