제출 #1087090

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1087090		ezluci	Feast (NOI19_feast)	C++17	100 / 100	86 ms	40320 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).
*/


class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;

	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}

public:
	InParser(FILE *stream) {
		fin = stream;
		buff = new char[4096]();
		sp = 4095;
	}
	
	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};

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];

alexaint Q; ll a, b, c;
inline alexaint combinemi(alexaint &A, alexaint &B, int st, int dr)
{
   a = sum(st, A.xp);   b = sum(st, B.xp);
   Q.xp = (a<=b ? A.xp : B.xp);
   
   a = sum(B.xs, dr);   b = sum(A.xs, dr);
   Q.xs = (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 (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;

   return Q;
}
inline alexaint combinema(alexaint &A, alexaint &B, int st, int dr)
{
   a = sum(st, A.xp);   b = sum(st, B.xp);
   Q.xp = (a>=b ? A.xp : B.xp);
   
   a = sum(B.xs, dr);   b = sum(A.xs, dr);
   Q.xs = (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 (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);
   aintma[nod] = combinema(aintma[nod*2], aintma[nod*2+1], st, dr);
   aintmi[nod] = combinemi(aintmi[nod*2], aintmi[nod*2+1], st, dr);
}

alexaint ansst, ansdr;  bool minmx;
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--;
   if (minmx)
   {
      for (; qst <= qdr; qst >>= 1, qdr >>= 1)
      {
         if (qst&1)
            ansst = combinemi(ansst, aintmi[qst], QST, (qst+1-(1<<__lg(qst)))*(1<<ainth-__lg(qst))),
            qst++;
         if (!(qdr&1))
            ansdr = combinemi(aintmi[qdr], ansdr, 1 + (qdr-(1<<__lg(qdr)))*(1<<ainth-__lg(qdr)), QDR),
            qdr--;
      }
      return combinemi(ansst, ansdr, QST, QDR);
   }
   else
   {
      for (; qst <= qdr; qst >>= 1, qdr >>= 1)
      {
         if (qst&1)
            ansst = combinema(ansst, aintma[qst], QST, (qst+1-(1<<__lg(qst)))*(1<<ainth-__lg(qst))),
            qst++;
         if (!(qdr&1))
            ansdr = combinema(aintma[qdr], ansdr, 1 + (qdr-(1<<__lg(qdr)))*(1<<ainth-__lg(qdr)), QDR),
            qdr--;
      }
      return combinema(ansst, ansdr, QST, QDR);
   }
}


struct alexmax {
   int fi, se, bfi, bse;
   bool operator<(const alexmax &B) const
      { return sum(bfi,bse) < sum(B.bfi,B.bse); }
};
struct alexmin {
   int fi, se, bfi, bse;
   bool operator<(const alexmin &B) const
      { return sum(bfi,bse) > sum(B.bfi,B.bse); }
};


int main()
{
   EZinit();
   InParser fin(stdin);

   fin >> n >> k;
   for (int i = 1; i <= n; ++i)  fin >> v[i],   sp[i] = sp[i-1] + v[i];

   build();

   ll ans = 0;
   priority_queue<alexmin> ivuse;
   priority_queue<alexmax> ivno;
   minmx = false; auto q = que(1, n);
   if (sum(q.x, q.y) >= 1) ivno.push({1, n, q.x, q.y});
   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;
         Xs = ivuse.top().bfi,   Ys = ivuse.top().bse;
         Ss = sum(Xs,Ys);
      }
      // ce putem pune
      ll Sp = LLONG_MIN;   int xp, yp, Xp, Yp;
      if (!ivno.empty())
      {
         xp = ivno.top().fi,  yp = ivno.top().se;
         Xp = ivno.top().bfi, Yp = ivno.top().bse;
         Sp = sum(Xp,Yp);
      }

      if (Ss != LLONG_MAX && (-Ss > Sp || Sp == LLONG_MIN))
      { // scoatem
         ivuse.pop();
         if (xs != Xs)
         {
            minmx = true; q = que(xs, Xs-1);
            if (sum(q.x, q.y) <= -1)   ivuse.push({xs, Xs-1, q.x, q.y});
         }
         if (ys != Ys)
         {
            minmx = true; q = que(Ys+1, ys);
            if (sum(q.x, q.y) <= -1)   ivuse.push({Ys+1, ys, q.x, q.y});
         }
         minmx = false;  q = que(Xs, Ys);
         if (sum(q.x, q.y) >= 1)   ivno.push({Xs, Ys, q.x, q.y});
         ans += -Ss;
      }
      else if (Sp != LLONG_MIN && (Sp >= -Ss || Ss == LLONG_MAX))
      { // punem
         ivno.pop();
         if (xp != Xp)
         {
            minmx = false; q = que(xp, Xp-1);
            if (sum(q.x, q.y) >= 1) ivno.push({xp, Xp-1, q.x, q.y});
         }
         if (yp != Yp)
         {
            minmx = false; q = que(Yp+1, yp);
            if (sum(q.x, q.y) >= 1) ivno.push({Yp+1, yp, q.x, q.y});
         }
         minmx = true;  q = que(Xp, Yp);
         if (sum(q.x, q.y) <= -1)   ivuse.push({Xp, Yp, q.x, q.y});
         ans += Sp;
      }
      else  break;
   }

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

컴파일 시 표준 에러 (stderr) 메시지

feast.cpp: In function 'void build(int, int, int)':
feast.cpp:116:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  116 |    int mj = st+dr >> 1;
      |             ~~^~~
feast.cpp: In function 'alexaint que(int, int)':
feast.cpp:138:88: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  138 |             ansst = combinemi(ansst, aintmi[qst], QST, (qst+1-(1<<__lg(qst)))*(1<<ainth-__lg(qst))),
      |                                                                                   ~~~~~^~~~~~~~~~
feast.cpp:141:85: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  141 |             ansdr = combinemi(aintmi[qdr], ansdr, 1 + (qdr-(1<<__lg(qdr)))*(1<<ainth-__lg(qdr)), QDR),
      |                                                                                ~~~~~^~~~~~~~~~
feast.cpp:151:88: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  151 |             ansst = combinema(ansst, aintma[qst], QST, (qst+1-(1<<__lg(qst)))*(1<<ainth-__lg(qst))),
      |                                                                                   ~~~~~^~~~~~~~~~
feast.cpp:154:85: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  154 |             ansdr = combinema(aintma[qdr], ansdr, 1 + (qdr-(1<<__lg(qdr)))*(1<<ainth-__lg(qdr)), QDR),
      |                                                                                ~~~~~^~~~~~~~~~
feast.cpp: In member function 'char InParser::read_ch()':
feast.cpp:38:9: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |    fread(buff, 1, 4096, fin);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~

• 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