Submission #722701

#	Time	Username	Problem	Language	Result	Execution time	Memory
722701		Ronin13	Holiday (IOI14_holiday)	C++14	100 / 100	2412 ms	31692 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define epb emplace_back
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;


const int dmax = 400001;
const int nmax = 200001;
struct node{
    ll val;
    ll x;
    node(){
        val = x = 0;
        return;
    }
}t[4 * nmax];

void upd(int v, int l, int r, int pos, ll val){
    if(l > pos || r < pos)
        return;
    if(l == r){
        t[v].val = val;
        t[v].x = (val > 0);
        if(val > 1e9)
            t[v].x = val;
        return;
    }
    int m = (l + r) / 2;
    upd(2 * v, l, m, pos, val);
    upd(2 * v + 1, m + 1, r, pos, val);
    t[v].val = t[v * 2].val + t[v * 2 + 1].val;
    t[v].x = t[v * 2].x + t[v * 2 + 1].x;
}

ll get(int v, int l, int r, int val){
    if(l == r){
        return 0;
    }
    int m = (l + r) /2;
    if(t[v * 2].x <= val)
        return t[v * 2].val + get(2 * v + 1, m + 1, r, val - t[v * 2].x);
    return get(2 * v, l, m, val);
}

pll ans[dmax][4];
ll a[nmax];
int b[nmax];
//op=0 --->
//op=1 <---
int n;
void divide_and_conquer(int l, int r, int optl, int optr, int op, int st, int ind){
    int m = (l + r) / 2;
    if(l > r)
        return;
    pll mx = {0, optl};
    if(op == 0){
        for(int j = optl; j <= optr; j++){
            upd(1, 1, n + 1, b[j], a[j]);
            ll cur = get(1, 1, n + 1, m - j + st);
            if(cur > mx.f)
                mx.f = cur, mx.s = j;
        }
        ans[m][ind] = mx;
        for(int j = optl; j <= optr; j++)
            upd(1, 1, n + 1, b[j], 0);
        divide_and_conquer(l, m - 1, optl, mx.s, op, st, ind);
        for(int j = optl; j < mx.s; j++){
            upd(1, 1, n + 1, b[j], a[j]);
        }
        divide_and_conquer(m + 1, r, mx.s, optr, op, st, ind);
        for(int j = optl; j <= optr; j++)
            upd(1, 1, n + 1, b[j], 0);
    }
    else {
        mx.s = optr;
        for(int j = optr; j >= optl; j--){
            upd(1, 1, n + 1, b[j], a[j]);
            ll cur = get(1, 1, n + 1, m - st + j);
            if(cur > mx.f)
                mx.f = cur, mx.s = j;
        }
        ans[m][ind] = mx;
        for(int j = optl; j <= optr; j++)
            upd(1, 1, n + 1, b[j], 0);
        divide_and_conquer(l, m - 1,  mx.s, optr, op, st, ind);
        for(int j = optr; j > mx.s; j--){
            upd(1, 1, n + 1, b[j], a[j]);
        }
        divide_and_conquer(m + 1, r, optl, mx.s, op, st, ind);
        for(int j = optl; j <= optr; j++)
            upd(1, 1, n + 1, b[j], 0);
    }


    return;
}


long long findMaxAttraction(int N, int start, int d, int attraction[]) {
    n = N;
    pll c[n + 1];
    for(int i = 1; i <= N; i++)
        a[i] = attraction[i - 1];
    for(int i = 1; i <= n; i++){
        c[i] = {a[i], i};
    }
    upd(1, 1, n + 1, n + 1, 1e9 + 1);
    sort(c + 1, c + n + 1);
    reverse(c + 1, c + n + 1);
    for(int i = 1; i <= n; i++)
        b[c[i].s] = i;
    start++;
    divide_and_conquer(0, d, start, n, 0, start, 0);
    divide_and_conquer(0, d, 1, start, 1, start, 1);


  //  cout << ans[d][0].f << ' ' << ans[d][1].f << "\n";
    if(start == 1){
        return ans[d][0].f;
    }
    if(start == n)
        return ans[d][1].f;
    divide_and_conquer(0, d, start + 1, n, 0, start + 1, 2);
    divide_and_conquer(0, d, 1, start - 1, 1, start - 1, 3);
    ll x = max(ans[d][0].f, ans[d][1].f);
    for(int i = 1; i < d; i++){
        ll u = ans[i][0].f;
        ll pos = ans[i][0].s;
        ll rem = d - i - (pos - start);
        rem--;

        if(rem >= 0)x = max(x, u + ans[rem][3].f);
        u = ans[i][1].f;
        pos = ans[i][1].s;
        rem = d - i - (start - pos);
        rem--;
        if(rem  >= 0)x = max(x, u + ans[rem][2].f);
    }
    return x;
}

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