Submission #1087094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087094		ezluci	Feast (NOI19_feast)	C++17	100 / 100	423 ms	38320 KiB

feast

#ifdef EZ
   #include "./ez/ez.h"
#else
   #include <bits/stdc++.h>
#endif
#define mp make_pair
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
void EZinit() {
   #ifndef EZ
   //cin.tie(0)->sync_with_stdio(0);
   #else
   freopen("test.in", "r", stdin);
   freopen("test.out", "w", stdout);
   #endif
}

/*
vom afla raspunsul secvential: j=1,2,..k secvente. pt j=1 folosim cea mai mare subsecventa initial.
pt a trece de la j-1 la j, ori folosim o noua subsecventa, ori
   spargem o subsecventa deja folosita (scoatem sub-subsecventa de suma MINIMA).
*/

void get(int &x)
{
   static char c;
   static bool neg;
   while (!isdigit(c = getchar_unlocked()) && c != '-');
   if (c == '-')  neg = 1, x = 0;
   else  neg = 0, x = c-'0';
   while (isdigit(c = getchar_unlocked()))   x = x*10 + c-'0';
   if (neg) x *= -1;
}

int n, k;
int v[300001];
ll sp[600001];
#define sum(x,y) (sp[y]-sp[x-1])


struct alexaint {
   int x, y, xp, xs;
};
const int ainth = 19;
const int aintlim = 1<<ainth;
alexaint aintmi[2*aintlim], aintma[2*aintlim];

bool minmx;   alexaint* aint;
inline alexaint combine(alexaint &A, alexaint &B, int st, int dr)
{
   alexaint Q; ll a, b, c;

   a = sum(st, A.xp);   b = sum(st, B.xp);
   Q.xp = (((minmx) ? (a<=b) : (a>=b)) ? A.xp : B.xp);
   
   a = sum(B.xs, dr);   b = sum(A.xs, dr);
   Q.xs = (((minmx) ? (a<=b) : (a>=b)) ? B.xs : A.xs);

   a = sum(A.x, A.y);   b = sum(B.x, B.y);   c = sum(A.xs, B.xp);
   if (minmx)
   {
      if (a <= min(b,c))   Q.x = A.x,  Q.y = A.y;
      else if (b <= min(a,c)) Q.x = B.x,  Q.y = B.y;
      else  Q.x = A.xs, Q.y = B.xp;
   }
   else
   {
      if (a >= max(b,c))   Q.x = A.x,  Q.y = A.y;
      else if (b >= max(a,c)) Q.x = B.x,  Q.y = B.y;
      else  Q.x = A.xs, Q.y = B.xp;
   }

   return Q;
}

void build(int nod = 1, int st = 1, int dr = aintlim)
{
   if (st == dr)  return (void) (aintma[nod] = aintmi[nod] = {st, st, st, st});
   int mj = st+dr >> 1;
   build(nod*2, st, mj);
   build(nod*2+1, mj+1, dr);
   minmx = false;
   aintma[nod] = combine(aintma[nod*2], aintma[nod*2+1], st, dr);
   minmx = true;
   aintmi[nod] = combine(aintmi[nod*2], aintmi[nod*2+1], st, dr);
}

alexaint ansst, ansdr;
inline alexaint que(int qst, int qdr)
{
   int QST = qst, QDR = qdr;
   if (qst == qdr)   return {qst, qst, qst, qst};
   ansst.x = ansst.y = ansst.xp = ansst.xs = qst;
   ansdr.x = ansdr.y = ansdr.xp = ansdr.xs = qdr;
   qst += aintlim-1;
   qdr += aintlim-1;
   qst++;   qdr--;
   for (; qst <= qdr; qst >>= 1, qdr >>= 1)
   {
      if (qst&1)
         ansst = combine(ansst, aint[qst], QST, (qst+1-(1<<__lg(qst)))*(1<<ainth-__lg(qst))),
         qst++;
      if (!(qdr&1))
         ansdr = combine(aint[qdr], ansdr, 1 + (qdr-(1<<__lg(qdr)))*(1<<ainth-__lg(qdr)), QDR),
         qdr--;
   }
   return combine(ansst, ansdr, QST, QDR);
}


struct alexmax {
   int fi, se;
   bool operator<(const alexmax &B) const
   {
      minmx = false; aint = aintma;
      auto Xq = que(fi, se);
      int X1 = Xq.x, X2 = Xq.y;
      auto Yq = que(B.fi, B.se);
      int Y1 = Yq.x, Y2 = Yq.y;
      return sum(X1,X2) < sum(Y1,Y2);
   }
};
struct alexmin {
   int fi, se;
   bool operator<(const alexmin &B) const
   {
      minmx = true; aint = aintmi;
      auto Xq = que(fi, se);
      int X1 = Xq.x, X2 = Xq.y;
      auto Yq = que(B.fi, B.se);
      int Y1 = Yq.x, Y2 = Yq.y;
      return sum(X1,X2) > sum(Y1,Y2);
   }
};


int main()
{
   EZinit();
   
   get(n);  get(k);
   for (int i = 1; i <= n; ++i)  get(v[i]),  sp[i] = sp[i-1] + v[i];

   build();

   ll ans = 0;
   priority_queue<alexmin> ivuse;
   priority_queue<alexmax> ivno;
   ivno.push({1, n});
   for (int j = 1; j <= k; ++j)
   {
      // ce putem scoate
      ll Ss = LLONG_MAX;   int xs, ys, Xs, Ys;
      if (!ivuse.empty())
      {
         xs = ivuse.top().fi, ys = ivuse.top().se;
         minmx = true;  aint = aintmi;
         auto q = que(xs, ys);
         Xs = q.x,   Ys = q.y;
         Ss = sum(Xs,Ys);
         if (-Ss <= 0) ivuse.pop();
      }
      // ce putem pune
      ll Sp = LLONG_MIN;   int xp, yp, Xp, Yp;
      if (!ivno.empty())
      {
         xp = ivno.top().fi, yp = ivno.top().se;
         minmx = false; aint = aintma;
         auto q = que(xp, yp);
         Xp = q.x,   Yp = q.y;
         Sp = sum(Xp,Yp);
         if (Sp <= 0)  ivno.pop();
      }
      if (Ss != LLONG_MAX && -Ss >= 1 && (-Ss > Sp || Sp == LLONG_MIN))
      { // scoatem
         ivuse.pop();
         if (xs != Xs)  ivuse.push({xs,Xs-1});
         if (ys != Ys)  ivuse.push({Ys+1, ys});
         ivno.push({Xs,Ys});
         ans += -Ss;
      }
      if (Sp != LLONG_MIN && Sp >= 1 && (Sp >= -Ss || Ss == LLONG_MAX))
      { // punem
         ivno.pop();
         if (xp != Xp)  ivno.push({xp,Xp-1});
         if (yp != Yp)  ivno.push({Yp+1, yp});
         ivuse.push({Xp,Yp});
         ans += Sp;
      }
   }

   cout << ans << '\n';
}

Compilation message (stderr)

feast.cpp: In function 'void build(int, int, int)':
feast.cpp:82:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |    int mj = st+dr >> 1;
      |             ~~^~~
feast.cpp: In function 'alexaint que(int, int)':
feast.cpp:104:81: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  104 |          ansst = combine(ansst, aint[qst], QST, (qst+1-(1<<__lg(qst)))*(1<<ainth-__lg(qst))),
      |                                                                            ~~~~~^~~~~~~~~~
feast.cpp:107:78: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  107 |          ansdr = combine(aint[qdr], ansdr, 1 + (qdr-(1<<__lg(qdr)))*(1<<ainth-__lg(qdr)), QDR),
      |                                                                         ~~~~~^~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29