제출 #1302032

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1302032		Tymond	휴가 (IOI14_holiday)	C++20	100 / 100	455 ms	19048 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

struct pair_hash{
  size_t operator()(const pair<int,int>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};

const int BASE = (1 << 18);
pair<int, ll> tree[2 * BASE + 7];
vi id;
vll A;

void upd(int ind, int ch, ll val){
    ind += BASE;
    while(ind > 0){
        tree[ind].fi += ch;
        tree[ind].se += (ch * val);
        ind /= 2;
    }
}

ll findSum(int v, int k){
    if(k == 0){
        return 0LL;
    }
    if(tree[v].fi == k){
        return tree[v].se;
    }

    if(k <= tree[2 * v + 1].fi){
        return findSum(2 * v + 1, k);
    }
    return findSum(2 * v + 1, tree[2 * v + 1].fi) + findSum(2 * v, k - tree[2 * v + 1].fi);
}

ll getSum(int k){
    if(tree[1].fi <= k){
        return tree[1].se;
    }

    return findSum(1, k);
}

void calc(int a, int b, int l, int p, vector<pll>& ret){
    if(a > b){
        return;
    }

    int mid = (a + b) / 2;
    //policz f(mid)
    int f = l;
    for(int i = l; i <= p; i++){
        upd(id[i], 1, A[i]);
        if(i > mid){
            continue;
        }
        ll val = getSum(mid - i);
        if(val > ret[mid].se){
            f = i;
            ret[mid].fi = i;
            ret[mid].se = val;
        }
    }
    for(int i = l; i <= p; i++){
        upd(id[i], -1, A[i]);
    }
    calc(a, mid - 1, l, f, ret);
    for(int i = l; i <= f - 1; i++){
        upd(id[i], 1, A[i]);
    }
    calc(mid + 1, b, f, p, ret);
    for(int i = l; i <= f - 1; i++){
        upd(id[i], -1, A[i]);
    }
}

vector<pll> calcRes(vll x, int d){
    if(sz(x) == 0){
        vector<pll> res(d + 1, mp(0LL, 0LL));
        return res;
    }
    id.resize(sz(x));
    vector<pll> vec;
    for(int i = 0; i < sz(x); i++){
        vec.pb(mp(x[i], i));
    }

    sort(all(vec));
    for(int i = 0; i < sz(vec); i++){
        id[vec[i].se] = i;
    }

    A = x;
    vector<pll> ret(d + 1, mp(0LL, 0LL));
    calc(0, d, 0, sz(x) - 1, ret);
    return ret;
}

//idziesz w lewo, zawracasz i idziesz w prawo
ll solve(vll left, vll right, int n, int d){
  //  cerr << "============\n";
  //  cerr << n << ' ' << d << '\n';
  //  debug(left);
  //  debug(right);

    vector<pll> resL = calcRes(left, d);
    vector<pll> resR = calcRes(right, d);
   // debug(resL);
   // debug(resR);
    ll ans = 0LL;
    for(int i = 0; i <= d; i++){
        ans = max(ans, resL[i].se);
        ans = max(ans, resL[i].se + resR[max(0LL, d - i - resL[i].fi - 1)].se);
    }

    return ans;
}

ll findMaxAttraction(int n, int start, int d, int attraction[]) {
    vll a = {};
    vll b = {};

    for(int i = 0; i < start; i++){
        a.pb(attraction[i]);
    }

    a.pb(attraction[start]);
    for(int i = n - 1; i > start; i--){
        b.pb(attraction[i]);
    }

    reverse(all(a));
    reverse(all(b));
    ll ans = solve(a, b, n, d);
    reverse(all(a));
    reverse(all(b));
    a.pop_back();
    b.pb(attraction[start]);
    reverse(all(a));
    reverse(all(b));
    ans = max(ans, solve(b, a, n, d));
    return ans;
}

// int main(){
//     int n, start, d;
//     int attraction[100000];
//     cin >> n >> start >> d;
//     for(int i = 0; i < n; i++){
//         cin >> attraction[i];
//     }

//     cout << findMaxAttraction(n, start, d, attraction) << '\n';
//     return 0;
// }

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