oj.uz

Submission #1014708

# Submission time Handle Problem Language Result Execution time Memory
1014708 2024-07-05T10:14:52 Z bleahbleah Distributing Candies (IOI21_candies) C++17
100 / 100
 1229 ms 73436 KB 
#include "candies.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;


template<typename T> 
struct AINT {
   vector<T> aint; int n;
   void init(int n_) {
      n = n_;
      aint.assign(n * 4 + 100, T());
   }
   template<class CB> void walk(CB&& cb) { walk(cb, -2, n - 1); }
   template<class CB> void walk(CB&& cb, int l, int r) { walk(cb, l, r, 1, -2, n - 1); }
   template<class CB> void walk(CB&& cb, int l, int r, int node, int cl, int cr) { 
      if(cr < l || r < cl) return;
      if(l <= cl && cr <= r && !cb(aint[node], cl, cr)) return;
      int mid = (cl + cr) >> 1, L =  node + (cr - mid) * 2, R = node + 1;
      aint[node].push(aint[L], aint[R]);
      walk(cb, l, r, R, mid + 1, cr);
      walk(cb, l, r, L, cl, mid);
      aint[node].pull(aint[L], aint[R]);
   }
};

const ll inf = 1e17 + 5;

int get_mn(int a, int b) {
   return min(a, b);
}

struct FirstUnit {
   int mx, rightmn, rightP;
   int fullmn, fullP;
   int lazy;
   
   int sum;
   
   FirstUnit(int b = 0, int c = 0, int d = 0, int f = 0, int h = 0, int e = 0): mx(b), rightmn(c), rightP(d), fullmn(f), fullP(h), lazy(0), sum(e) {;}
   
   void pull(const FirstUnit& a, const FirstUnit& b) {
      *this = FirstUnit(max(a.mx, b.mx), -1, -1, min(a.fullmn, b.fullmn), -1, a.sum + b.sum);
      if(a.mx >= b.mx) {
         if(a.rightmn < b.fullmn) rightmn = a.rightmn, rightP = a.rightP;
         else rightmn = b.fullmn, rightP = b.fullP;
      }
      else
         rightmn = b.rightmn, rightP = b.rightP;
         
      fullP = a.fullP;
      if(fullmn == b.fullmn) fullP = b.fullP;
      
      
      return;
   }
   void apply(int a) {
      mx += a; rightmn += a; lazy += a; fullmn += a;
   }
   void push(FirstUnit& a, FirstUnit& b) { a.apply(lazy); b.apply(lazy); lazy = 0; }
};

std::vector<signed> distribute_candies(std::vector<signed> c, std::vector<signed> l,
                                    std::vector<signed> r, std::vector<signed> v) {
   
   int n = sz(c), q = sz(l);
   vector<vector<pii>> opers(n + 1);
   for(int i = 0; i < q; i++) opers[l[i]].emplace_back(i, v[i]), opers[r[i] + 1].emplace_back(i, -v[i]);
   
   AINT<FirstUnit> operational;
   operational.init(q);
   operational.walk([&](auto& a, int cl, int cr) { if(cl != cr) return 1; a.rightP = a.fullP = cl; return 0; });
   vector<signed> rez;
   
   operational.walk([&](FirstUnit& a, int cl, int cr) {
         a.apply(inf); return 0;
   }, -2, q - 1);
   operational.walk([&](FirstUnit& a, int cl, int cr) {
         a.sum += inf; return 0;
   }, -2, -2);
   operational.walk([&](FirstUnit& a, int cl, int cr) {
         a.apply(-inf); return 0;
   }, -1, q - 1);
   operational.walk([&](FirstUnit& a, int cl, int cr) {
         a.sum += -inf; return 0;
   }, -1, -1);
   
   for(int i = 0; i < n; i++) {
      for(auto [p, v] : opers[i]) {
         operational.walk([&](FirstUnit& a, int cl, int cr) {
               a.apply(v); return 0;
         }, p, q - 1);
         operational.walk([&](FirstUnit& a, int cl, int cr) {
               a.sum += v; return 0;
         }, p, p);
         //if(abs(p - 4107) <= 2) cerr << " + " << p << ' ' << v  << '\n';
      }
      
      //if(i < 16) continue;
      
      int target_bar = c[i];
      int lastinterest = -1, lastmin = 0;
      operational.walk([&](FirstUnit& a, int cl, int cr) {
         if(cr <= lastinterest) return 0;
         
         int my_rightmn = a.rightmn, rP = a.rightP;
         operational.walk([&](FirstUnit& u, int tt, int tt2) {
            if(my_rightmn > u.fullmn) rP = u.fullP, my_rightmn = u.fullmn; return 0;
         }, cr + 1, q - 1);
         
         int R = a.mx - lastmin, L = a.mx - my_rightmn;
         
         //cerr << cl << ' ' << cr << '\t' << a.mx << ' ' << my_rightmn << ' ' << L << ' ' << R << '\t' << a.fullmn << '\n'
         //;
         
         if(L > target_bar || L > R) {
            lastinterest = rP;
            lastmin = my_rightmn;
            return 1;
         }
         else {
            return 0;
         }
      });
      
      int sum = 0, mx = -inf;
      operational.walk([&](FirstUnit& a, int cl, int cr) {
         mx = max(mx, a.mx);
         sum += a.sum;
         return 0;
      }, lastinterest + 1, q - 1);
      rez.emplace_back(sum - max(0ll, mx - target_bar - lastmin));
      
      
      //cerr << last << ' ' << q - 1 << '\n';
      //cerr << lastinterest << ' ' << lastmin << ' ' << sum << ' '<< mx << ' ' << target_bar << '\n';
      //cerr << A << ' ' << sum - max(0ll, mx - target_bar - lastmin) << '\n';
      //cerr << "-------------\n";
      //if(i >= 18) break;
   }
   
   return rez;

}
//26416 -24803 -7010 68416 90723 60899 85738 25434

//26416 -51219 17793 75426 22307 -29824 24839 -60304
#undef int

Compilation message

candies.cpp: In lambda function:
candies.cpp:117:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  117 |             if(my_rightmn > u.fullmn) rP = u.fullP, my_rightmn = u.fullmn; return 0;
      |             ^~
candies.cpp:117:76: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  117 |             if(my_rightmn > u.fullmn) rP = u.fullP, my_rightmn = u.fullmn; return 0;
      |                                                                            ^~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 856 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 3 ms 1116 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1143 ms 71628 KB Output is correct
2 Correct 1030 ms 70860 KB Output is correct
3 Correct 1229 ms 70732 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 332 ms 60640 KB Output is correct
3 Correct 258 ms 10440 KB Output is correct
4 Correct 786 ms 72752 KB Output is correct
5 Correct 536 ms 72984 KB Output is correct
6 Correct 451 ms 73436 KB Output is correct
7 Correct 469 ms 72904 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 145 ms 58116 KB Output is correct
4 Correct 61 ms 9436 KB Output is correct
5 Correct 279 ms 66740 KB Output is correct
6 Correct 258 ms 67504 KB Output is correct
7 Correct 282 ms 68000 KB Output is correct
8 Correct 256 ms 66736 KB Output is correct
9 Correct 979 ms 68008 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 856 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 3 ms 1116 KB Output is correct
6 Correct 1143 ms 71628 KB Output is correct
7 Correct 1030 ms 70860 KB Output is correct
8 Correct 1229 ms 70732 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 332 ms 60640 KB Output is correct
11 Correct 258 ms 10440 KB Output is correct
12 Correct 786 ms 72752 KB Output is correct
13 Correct 536 ms 72984 KB Output is correct
14 Correct 451 ms 73436 KB Output is correct
15 Correct 469 ms 72904 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 145 ms 58116 KB Output is correct
19 Correct 61 ms 9436 KB Output is correct
20 Correct 279 ms 66740 KB Output is correct
21 Correct 258 ms 67504 KB Output is correct
22 Correct 282 ms 68000 KB Output is correct
23 Correct 256 ms 66736 KB Output is correct
24 Correct 979 ms 68008 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 89 ms 9616 KB Output is correct
27 Correct 307 ms 60460 KB Output is correct
28 Correct 530 ms 71260 KB Output is correct
29 Correct 535 ms 71680 KB Output is correct
30 Correct 497 ms 71884 KB Output is correct
31 Correct 556 ms 72136 KB Output is correct
32 Correct 602 ms 72364 KB Output is correct