Submission #1087097

#TimeUsernameProblemLanguageResultExecution timeMemory
1087097ezluciFeast (NOI19_feast)C++17
100 / 100
430 ms38596 KiB
#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 } #pragma GCC optimize("unroll-loops") #pragma GCC optimize("inline") /* 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[min(n,y)]-sp[min(n,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 que(int qst, int qdr) { //cerr<<qst << ' ' << qdr << '\n'; int QST = qst, QDR = qdr; if (qst == qdr) return {qst, qst, qst, qst}; alexaint ansst = {qst, qst, qst, qst}; alexaint ansdr = {qdr, qdr, qdr, qdr}; qst += aintlim-1; qdr += aintlim-1; qst++; qdr--; while (qst <= qdr) { //cerr << qst << ' ' << qdr << '\n'; if (qst%2 == 1) ansst = combine(ansst, aint[qst], QST, (qst+1-(1<<__lg(qst)))*(1<<ainth-__lg(qst))), qst++; if (qdr%2 == 0) ansdr = combine(aint[qdr], ansdr, 1 + (qdr-(1<<__lg(qdr)))*(1<<ainth-__lg(qdr)), QDR), qdr--; qst >>= 1; qdr >>= 1; } //cerr<<'a'; 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(); aint = aintma; minmx = false; //cerr<<aint[524290].x<<' ' << aint[524290].y << '\n'; auto q = que(1,3); //cerr<<q.x<<' ' << q.y << '\n'; 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 = 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; minmx = false; aint = aintma; auto q = que(xp, yp); 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:85:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |    int mj = st+dr >> 1;
      |             ~~^~~
feast.cpp: In function 'alexaint que(int, int)':
feast.cpp:108:81: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  108 |          ansst = combine(ansst, aint[qst], QST, (qst+1-(1<<__lg(qst)))*(1<<ainth-__lg(qst))),
      |                                                                            ~~~~~^~~~~~~~~~
feast.cpp:111:78: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  111 |          ansdr = combine(aint[qdr], ansdr, 1 + (qdr-(1<<__lg(qdr)))*(1<<ainth-__lg(qdr)), QDR),
      |                                                                         ~~~~~^~~~~~~~~~
feast.cpp: In function 'int main()':
feast.cpp:156:9: warning: variable 'q' set but not used [-Wunused-but-set-variable]
  156 |    auto q = que(1,3);
      |         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...