제출 #1277018

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277018		trandangquang	휴가 (IOI14_holiday)	C++17	0 / 100	201 ms	131072 KiB

holiday

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

using namespace std;

#define task "test"
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define bit(s, i) (((s) >> (i)) & 1)
#define ii pair <int, int>
#define vii vector <ii>
#define vi vector <int>
#define fi first
#define se second
//#define int long long
#define ll long long
#define eb emplace_back
#define pb push_back
#define __builtin_popcount __builtin_popcountll

const int NX = 250005;

int n, st, d, att[NX], upto[20]; ii bestr[NX], bestl[NX];
vi rar;

/// bestr[u] = {gia tri, vi tri gan nhat} khi di voi thoi gian u
/// bestl[u]: tuong tu voi bestr[u]

struct segmentTree {
    struct node {
        int num = 0;
        ll sum = 0;
    } st[NX<<2];

    void reset() {
        node tmp = {0, 0};
        fill(begin(st), end(st), tmp);
    }

    void upd(int x, int val) {
        int id=1, l=1, r=sz(rar);
        while(1) {
            if(l==r) break;
            int m=(l+r)>>1;
            if(x<=m) {
                id = id<<1;
                r=m;
            }
            else {
                id = id<<1|1;
                l=m+1;
            }
        }

        st[id].num += val;
        st[id].sum += val*rar[x-1];

        while(id>1) {
            id /= 2;
            st[id].num = st[id<<1].num + st[id<<1|1].num;
            st[id].sum = st[id<<1].sum + st[id<<1|1].sum;
        }
    }

    ll get_max(int nli) {
        int id=1, l=1, r=sz(rar);

        ll res = 0;
        while(l<=r) {
            if(l==r) break;

            int m=(l+r)>>1;

            if(st[id<<1|1].num <= nli) {
                nli-=st[id<<1|1].num;
                res+=st[id<<1|1].sum;
                id=id<<1;
                r=m;
            }
            else {
                id=id<<1|1;
                l=m+1;
            }
        }

        return res + min(nli, st[id].num)*rar[l-1];
    }
} smt[20];


void calcr(int L, int R, int optL, int optR, int lvl) {
//    printf("Range: %d %d, optRange: %d %d\n", L, R, optL, optR);
    if(L > R) return;

    int mid = (L+R) >> 1;
    FOR(i, optL, optR) {
        if(mid-(i-st) < 0) break; /// neu nhu di qua xa -> break
        while(upto[lvl] < i) smt[lvl].upd(att[++upto[lvl]], 1);
        int nwVal = smt[lvl].get_max(mid-(i-st));
        if(nwVal > bestr[mid].fi) {
            bestr[mid].fi = nwVal;
            bestr[mid].se = i;
        }
    }

    calcr(L, mid-1, optL, bestr[mid].se, lvl+1);
    calcr(mid+1, R, bestr[mid].se, optR, lvl+1);
}

void calcl(int L, int R, int optL, int optR, int lvl) {
//    printf("Range: %d %d, optRange: %d %d\n", L, R, optL, optR);
    if(L > R) return;

    int mid = (L+R) >> 1;
    FORD(i, optR, optL) {
        if(mid-(st-i) < 0) break; ///
        while(upto[lvl] > i) smt[lvl].upd(att[--upto[lvl]], 1);
        int nwVal = smt[lvl].get_max(mid-(st-i));
//        if(mid == 3) cout << i << " " << nwVal << " " << mid-(st-i) << '\n';
        if(nwVal > bestl[mid].fi) {
            bestl[mid].fi = nwVal;
            bestl[mid].se = i;
        }
    }

//    cout << mid << " " << bestl[mid].se<<" "<<bestl[mid].fi<<'\n';
    calcl(L, mid-1, bestl[mid].se, optR, lvl+1);
    calcl(mid+1, R, optL, bestl[mid].se, lvl+1);
}

ll findMaxAttraction(int N, int ST, int D, int attraction[]){
    n=N; st=ST; d=D;
    ++st;
    FOR(i, 1, n) {
        att[i]=attraction[i-1];
        rar.eb(att[i]);
    }

    sort(all(rar));
    FOR(i, 1, n) {
        att[i] = upper_bound(all(rar), att[i]) - rar.begin();
    }

    FOR(i, 1, d) bestl[i].fi = bestr[i].fi = -1;

    FOR(i, 1, 19) upto[i] = st;
    calcr(1, d, st+1, n, 1);

    FOR(i, 1, 19) {
        smt[i].reset();
        upto[i] = st;
    }
    calcl(1, d, 1, st-1, 1);

    int ans = 0;
    FOR(i, 0, d) {
        if(d-i-(bestr[i].se-st)>=0) {
            ans = max(ans, bestr[i].fi + bestl[d-i-(bestr[i].se-st)].fi);

        }
        if(d-i-(st-bestl[i].se)>=0) {
            ans = max(ans, bestl[i].fi + bestr[d-i-(st-bestl[i].se)].fi);
        }
        ans = max(ans, bestl[i].fi);
        ans = max(ans, bestr[i].fi);
    }

    --d;
    FOR(i, 0, d) {
        if(d-i-(bestr[i].se-st)>=0) {
            ans = max(ans, bestr[i].fi + bestl[d-i-(bestr[i].se-st)].fi + rar[att[st] - 1]);
        }
        if(d-i-(st-bestl[i].se)>=0) {
            ans = max(ans, bestl[i].fi + bestr[d-i-(st-bestl[i].se)].fi + rar[att[st] - 1]);
        }
        ans = max(ans, bestl[i].fi + rar[att[st] - 1]);
        ans = max(ans, bestr[i].fi + rar[att[st] - 1]);
    }

    return ans;
}

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