Submission #1027840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027840		dozer	Holiday (IOI14_holiday)	C++14	24 / 100	5076 ms	65536 KiB

holiday

#include"holiday.h"
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define LL node * 2
#define RR node * 2 + 1
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define ll long long
#define MAXN 200005


const int modulo = 1e9+7;
const ll INF = 2e18 + 7;

//l - r is the range for which we will compute dp, sl - sr is the range in which we will search for the maximum
inline void compute_dc_dp(int l, int r, int sl, int sr, ll curr_sum, int flag, array<multiset<int>, 2> &curr, vector<int> &arr, vector<ll> &dp){
    if (l > r) return;
    int mid = (l + r) / 2;
    pair<ll, ll> opt = {0, sl};
    vector<array<int, 4>> rollback; // first is set index, second is type of operation -> 0 is erase 1 is insert last one is time
    for (int i = sl; i <= sr; i++){
        if (i * flag > mid) break;
        if (i != 0) { //umm, not fully sure of this but whatever
            curr[1].insert(arr[i]);
            rollback.pb({1, 1, arr[i], i}); 
        }
        while(curr[0].size() < mid - flag * i && !curr[1].empty()){
            int top = *curr[1].rbegin();
            rollback.pb({1, 0, top, i});
            curr[1].erase(curr[1].find(top));
            curr_sum += top;
            curr[0].insert(top);
            rollback.pb({0, 1, top, i});
        }

        while(curr[0].size() > mid - flag * i){
            int top = *curr[0].begin();
            curr[0].erase(curr[0].begin());
            rollback.pb({0, 0, top, i});
            curr_sum -= top;
            curr[1].insert(top);
            rollback.pb({1, 1, top, i});
        }

        while(!curr[0].empty() && !curr[1].empty() && *curr[0].begin() < *curr[1].rbegin()){
            int top = *curr[1].rbegin();
            rollback.pb({1, 0, top, i});
            curr[1].erase(curr[1].find(top));
            curr_sum += top;
            curr[0].insert(top);
            rollback.pb({0, 1, top, i});

            top = *curr[0].begin();
            curr[0].erase(curr[0].begin());
            rollback.pb({0, 0, top, i});
            curr_sum -= top;
            curr[1].insert(top);
            rollback.pb({1, 1, top, i});
        }
       // cout<<"ğaa "<<mid<<sp<<sl<<sp<<sr<<sp<<i<<sp<<curr_sum<<endl;
        opt = max(opt, {curr_sum, i}); // does it matter which of the optimals we choose??
    }
   // cout<<"opt : "<<mid<<sp<<flag<<" : "<<opt.st<<sp<<opt.nd<<endl;


    int pos = opt.nd;
    dp[mid] = opt.st;

    while(!rollback.empty() && rollback.back()[3] >= pos){
        array<int, 4> tmp = rollback.back();
        rollback.pop_back();
        int p = tmp[0], val = tmp[2];
        if (tmp[1] == 1){ //it was insert, so we erase
            curr[p].erase(curr[p].find(val));
            if (p == 0) curr_sum -= val;
        }
        else{
            curr[p].insert(val);
            if (p == 0) curr_sum += val;
        }
    }


    compute_dc_dp(mid + 1, r, pos, sr, curr_sum, flag, curr, arr, dp);


    while(!rollback.empty()){
        array<int, 4> tmp = rollback.back();
        rollback.pop_back();
        int p = tmp[0], val = tmp[2];
        if (tmp[1] == 1){ //it was insert, so we erase
            curr[p].erase(curr[p].find(val));
            if (p == 0) curr_sum -= val;
        }
        else{
            curr[p].insert(val);
            if (p == 0) curr_sum += val;
        }
    }
    compute_dc_dp(l, mid - 1, sl, pos, curr_sum, flag, curr, arr, dp);
}



long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    vector<ll> lft[2], rgt[2];
    for (int i = 0; i < 2; i++){
        lft[i].resize(d + 1, 0);
        rgt[i].resize(d + 1, 0);
    }

    vector<int> L, R;
    L.pb(0), R.pb(0);

    for (int i = start - 1; i >= 0; i--){
        L.pb(attraction[i]);
    }

    array<multiset<int>, 2> tmp;

    compute_dc_dp(0, d, 0, L.size() - 1, 0, 1, tmp, L, lft[0]);
    compute_dc_dp(0, d, 0, L.size() - 1, 0, 2, tmp, L, lft[1]);


    for (int i = start + 1; i < n; i++)
        R.pb(attraction[i]);

    compute_dc_dp(0, d, 0, R.size() - 1, 0, 1, tmp, R, rgt[0]);
    compute_dc_dp(0, d, 0, R.size() - 1, 0, 2, tmp, R, rgt[1]);

    
    ll ans = 0;
    for (int i = 0; i <= d; i++){
        ll t1 = lft[0][i] + rgt[1][d - i];
        ll t2 = lft[1][i] + rgt[0][d - i];
        ll t3 = 0, t4 = 0;
        if (i < d) t3 = lft[0][i] + rgt[1][d - i - 1] + attraction[start];
        if (i < d) t4 = lft[1][i] + rgt[0][d - i - 1] + attraction[start];
        ans = max(ans, max(t1, t2));
        ans = max(ans, max(t3, t4));
    }
    return ans;
}
/*

int main() {
    fileio();
    int n, start, d;
    int attraction[100000];
    int i, n_s;
    n_s = scanf("%d %d %d", &n, &start, &d);
    for (i = 0 ; i < n; ++i) {
	n_s = scanf("%d", &attraction[i]);
    }
    printf("%lld\n", findMaxAttraction(n, start, d,  attraction));
    cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
    return 0;
}*/

Compilation message (stderr)

holiday.cpp: In function 'void compute_dc_dp(int, int, int, int, long long int, int, std::array<std::multiset<int>, 2>&, std::vector<int>&, std::vector<long long int>&)':
holiday.cpp:35:30: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |         while(curr[0].size() < mid - flag * i && !curr[1].empty()){
      |               ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
holiday.cpp:44:30: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |         while(curr[0].size() > mid - flag * i){
      |               ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

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