답안 #157411

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
157411	2019-10-11T12:22:46 Z	ryansee	Candies (JOI18_candies)	C++14	100 / 100	668 ms	43796 KB

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

8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	2296 KB	Output is correct
2	Correct	7 ms	2296 KB	Output is correct
3	Correct	6 ms	2296 KB	Output is correct
4	Correct	7 ms	2296 KB	Output is correct
5	Correct	6 ms	2296 KB	Output is correct
6	Correct	6 ms	2296 KB	Output is correct
7	Correct	7 ms	2424 KB	Output is correct
8	Correct	6 ms	2424 KB	Output is correct
9	Correct	6 ms	2296 KB	Output is correct
10	Correct	6 ms	2296 KB	Output is correct
11	Correct	6 ms	2412 KB	Output is correct
12	Correct	6 ms	2396 KB	Output is correct
13	Correct	6 ms	2344 KB	Output is correct
14	Correct	6 ms	2300 KB	Output is correct
15	Correct	7 ms	2424 KB	Output is correct
16	Correct	6 ms	2296 KB	Output is correct
17	Correct	6 ms	2296 KB	Output is correct
18	Correct	6 ms	2300 KB	Output is correct
19	Correct	6 ms	2344 KB	Output is correct
20	Correct	6 ms	2296 KB	Output is correct

Subtask #2

92.0 / 92.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	2296 KB	Output is correct
2	Correct	7 ms	2296 KB	Output is correct
3	Correct	6 ms	2296 KB	Output is correct
4	Correct	7 ms	2296 KB	Output is correct
5	Correct	6 ms	2296 KB	Output is correct
6	Correct	6 ms	2296 KB	Output is correct
7	Correct	7 ms	2424 KB	Output is correct
8	Correct	6 ms	2424 KB	Output is correct
9	Correct	6 ms	2296 KB	Output is correct
10	Correct	6 ms	2296 KB	Output is correct
11	Correct	6 ms	2412 KB	Output is correct
12	Correct	6 ms	2396 KB	Output is correct
13	Correct	6 ms	2344 KB	Output is correct
14	Correct	6 ms	2300 KB	Output is correct
15	Correct	7 ms	2424 KB	Output is correct
16	Correct	6 ms	2296 KB	Output is correct
17	Correct	6 ms	2296 KB	Output is correct
18	Correct	6 ms	2300 KB	Output is correct
19	Correct	6 ms	2344 KB	Output is correct
20	Correct	6 ms	2296 KB	Output is correct
21	Correct	603 ms	43616 KB	Output is correct
22	Correct	591 ms	43576 KB	Output is correct
23	Correct	612 ms	43592 KB	Output is correct
24	Correct	396 ms	42376 KB	Output is correct
25	Correct	382 ms	42208 KB	Output is correct
26	Correct	398 ms	42224 KB	Output is correct
27	Correct	598 ms	43796 KB	Output is correct
28	Correct	509 ms	43716 KB	Output is correct
29	Correct	444 ms	43588 KB	Output is correct
30	Correct	447 ms	43616 KB	Output is correct
31	Correct	443 ms	43692 KB	Output is correct
32	Correct	464 ms	43744 KB	Output is correct
33	Correct	518 ms	43356 KB	Output is correct
34	Correct	578 ms	43532 KB	Output is correct
35	Correct	529 ms	43644 KB	Output is correct
36	Correct	600 ms	43528 KB	Output is correct
37	Correct	601 ms	43704 KB	Output is correct
38	Correct	668 ms	43660 KB	Output is correct
39	Correct	390 ms	42360 KB	Output is correct
40	Correct	399 ms	42336 KB	Output is correct
41	Correct	379 ms	42208 KB	Output is correct
42	Correct	450 ms	43580 KB	Output is correct
43	Correct	448 ms	43632 KB	Output is correct
44	Correct	446 ms	43632 KB	Output is correct
45	Correct	452 ms	43636 KB	Output is correct
46	Correct	442 ms	43752 KB	Output is correct
47	Correct	445 ms	43656 KB	Output is correct
48	Correct	525 ms	43488 KB	Output is correct
49	Correct	522 ms	43488 KB	Output is correct
50	Correct	519 ms	43448 KB	Output is correct