Submission #932627

#	Time	Username	Problem	Language	Result	Execution time	Memory
932627		Wael	Candies (JOI18_candies)	C++17	0 / 100	2 ms	10844 KiB

candies

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define log(x) (63^__builtin_clzll(x))
#define endl '\n'
#define int long long
typedef long long ll;
int const M = 1e6 + 10 , lg = 23 , mod[] = {(ll)1e9 + 7 , 100000643} , block = 700;
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
int dx[] = {1 , -1 , 0 , 0} , dy[] = {0 , 0 , 1 , -1};
int s[M] , pref[M] , l[M] , r[M] , one[M];
set<pair<ll , ll>>blocks;

void eraseBlock(int L , int R) {

    one[L] = one[R] = 0;
    int value = (pref[R + 1] - (L - 3 >= 1 ? pref[L - 3] : 0)) - (pref[R] - (L - 2 >= 1 ? pref[L - 2] : 0));
    blocks.erase({value , L});

}

void insertBlock(int L , int R) {

    one[L] = one[R] = 1;
    l[R] = L , r[L] = R;
    int value = (pref[R + 1] - (L - 3 >= 1 ? pref[L - 3] : 0)) - (pref[R] - (L - 2 >= 1 ? pref[L - 2] : 0));
    blocks.insert({value , L});

}

void merge(int l1 , int r1 , int l2 , int r2) {

    eraseBlock(l1 , r1);
    eraseBlock(l2 , r2);
    insertBlock(l1 , r2);

} 

main() {
    ios_base::sync_with_stdio(false);cout.tie(nullptr);cin.tie(nullptr);

    int n;
    cin >> n;

    set<pair<ll , ll>>free;
    for(int i = 1 ; i <= n ; ++i) {
        cin >> s[i];
        pref[i] = s[i];
        if(i - 2 >= 1) pref[i] += pref[i - 2];
        free.insert({s[i] , i});
    }

    int ans = 0;
    for(int i = 1 ; i <= (n + 1) / 2 ; ++i) {
        int value1 = -1e18 , value2 = -1e18;
        if(free.size()) value1 = prev(free.end()) -> F;
        if(blocks.size()) value2 = prev(blocks.end()) -> F;
        
        int L , R;
        if(value1 > value2) {
            ans += value1;
            int index = prev(free.end()) -> S;
            free.erase({s[index] , index});
            insertBlock(index , index);
            L = R = index;
        }
        else {
            ans += value2;
            L = prev(blocks.end()) -> S;
            R = r[L];
            if(L == 1 || R == n) {
                blocks.erase(prev(blocks.end()));
                --i;
                continue;
            }
            eraseBlock(L , R);
            --L , ++R;
            insertBlock(L , R);
        }

        //cerr << value1 << " " << value2 << " " << L << " " << R << endl;
        if(L - 1 >= 1) free.erase({s[L - 1] , L - 1});
        if(R + 1 <= n) free.erase({s[R + 1] , R + 1});

        if(L - 2 >= 1 && one[L - 2]) {
            merge(l[L - 2] , L - 2 , L , R);
            L = l[R];
        }
        if(R + 2 <= n && one[R + 2]) {
            merge(L , R , R + 2 , r[R + 2]);
            R = r[L];
        }

        cout << ans << endl;
    }

    return 0;
}

Compilation message (stderr)

candies.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main() {
      | ^~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 92