Submission #47856

#	Time	Username	Problem	Language	Result	Execution time	Memory
47856		Talant	Candies (JOI18_candies)	C++17	0 / 100	129 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];

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 c,int v = 1,int tl = 1,int tr = n) {
      if (tl == tr) {
            t[v].prv = max(0ll,tl - 2);
            lst[tl] = t[v].prv;
            t[v].nxt = min(n + 1,tl + 2);
            nxt[tl] = t[v].nxt;

            t[v].id = tl;

            if (c & 1) {
                  if (tl & 1) 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{
                  if (!(tl & 1)) 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(c,v + v,tl,tm);
            build(c,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];
            if (i % 2) od += a[i];
            else ev += a[i];
      }
      buildtable();

      a[n + 1] = 0;

      if (od > ev || n & 1) build(1),res = od;
      else build(0),res = ev;

      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:118:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

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