Submission #1087095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087095		ezluci	Feast (NOI19_feast)	C++17	71 / 100	1025 ms	38384 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[300001];
#define sum(x,y) (sp[y]-sp[x-1])


struct alexaint {
   int x, y, xp, xs;
};
alexaint aintmi[1200001], aintma[1200001];

alexaint combine(alexaint A, alexaint B, int st, int dr, bool minmax)
{
   alexaint Q; ll a, b, c;

   a = sum(st, A.xp);   b = sum(st, B.xp);
   Q.xp = (((minmax) ? (a<=b) : (a>=b)) ? A.xp : B.xp);
   
   a = sum(B.xs, dr);   b = sum(A.xs, dr);
   Q.xs = (((minmax) ? (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 (minmax)
   {
      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 = n)
{
   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);
   aintma[nod] = combine(aintma[nod*2], aintma[nod*2+1], st, dr, false);
   aintmi[nod] = combine(aintmi[nod*2], aintmi[nod*2+1], st, dr, true);
}

alexaint que(int qst, int qdr, bool minmax, alexaint aint[], int nod = 1, int st = 1, int dr = n)
{
   if (qst <= st && dr <= qdr)   return aint[nod];
   
   int mj = st+dr >> 1;
   if (qst <= mj && mj < qdr)
   {
      alexaint q1 = que(qst, qdr, minmax, aint, nod*2, st, mj);
      alexaint q2 = que(qst, qdr, minmax, aint, nod*2+1, mj+1, dr);
      return combine(q1, q2, qst, qdr, minmax);
   }
   else if (qst <= mj)  return que(qst, qdr, minmax, aint, nod*2, st, mj);
   else  return que(qst, qdr, minmax, aint, nod*2+1, mj+1, dr);
}


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


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;
         auto q = que(xs, ys, true, aintmi);
         Xs = q.x,   Ys = q.y;
         Ss = sp[Ys]-sp[Xs-1];
         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;
         auto q = que(xp, yp, false, aintma);
         Xp = q.x,   Yp = q.y;
         Sp = sp[Yp]-sp[Xp-1];
         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:79:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |    int mj = st+dr >> 1;
      |             ~~^~~
feast.cpp: In function 'alexaint que(int, int, bool, alexaint*, int, int, int)':
feast.cpp:90:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |    int mj = st+dr >> 1;
      |             ~~^~~

• 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: 0 / 29