제출 #1014686

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1014686		bleahbleah	사탕 분배 (IOI21_candies)	C++17	40 / 100	531 ms	70776 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

//#ifndef DLOCAL
//   #define cin fin
//   #define cout fout
//   ifstream cin(".in");
//   ofstream cout(".out");
//#endif

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 = 2 * node + 1, R = node * 2;
      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 = 1e15 + 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);
         //cerr << p << ' ' << p << '\t' << v << '\n';
      }
      
      int target_bar = c[i];
      int lastinterest = -1, lastmin = 0;
      operational.walk([&](FirstUnit& a, int cl, int cr) {
         if(cr <= lastinterest) return 0;
         int R = a.mx - lastmin, L = a.mx - a.rightmn;
         //cerr << "\t\t" << cl << ' ' << cr << '\t' << a.mx << ' ' << a.rightmn << ' ' << a.rightP << '\t' << L << ' ' << R << '\n';
         if(L > target_bar || L >= R) {
            //cerr << "\t\t\t\t\tdobre\n";
            lastinterest = a.rightP;
            lastmin = a.rightmn;
            //cerr << a.rightP << ' ' << a.rightmn << '\n';
            return (cl != cr? 1 : 0);
         }
         else {
            return 0;
         }
      });
      
      int sum = 0, mx = -inf;
      operational.walk([&](FirstUnit& a, int cl, int cr) {
         //cerr << '\t' << cl << ' ' << cr << '\n';
         mx = max(mx, a.mx);
         sum += a.sum;
         return 0;
      }, lastinterest + 1, q - 1);
      rez.emplace_back(sum - max(0ll, mx - target_bar - lastmin));
      
   }
   
   return rez;
}

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

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

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 0 / 27
• Subtask 4: 29 / 29
• Subtask 5: 0 / 33