Submission #1246629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246629		bleahbleah	Distributing Candies (IOI21_candies)	C++20	3 / 100	5090 ms	22592 KiB

candies

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

const int qmax = 2e5 + 5;
const int nmax = 2e5 + 5;

namespace DS {
   int v[qmax];
   int Q;
   void upd(int p, int x) {
      v[p] += x;
   }
   
   int solve(int C) {
      int p = -1, mn = 0;
      int sum = 0;
      for(int i = 0; i < Q; i++) {
         sum += v[i];
         if(sum <= mn) mn = sum, p = i;
      }
      vector<int> a, bad, nxtbad;
      a.emplace_back(0);
      for(int i = p + 1; i < Q; i++) a.emplace_back(a.back() + v[i]);
      vector<int> mx;
      mx.emplace_back(0);
      for(auto x : a | views::reverse) mx.emplace_back(max(mx.back(), x));
      reverse(all(mx));
      
      bad.assign(sz(a), 0);
      nxtbad.assign(sz(a), 0);
      
      mn = a.back();
      for(int i = sz(a) - 1; i >= 0; i--) {
         mn = min(mn, a[i]);
         if(mn == a[i]) bad[i] = 1, nxtbad[i] = mn;
         else nxtbad[i] = nxtbad[i + 1];
      }
      int rez = a.back();
      for(int i = 0; i < sz(a); i++) {
         if(bad[i]) mn = a[i];
         if(mx[i] >= C) rez = min(rez, a.back() - min(mx[i] - C, nxtbad[i]));
         else break;
      }
      return max(rez, 0);
   }
   
}

vector<pii> opers[nmax];

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
   DS::Q = sz(l);
   for(int i = 0; i < sz(l); i++) {
      opers[l[i]].emplace_back(i, v[i]);
      opers[r[i] + 1].emplace_back(i, -v[i]);
   }
   
   vector<int> rez;
   for(int i = 0; i < sz(c); i++) {
      for(auto [p, x] : opers[i]) DS::upd(p, x);
      rez.emplace_back(DS::solve(c[i]));
   }
   
   return rez;
}
                                    
/**
vreau sa ma tai   
--
*/ 

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