Submission #393803

#	Time	Username	Problem	Language	Result	Execution time	Memory
393803		Vladth11	Holiday (IOI14_holiday)	C++14	100 / 100	1920 ms	28884 KiB

holiday

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "
#include"holiday.h"

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;

const ll NMAX = 1000001;
const ll INF = (1LL << 60);
const ll MOD = 666013;
const ll BLOCK = 225;
const ll base = 31;
const ll nr_of_bits = 21;

ll v[NMAX];
ll N;
ll c;
ll D;
ll fdr[NMAX];
ll fst[NMAX];
map <ll, ll> mp;
pii normalizare[NMAX];

class Fenwick{
    ll aib[NMAX];
public:
    void init(){
        for(int i = 0; i < NMAX; i++)
            aib[i] = 0;
    }
    void update(ll node, ll x){

        for(ll i = node; i <= N; i += i&(-i))
            aib[i] += x;
    }
    ll query(ll node){
        ll x = 0;
        for(ll i = node; i > 0; i -= i&(-i))
            x += aib[i];
        return x;
    }
    ll kth(ll node){
        ll idx = 0;
        for(ll i = nr_of_bits; i >= 0; i--){
            ll nxt = idx | (1 << i);
            if(nxt <= N && aib[nxt] <= node){
                idx = nxt;
                node -= aib[nxt];
            }
        }
        return idx;
    }
};

class Structura{
    Fenwick cnt, suma;
public:
    void init(){
        cnt.init();
        suma.init();
    }
     ll scor(ll p){
        ll poz = cnt.kth(p);
        return suma.query(poz);
     }
     void insert(pii x){
        ll poz = mp[x.second];
        cnt.update(poz, 1);
        suma.update(poz, x.first);
     }
     void erase(pii x){
        ll poz = mp[x.second];
        cnt.update(poz, -1);
        suma.update(poz, -x.first);
     }
     int size(){
        return suma.query(NMAX - 2);
     }
}ura;

void calcdr(ll st, ll dr, ll l, ll r){
    if(st > dr)
        return;
    ll target = (st + dr) / 2;
    ll pz = 0, maxim = 0;
    for(ll i = l; i <= r; i++){
        ura.insert({v[i], i});
        ll ramase = target - (i - c);
        ll scor = ura.scor(ramase);
        if(maxim < scor){
            maxim = scor;
            pz = i;
        }
    }
    fdr[target] = maxim;
    for(ll i = r; i >= pz; i--){
        ura.erase({v[i], i});
    }
    calcdr(target + 1, dr, pz, r);
    for(ll i = l; i < pz; i++){
        ura.erase({v[i], i});
    }
    calcdr(st, target - 1, l, pz);
}

void calcst(ll st, ll dr, ll l, ll r){
    if(st > dr){
        return;
    }
    ll target = (st + dr) / 2;
    ll pz = 0, maxim = 0;
    for(ll i = r; i >= l; i--){
        ura.insert({v[i], i});
        ll ramase = target - (c - 1 - i) * 2;
        ll scor = ura.scor(ramase);
        if(maxim <= scor){
            maxim = scor;
            pz = i;
        }
    }
    fst[target] = maxim;
    for(ll i = l; i <= pz; i++){
        ura.erase({v[i], i});
    }
    calcst(target + 1, dr, l, pz);
    for(ll i = pz + 1; i <= r; i++){
        ura.erase({v[i], i});
    }
    calcst(st, target - 1, pz, r);
}

ll solve(){
    ura.init();
  	if(c != 0)
    calcst(0, D, 0, c - 1);
  	ura.init();
    calcdr(0, D, c, N - 1);
    ll maxim = 0;
    for(ll i = 0; i <= D; i++){
        if(D - i - 2 >= 0){
        maxim = max(maxim, fdr[i] + fst[D - i - 2]);
        }
        maxim = max(maxim, fdr[i]);
    }
  	for(ll i = 0; i <= D; i++){
      fst[i] = fdr[i] = 0;
    }
    return maxim;
}

bool cmp(pii a, pii b){
    if(a.first != b.first){
        return a.first > b.first;
    }
    return a.second < b.second;
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    c = start;
    N = n;
    D = d;
    for(ll i = 0; i < n; i++){
        v[i] = attraction[i];
        normalizare[i + 1] = {v[i], i};
    }
    sort(normalizare + 1, normalizare + n + 1, cmp);
    for(ll i = 1; i <= n; i++){
        mp[normalizare[i].second] = i;
    }
    ll maxim = solve();
    //debug(ura.size());
    c = n - start - 1;
    reverse(attraction, attraction + n);
    for(ll i = 0; i < n; i++){
        v[i] = attraction[i];
        //debug(attraction[i]);
        normalizare[i + 1] = {v[i], i};
    }
    sort(normalizare + 1, normalizare + n + 1, cmp);
    for(ll i = 1; i <= n; i++){
        mp[normalizare[i].second] = i;
    }
    c = n - start - 1;
    maxim = max(maxim, solve());
    return maxim;
}

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