Submission #1053638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053638		phong	Holiday (IOI14_holiday)	C++17	100 / 100	260 ms	18984 KiB

holiday

#include <holiday.h>
#include<bits/stdc++.h>

#define ll long long
const int nmax = 1e5 + 5, N = 250005;
const ll oo = 1e18;
const int lg = 19, M = 2, mod = 1e6;
#define pii pair<ll, int>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
#define endl "\n"
#define task "code"
using namespace std;

int n, st, D;
pii a[nmax];
int rev[nmax];
int best[N][2];
ll dp[N][2];
pii tree[1 << 18];

void build(int id, int l, int r){
    tree[id].fi = 0;
    tree[id].se = 0;
    if(l != r){
        int mid = r + l >> 1;
        build(id << 1, l, mid);
        build(id << 1|  1, mid + 1, r);
    }
}

void update(int id, int l, int r, int u, int val){
    if(l > u || r < u) return;
    if(l == r){
        tree[id] = {val, 1};
        return;
    }
    int mid = r + l >> 1;
    update(id << 1, l, mid, u, val);
    update(id << 1 | 1, mid + 1, r, u, val);
    tree[id].fi = tree[id << 1].fi + tree[id << 1 | 1].fi;
    tree[id].se = tree[id << 1].se + tree[id << 1 | 1].se;

}
ll get(int id, int l, int r, int k){
    if(tree[id].se <= k) return tree[id].fi;
    int mid = r+ l >> 1;
    if(tree[id << 1 | 1].se >= k) return get(id << 1 | 1, mid + 1, r, k);
    return tree[id << 1 | 1].fi + get(id << 1, l ,mid, k - tree[id << 1 | 1].se);
}

struct node{
    int L, R, from, to;
};
vector<node> adj[21];

void Init(int ok){
    if(st > n) return;
    for(int i = 1; i <= n; ++i) rev[a[i].se] = i;
    for(int e = 1; e <= 20; ++e)adj[e].clear();
    adj[1].push_back({1, D, st, n});
    for(int e = 1; e <= 20; ++e){
        if(adj[e].empty()) continue;
        build(1, 1, n);
        int pos = st;
        for(auto [L, R, from, to] : adj[e]){

            int mid = R + L >> 1;
            auto &FF = best[mid][ok];
            FF = 1e9;
            ll &ma = dp[mid][ok];
            ma = -1;
            for(int i = from; i <= to; ++i){
                if(mid - (i - st) >= 0){
                    while(pos <= i){
                        int x = rev[pos];
                        update(1, 1, n, x, a[x].fi);
                        ++pos;
                    }
                    ll cur = get(1, 1, n, mid - (i - st));
                    if(ma < cur){
                        ma = cur;
                        FF = i;
                    }
                }
            }
            if(L < mid) adj[e + 1].push_back({L, mid - 1, from, FF});
            if(mid < R) adj[e + 1].push_back({mid + 1, R, FF, to});
        }
//        cout << endl;
    }
    for(int i = 1; i <= D; ++i) best[i][ok] -= st;
}
ll ans = 0;
int g[nmax];

void solve(){
    for(int i = 1; i <= n; ++i) a[i].fi = g[i], a[i].se = i;
    sort(a + 1,a + 1 + n,[](pii a, pii b){
         return a.fi < b.fi;
         });
    Init(0);
    st = n - (st - 1) + 1;
    for(int i = 1; i <= n; ++i) a[i].se = n - a[i].se + 1;
    Init(1);
    st = n - st + 1;
    ++st;
     for(int x = 0; x <= D; ++x){
        ll val = dp[x][0];
        int y = D - (best[x][0] * 2 + x - best[x][0]) - 1;
        if(y >= 0) val += dp[y][1];
        ans = max(ans, val);
        ans = max(ans, dp[x][0]);
        if(x - 1 >= 0) ans = max(ans, dp[x - 1][1]);
        if(x - 2 >= 0) ans = max(ans, dp[x - 2][1] + g[st]);
        //
        val = dp[x - 1][1];
        y = D - (best[x - 1][1] * 2 + x - 1 - best[x - 1][1] + 1) - 1;
        if(y >= 0) val += dp[y][0];
        ans = max(ans, val);
        val = dp[x - 2][1] + g[st];
        y = D - (best[x - 2][1] * 2 + x - 2 - best[x - 2][1] + 1) - 1;
        if(y >= 0) val += dp[y][0];
    }
}
ll findMaxAttraction(int Na, int start, int d, int attraction[]){
    n = Na, st = start, D = d;
    ++st;
    for(int i = 1; i <= n; ++i) g[i] = attraction[i- 1];
    solve();
    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'void build(int, int, int)':
holiday.cpp:27:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |         int mid = r + l >> 1;
      |                   ~~^~~
holiday.cpp: In function 'void update(int, int, int, int, int)':
holiday.cpp:39:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     int mid = r + l >> 1;
      |               ~~^~~
holiday.cpp: In function 'long long int get(int, int, int, int)':
holiday.cpp:48:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     int mid = r+ l >> 1;
      |               ~^~~
holiday.cpp: In function 'void Init(int)':
holiday.cpp:69:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |             int mid = R + L >> 1;
      |                       ~~^~~

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