Submission #47866

#	Time	Username	Problem	Language	Result	Execution time	Memory
47866		Talant	Candies (JOI18_candies)	C++17	0 / 100	128 ms	188280 KiB

candies

#include <bits/stdc++.h>

#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )
#define Scan(a) scanf ("%I64d", &a)
#define scan(a) scanf ("%d", &a)
#define int long long

using namespace std;

const int inf = (int)1e9 + 7;
const int N = (int)2e5 + 7;

int n;
int a[N];
int od,ev;
int res;
int nxt[N],lst[N];
int prs[N],pr[N];
int ll,rr,mx;
int f[N];

vector <int> ans;

struct node {
      int mx,cur,nxt,prv,id;
      node() {
            mx = cur = nxt = prv = id = 0;
      }
}t[N * 4];

node tt[20][N];

node merge(node a,node b) {
      if (a.mx >= b.mx)
            return a;
      return b;
}

void buildtable() {
      for (int i = 0; i <= ceil(log2(n)); i ++) {
            for (int j = 1; j <= n; j ++) {
                  if (i == 0) {
                        tt[i][j].mx = a[j];
                        tt[i][j].id = j;
                        continue;
                  }
                  tt[i][j] = merge(tt[i - 1][j],tt[i - 1][j + (1 << (i - 1))]);
            }
      }
}
node getmax(int l,int r) {
      node cp;
      if (l > r || l == 0 || r == n + 1)
            return cp;
      int cur = log2(r - l + 1);
      return merge(tt[cur][l],tt[cur][r - (1 << cur) + 1]);
}

void build (int v = 1,int tl = 1,int tr = n) {
      if (tl == tr) {
            if (f[tl]) {
                  int ps = 0;
                  for (ps = tl - 1; ps >= 0; ps --)
                        if (f[ps])
                              break;
                  t[v].prv = ps;
                  lst[tl] = t[v].prv;
                  for (ps = tl + 1; ps <= n + 1; ps ++)
                        if (f[ps])
                              break;
                  t[v].nxt = ps;
                  nxt[tl] = t[v].nxt;

                  t[v].id = tl;
                  t[v].mx = (getmax(t[v].prv,tl - 1).mx + getmax(tl + 1,t[v].nxt).mx) - (a[tl] + a[t[v].prv] + a[t[v].nxt]);
            }
            else t[v].mx = -inf;
      }
      else {
            int tm = (tl + tr) >> 1;
            build(v + v,tl,tm);
            build(v + v + 1,tm + 1,tr);

            t[v] = merge(t[v + v],t[v + v + 1]);
      }
}
void update (int pos,int v = 1,int tl = 1,int tr = n) {
      if (tl == tr)
            t[v].mx = -inf;
      else {
            int tm = (tl + tr) >> 1;
            if (pos <= tm)
                  update (pos,v + v,tl,tm);
            else
                  update (pos,v + v + 1,tm + 1,tr);
            t[v] = merge(t[v + v],t[v + v + 1]);
      }
}
void Update (int pos,int l,int r,int v = 1,int tl = 1,int tr = n) {
      if (tl == tr) {
            t[v].prv = l;
            lst[tl] = t[v].prv;
            t[v].nxt = r;
            nxt[tl] = t[v].nxt;

            t[v].id = tl;
            t[v].mx = (getmax(t[v].prv,tl - 1).mx + getmax(tl + 1,t[v].nxt).mx) - (a[tl] + a[t[v].prv] + a[t[v].nxt]);
      }
      else {
            int tm = (tl + tr) >> 1;
            if (pos <= tm)
                  Update (pos,l,r,v + v,tl,tm);
            else
                  Update (pos,l,r,v + v + 1,tm + 1,tr);
            t[v] = merge(t[v + v],t[v + v + 1]);
      }
}
main () {
      cin >> n;

      for (int i = 1; i <= n; i ++)  {
            cin >> a[i];
            pr[i] = pr[max(0ll,i - 2)] + a[i];

            if (i % 2) od += a[i];
            else ev += a[i];
      }
      prs[n + 1] = 0;
      for (int i = n; i >= 1; i --) {
            prs[i] = prs[min(n + 1,i + 2)] + a[i];
      }

      buildtable();

      a[n + 1] = 0;

      for (int i = 1; i <= n - 1; i ++) {
            if (mx < pr[i - 1] + prs[i + 2])
                  mx = pr[i - 1] + prs[i + 2],ll = i,rr = i + 1;
      }
      if (mx <= od || mx <= ev) {
            if (od > ev || n & 1){
                        res = od;
                        for (int i = 1; i <= n; i ++)
                        if (i % 2 == 0)
                              f[i] = 1;
            }
            else {
                  for (int i = 1; i <= n; i ++)
                        if (i % 2 == 0)
                              f[i] = 1;
                  res = ev;
            }
            build();
      }
      else{
            res = mx;
            for (int i = 1; i < ll; i ++)
                  if (i % 2 != ll % 2)
                        f[i] = 1;
            for (int i = rr + 1; i <= n; i ++)
                  if (i % 2 != rr % 2)
                        f[i] = 1;

            build();
      }

      ans.pb(res);

      lst[0] = 0;
      nxt[n + 1] = n + 1;

      for (int i = (n + 1) / 2 - 1; i >= 1; i --) {
            node c = t[1];
            res += c.mx;

            ans.pb(res);

            int aa = lst[c.prv];
            int bb = c.id;
            int cc = nxt[c.nxt];

            node f = getmax(c.prv,bb - 1);
            node s = getmax(bb + 1,c.nxt);
//
            update (c.id);
            update (c.prv);
            update (c.nxt);

            if (f.id != 0)
                  Update (f.id,aa,s.id);
            if (s.id != 0)
            Update (s.id,f.id,cc);


      }

      reverse(ans.begin(),ans.end());

      for (auto to : ans)
            cout << to << endl;
}

Compilation message (stderr)

candies.cpp:123:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

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