Submission #157410

#	Time	Username	Problem	Language	Result	Execution time	Memory
157410		ryansee	Candies (JOI18_candies)	C++14	0 / 100	65 ms	2552 KiB

candies

#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define btinpct(x) __builtin_popcountll((x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?b:gcd(b%a,a); }

#define ll long long int 
#define ld long double
#define FOR(ii, ss, ee) for(ll ii = (ss); ii <= (ll)(ee); ++ii)
#define DEC(ii, ss, ee) for(ll ii = (ss); ii >= (ll)(ee); --ii)
typedef pair <ll, ll> pi; typedef pair <ll, pi> spi; typedef pair <pi, pi> dpi;

#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
// #define cerr if(0)cout
#define MAXN (200006)
ll n, A[MAXN];
set<spi, greater<spi>> ms;
spi status[MAXN];
struct ufds_{
	int p[MAXN], sz[MAXN];
	ufds_() {
		FOR(i,0,MAXN-1) p[i]=i, sz[i]=1;
	}
	void merge(ll x,ll y) {
		x=find(x),y=find(y);
		if(x==y) return;
// 		if(status[x].f!=0&&status[y].f!=0) assert(0);
		sz[y]+=sz[x];
		p[x]=y;
	}
	ll find(ll x) { return (p[x]==x)?x:p[x]=find(p[x]); }
	bool same(ll a,ll b) { return find(a)==find(b); }
	ll szz(ll x) { return sz[find(x)]; }
} ufds;
void re(ll x) {
	ll a=status[x].s.f, b=status[x].s.s;
	if(a>=1&&b<=n) ms.erase(status[x]);
	else if(ms.find(status[x])!=ms.end()) ms.erase(status[x]);
}
void merge(ll x,ll y) {
	ll ox=x, oy=y;
	if(0)assert(y-x==2);
	ll o=y-1;
	// cerr<<"hmm: "<<x<<' '<<y<<'\n';
	x=ufds.find(x), y=ufds.find(y);
	// cerr<<"merging: "<<x<<' '<<y<<'\n';
	if(x==y) { if(0)assert(0); return; }
	re(x), re(y); re(ox), re(oy);
	status[y].s.f=status[x].s.f;
	status[x].s.s=status[y].s.s;
	cerr<<ox<<' '<<oy<<' '<<status[x].f<<' '<<status[y].f<<' '<<A[o]<<'\n';
	status[x].f += status[y].f-A[o];
	status[y]=status[x];
	status[y].f=0;
	ufds.merge(y,x);
	cerr<<"nice: "<<status[x].f<<' '<<x<<'\n';
	cerr<<ox<<' '<<oy<<'\n';
	
	if(status[x].s.f >= 1 && status[x].s.s <= n) ms.ins(status[x]);
}
struct node {
	int s,e,m;
	ll v, add;
	node *l,*r;
	node (ll _S,ll _E){
		s=_S,e=_E,m=(s+e)>>1;
		v=add=0;
		if(s^e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	void flip(ll x, ll y) {
		if(s==x&&e==y) {
			++ add;
			return;
		}
		if(x>m) r->flip(x,y);
		else if(y<=m) l->flip(x,y);
		else l->flip(x,m), r->flip(m+1,y);
	}
	ll value() {
		if(s==e) v += add;
		if(s^e) {
			l->add+=add;
			r->add+=add;
		}
		add=0;
		return v;
	}
	ll rmq(ll x) {
		value();
		if(s==e) { return (v&1); }
		if(x>m) return r->rmq(x); else return l->rmq(x);
	}
} *in;
ll sum[MAXN];
bool valid(ll x) { return x>=1 && x<=n; }
void degug() { return;
	for(auto i:ms) {
		cerr<<i.f<<' '<<i.s.f<<' '<<i.s.s<<'\n';
	}
	FOR(i,1,n) {
		cerr<<"ufds: "<<ufds.find(i)<<'\n';
	}
}
int main()
{
	// freopen("out1","w",stdout);
	FAST
	cin>>n;
	ll ans=0, where=0;
	FOR(i,1,n) { cin>>A[i]; tie(ans, where)=max(pi(ans, where), pi(A[i], i)); sum[i]=sum[i-1]+A[i]; }
	priority_queue<pi> pq;
	FOR(i,1,n) if(llabs(where-i)>1) pq.emplace(A[i], i);
	in=new node(0, n+1); // extra space
	in->flip(where,where);status[where]=spi(A[where-1]+A[where+1]-A[where], pi(where-1, where+1));
	if(where>1 && where < n) ms.ins(spi(A[where-1]+A[where+1]-A[where], pi(where-1, where+1)));
	if(valid(where-1)) ufds.merge(where-1, where);
	if(valid(where+1)) ufds.merge(where+1, where);
	cout<<ans<<'\n';
	FOR(i,2,(n+1)/2) {
		while(pq.size() && (in->rmq(pq.top().s-1) || in->rmq(pq.top().s+1) || in->rmq(pq.top().s))) {
			pq.pop();
		}
		while(ms.size()) {
		    ll c=ms.begin()->f, a=ms.begin()->s.f, b=ms.begin()->s.s;  degug();
            ll guy=ufds.find(a);
            if(status[guy].f != c || status[guy].s.f != a || status[guy].s.s != b) ms.erase(ms.begin());
            else break;
		}
		if(pq.size() && pq.top().f >= ms.begin()->f) {
			cerr<<"heyyyy\n";
			in->flip(pq.top().s, pq.top().s);
			ans += pq.top().f;
// 			assert(in->rmq(pq.top().s-1)==0&&in->rmq(pq.top().s+1)==0);
// 			assert(ufds.find(pq.top().s)==pq.top().s);
			status[pq.top().s]=spi(A[pq.top().s-1]+A[pq.top().s+1]-A[pq.top().s], pi(pq.top().s-1, pq.top().s+1));
			if(valid(pq.top().s-1)&&ufds.szz(pq.top().s-1)==1) cerr<<"gg2\n", ufds.merge(pq.top().s-1, pq.top().s);
			if(valid(pq.top().s+1)&&ufds.szz(pq.top().s+1)==1) cerr<<"gg2\n", ufds.merge(pq.top().s+1, pq.top().s);
			if(pq.top().s>1&&pq.top().s<n) ms.ins(spi(A[pq.top().s-1]+A[pq.top().s+1]-A[pq.top().s], pi(pq.top().s-1, pq.top().s+1)));
			if(pq.top().s > 1 && in->rmq(pq.top().s-2)) merge(pq.top().s-2, pq.top().s);
			if(pq.top().s+2 <= n && in->rmq(pq.top().s+2)) merge(pq.top().s, pq.top().s+2);
			pq.pop();
		} else {
			ll c=ms.begin()->f, a=ms.begin()->s.f, b=ms.begin()->s.s;  degug();
// 			assert(a>=1 && b<=n);
			ans += c;
			in->flip(a, b);
			ll guy=ufds.find(a);
			ms.erase(ms.begin());
			cerr<<guy<<' '<<status[guy].f<<' '<<status[guy].s.f<<' '<<status[guy].s.s<<' '<<a<<' '<<b<<'\n';
			assert(status[guy].f==c);
			assert(status[guy].s.f==a);
			assert(status[guy].s.s==b);
			-- status[guy].s.f;
			++ status[guy].s.s;
			-- a, ++ b;
			if(i==(n+1)/2) cerr<<a<<' '<<b<<' '<<status[guy].f<<'\n';
			if(status[guy].s.f>=1 && status[guy].s.s<=n) {
				status[guy].f=A[b]+A[a]-status[guy].f;
				cerr<<"special delievey yyy: "<<status[guy].f<<'\n';
				ms.ins(status[guy]);
				if(a>1 && in->rmq(a-1)) merge(a-1, a+1);
				if(b<n && in->rmq(b+1)) merge(b-1, b+1);
			}
			if(a>=1&&a<=n) if(ufds.find(a)!=ufds.find(a+1)) ufds.merge(a, a+1);
			if(b>=1&&b<=n) if(ufds.find(b)!=ufds.find(b-1)) ufds.merge(b, b-1);
		}
		cout<<ans<<'\n';
	}
}

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