Submission #957561

#	Time	Username	Problem	Language	Result	Execution time	Memory
957561		parlimoos	Candies (JOI18_candies)	C++14	0 / 100	2 ms	604 KiB

candies

//‌‌Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<ll , x>
#define endl '\n'

int n;
vector<ll> a;
set<arr(3)> ord , sgs;
ll o = 0;

void uSg(ll l , ll r , ll c){
    arr(3) d = {l , r , c};
    auto itr = sgs.find(d);
    ord.erase({(*itr)[2] , (*itr)[0] , (*itr)[1]});
    vector<arr(3)> dls;
    dls.pb({l , r , c});
    o += c , c = (-c);
    if(itr != sgs.bg()){
        --itr;
        c += (*itr)[2] , l = (*itr)[0];
        ord.erase({(*itr)[2] , (*itr)[0] , (*itr)[1]}) , dls.pb({(*itr)[0] , (*itr)[1] , (*itr)[2]});
        itr++;
    }
    if(itr != --sgs.end()){
        ++itr;
        c += (*itr)[2] , r = (*itr)[1];
        ord.erase({(*itr)[2] , (*itr)[0] , (*itr)[1]}) , dls.pb({(*itr)[0] , (*itr)[1] , (*itr)[2]});
        itr--;
    }
    ord.insert({c , l , r}) , sgs.insert({l , r , c});
    for(auto &dl : dls) sgs.erase(dl);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 0 ; i < n ; i++){
        int d;
        cin >> d;
        a.pb(d);
    }
    for(int i = 0 ; i < n ; i++){
        sgs.insert({i , i , a[i]}) , ord.insert({a[i] , i , i});
    }
    for(int i = 1 ; i <= ((n + 1) >> 1) ; i++){
        auto itr = --(ord.end());
        ll l = (*itr)[1] , c = (*itr)[0] , r = (*itr)[2];
        uSg(l , r , c);
        cout << o << endl;
    }
}

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