Submission #718178

#	Time	Username	Problem	Language	Result	Execution time	Memory
718178		radal	Candies (JOI18_candies)	C++17	100 / 100	647 ms	21532 KiB

candies

#include <bits/stdc++.h>
//#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O3")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 4e5+20,mod = 998244353;
constexpr ll inf = 1e18+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    } 
    return z; 
}


ll ps[N],b[N];
int a[N];
bool L[N],R[N];
set<pair<ll,int> > st;
map<int,int> mp[2]; // L R

int main(){
	ios :: sync_with_stdio(0); cin.tie(0);  cout.tie(0);
	int n;
	cin >> n;
	rep(i,1,n+1){
		cin >> a[i];
		ps[i] = a[i];
		b[i] = a[i];
		if (i > 1) ps[i] += ps[i-2];
		st.insert({a[i],i});
	}
	if (n == 1){
	   	cout << a[1] << endl;
		return 0;
	}
	int T = (n+1)/2;
	ll ans = 0;
	while (T--){
		auto [val,i] = (*st.rbegin());
		st.erase({val,i});
		ans += val;
		cout << ans << endl;
		L[i+1] = 1;
		R[i-1] = 1;
		if (i == 1){
			if (mp[0].find(2) != mp[0].end()){
				int x = mp[0][2];
				int j = 2*x+1;
				st.erase({b[j],j});
				mp[0].erase(2);
				mp[1].erase(j-1);
				mp[0][1] = (j+1)/2;
				mp[1][j] = (j+1)/2;
				L[j+1] = 1;
				st.erase({b[j+1],j+1});
				if (j < n-1 && R[j+1]){
					x = mp[0][j+2];
					mp[0].erase(j+2);
					mp[1].erase(j);
					mp[0][1] += x;
					int k = mp[0][1]*2-1;
					mp[1][k] = (k+1)/2;
					st.erase({b[k+1],k+1});
				}
				continue;
			}
			st.erase({b[2],2});
			if (!R[2]){
				mp[0][1] = 1;
				mp[1][1] = 1;
				continue;
			}
			mp[0][1] = 1+mp[0][3];
			mp[0].erase(3);
			int j = 2*mp[0][1]-1;
			mp[1][j] = (j+1)/2;
			st.erase({b[j+1],j+1});
			continue;
		}
		if (i == n){
            if (mp[1].find(n-1) != mp[1].end()){
                int x = mp[1][n-1];
                int j = n-2*x;
                st.erase({b[j],j});
                mp[1].erase(n-1);
                mp[0].erase(j+1);
                mp[0][j] = (n-j)/2+1;
                mp[1][n] = (n-j)/2+1;
                R[j-1] = 1;
                st.erase({b[j-1],j-1});
                if (j > 2 && L[j-1]){
                    x = mp[1][j-2];
                    mp[0].erase(j);
                    mp[1].erase(j-2);
                    mp[1][n] += x;
                    int k = n-(mp[1][n]-1)*2;
                    mp[0][k] = (n-k)/2+1;
                    st.erase({b[k-1],k-1});
                }
                continue;
            }
            st.erase({b[n-1],n-1});
            if (!L[n-1]){
                mp[0][n] = 1;
                mp[1][n] = 1;
                continue;
            }
            mp[1][n] = 1+mp[1][n-2];
			mp[1].erase(n-2);
            int j = n-2*(mp[1][n]-1);
            mp[0][j] = (n-j)/2 + 1;
            st.erase({b[j-1],j-1});
            continue;
		}
		if (!L[i] && !R[i]){
			int r = i, l = i;
			if (R[i+1]){
			   	r = i+2*mp[0][i+2];
				mp[0].erase(i+2);
				st.erase({b[i+1],i+1});
			}
			if (L[i-1]){
				l = i-2*mp[1][i-2];
				mp[1].erase(i-2);
				st.erase({b[i-1],i-1});
			}
			mp[0][l] = (r-l+2)/2;
			mp[1][r] = (r-l+2)/2;
            st.erase({b[l-1],l-1});
            st.erase({b[r+1],r+1});
			if (l > 1 && r < n){
				ll s = ps[r+1]-ps[l-1]+a[l-1];
				s -= (ps[r]-ps[l-2]);
				b[l-1] = b[r+1] = s;
                st.insert({b[l-1],l-1});
                st.insert({b[r+1],r+1});
			}
			continue;
		}
		if (R[i]){
			int l = i;
			if (i > 2 && mp[1].find(i-2) != mp[1].end()){
			   	l = i-mp[1][i-2]*2;
				mp[1].erase(i-2);
				st.erase({b[i-1],i-1});
			}
			int j = 2*mp[0][i+1]+i;
			mp[0].erase(i+1);
			mp[1].erase(j-1);
			st.erase({b[j],j});
			mp[0][l] = (j-l+2)/2;
			mp[1][j] = (j-l+2)/2;
			L[j+1] = 1;
			int r = j;
			if (j < n-1 && R[j+1]){
				st.erase({b[j+1],j+1});
				mp[0][l] += mp[0][j+2];
				r = l + 2*(mp[0][l]-1);
				mp[1][r] = (r-l+2)/2;
				mp[1].erase(j);
			}
			st.erase({b[l-1],l-1});
			st.erase({b[r+1],r+1});
			if (l > 1 && r < n){
				ll s = ps[r+1]-ps[l-1]+a[l-1];
				s -= (ps[r]-ps[l-2]);
				b[l-1] = b[r+1] = s;
                st.insert({b[l-1],l-1});
                st.insert({b[r+1],r+1});
			}
			continue;
		}
        if (L[i]){
            int r = i;
            if (i < n-1 && mp[0].find(i+2) != mp[0].end()){
                r = i+mp[0][i+2]*2;
                mp[0].erase(i+2);
                st.erase({b[i+1],i+1});
            }
            int j = i-2*mp[1][i-1];
            mp[1].erase(i-1);
            mp[0].erase(j+1);
            st.erase({b[j],j});
            mp[0][j] = (r-j+2)/2;
            mp[1][r] = (r-j+2)/2;
            R[j-1] = 1;
            int l = j;
            if (j > 2 && L[j-1]){
                st.erase({b[j-1],j-1});
                mp[1][r] += mp[1][j-2];
                l = r - 2*(mp[1][r]-1);
                mp[0][l] = (r-l+2)/2;
                mp[0].erase(j);
            }
            st.erase({b[l-1],l-1});
            st.erase({b[r+1],r+1});
            if (l > 1 && r < n){
                ll s = ps[r+1]-ps[l-1]+a[l-1];
                s -= (ps[r]-ps[l-2]);
                b[l-1] = b[r+1] = s;
                st.insert({b[l-1],l-1});
                st.insert({b[r+1],r+1});
            }
            continue;
		}
	}
} 

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