oj.uz

Submission #393803

# Submission time Handle Problem Language Result Execution time Memory
393803 2021-04-24T14:21:19 Z Vladth11 Holiday (IOI14_holiday) C++14
100 / 100
 1920 ms 28884 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 15988 KB Output is correct
2 Correct 15 ms 15948 KB Output is correct
3 Correct 15 ms 15980 KB Output is correct
4 Correct 15 ms 15996 KB Output is correct
5 Correct 15 ms 15948 KB Output is correct
6 Correct 14 ms 15984 KB Output is correct
7 Correct 15 ms 15976 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1436 ms 28184 KB Output is correct
2 Correct 1857 ms 28152 KB Output is correct
3 Correct 1920 ms 28100 KB Output is correct
4 Correct 1410 ms 28088 KB Output is correct
5 Correct 1122 ms 26392 KB Output is correct
6 Correct 382 ms 21356 KB Output is correct
7 Correct 583 ms 22028 KB Output is correct
8 Correct 693 ms 22908 KB Output is correct
9 Correct 322 ms 21648 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 16300 KB Output is correct
2 Correct 36 ms 16332 KB Output is correct
3 Correct 36 ms 16324 KB Output is correct
4 Correct 34 ms 16204 KB Output is correct
5 Correct 33 ms 16260 KB Output is correct
6 Correct 20 ms 16088 KB Output is correct
7 Correct 19 ms 16076 KB Output is correct
8 Correct 22 ms 16076 KB Output is correct
9 Correct 19 ms 16084 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1474 ms 28884 KB Output is correct
2 Correct 1509 ms 28876 KB Output is correct
3 Correct 418 ms 20220 KB Output is correct
4 Correct 32 ms 16252 KB Output is correct
5 Correct 19 ms 16092 KB Output is correct
6 Correct 20 ms 16052 KB Output is correct
7 Correct 19 ms 16076 KB Output is correct
8 Correct 1283 ms 26668 KB Output is correct
9 Correct 1254 ms 26648 KB Output is correct