| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 157410 |
2019-10-11T12:21:08 Z |
ryansee |
Candies (JOI18_candies) |
C++14 |
|
65 ms |
2552 KB |
#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';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
65 ms |
2552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
65 ms |
2552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
