#include "candies.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long
using i64 = long long;
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
const i64 inf = 1e16;
const int N = 2e5 + 5;
//~ {
//~ if ( l > tr or r < tl ){
//~ return inf;
//~ }
//~ if ( l <= tl && tr >= r ){
//~ if ( T[v].mx <= bound ){
//~ return T[v].mn;
//~ }
//~ if ( l == r ) return inf;
//~ int m = (l + r) / 2;
//~ int ret = get(v * 2 + 1, m + 1, r, tl, tr);
//~ if ( T[v * 2 + 1].mx <= bound ){
//~ chmin(ret, get(v * 2, l, m, tl, tr));
//~ }
//~ return ret;
//~ }
//~ }
struct SegTree{
vector <ar<i64,2>> T;
vector <i64> lazy;
int n;
SegTree(int n) : n(n) {
T.resize(N * 4);
lazy.resize(N * 4);
for ( int i = 0; i < N * 4; i++ ){
T[i] = {inf, inf};
lazy[i] = 0;
}
}
void push(int v, int l, int r){
if ( l != r ){
lazy[v * 2] += lazy[v];
lazy[v * 2 + 1] += lazy[v];
}
T[v][0] += lazy[v];
T[v][1] -= lazy[v];
lazy[v] = 0;
}
void upd(int v, int l, int r, int tl, int tr, i64 x){
push(v, l, r);
if ( l > tr or r < tl ) return;
if ( tl <= l && tr >= r ){
lazy[v] += x;
push(v, l, r);
return;
}
int m = (l + r) / 2;
upd(v * 2, l, m, tl, tr, x);
upd(v * 2 + 1, m + 1, r, tl, tr, x);
for ( auto j: {0, 1} ){
T[v][j] = min(T[v * 2][j], T[v * 2 + 1][j]);
}
}
void upd(int l, int r, i64 x){
upd(1, 0, n, l, r, x);
}
void set(int v, int l, int r, int ps, i64 x){
push(v, l, r);
if ( l == r ){
T[v] = {x, -x};
return;
}
int m = (l + r) / 2;
if ( ps <= m ) set(v * 2, l, m, ps, x);
else set(v * 2 + 1, m + 1, r, ps, x);
for ( auto j: {0, 1} ){
T[v][j] = min(T[v * 2][j], T[v * 2 + 1][j]);
}
}
void set(int ps, i64 x){
set(1, 0, n, ps, x);
}
i64 get(int v, int l, int r, int tl, int tr, int j){
push(v, l, r);
if ( l > tr or r < tl ) return inf;
if ( tl <= l && tr >= r ){
return T[v][j];
}
int m = (l + r) / 2;
return min(get(v * 2, l, m, tl, tr, j), get(v * 2 + 1, m + 1, r, tl, tr, j));
}
i64 get(int l, int r, int j){ // 0 - min, 1 - max
return get(1, 0, n, l, r, j) * (!j ? 1 : -1);
}
bool in(i64 l, i64 r, i64 u){ return l <= u && r >= u; }
i64 f(int v, int l, int r, int tl, int tr, i64 L, i64 R, int j){
push(v, l, r);
if ( l > tr or r < tl ) return inf;
int m = (l + r) / 2;
if ( tl <= l && tr >= r ){
if ( !in(L, R, -T[v][1]) || !in(L, R, T[v][0]) ){
return inf;
}
i64 ret = f(v * 2 + 1, m + 1, r, tl, tr, L, R, j);
if ( in(L, R, -T[v * 2 + 1][1]) && in(L, R, T[v * 2 + 1][0]) ){
chmin(ret, f(v * 2, l, m, tl, tr, L, R, j));
}
return ret;
}
//~ not finished
}
};
struct Fenwick{
vector <i64> fn;
int n;
Fenwick(int n) : fn(n + 1, 0), n(n) {}
void upd(int i, int x){
for (; i <= n; i += i & -i ){
fn[i] += x;
}
}
i64 get(int i){
i64 ret = 0;
for (; i > 0; i -= i & -i ){
ret += fn[i];
}
return ret;
}
i64 get(int l, int r){
return get(r) - get(l - 1);
}
};
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int q = l.size(), n = c.size();
vector <vector<int>> H(n + 1);
for ( int i = 0; i < q; i++ ){
H[l[i]].pb(i + 1);
H[r[i] + 1].pb(-(i + 1));
}
vector <int> ans(n);
SegTree seg(q);
for ( int j = 0; j <= q; j++ ){
seg.set(j, 0);
}
i64 pf = 0, mn = 0;
for ( int j = 0; j < q; j++ ){
pf += v[j];
chmin(mn, pf);
}
Fenwick fn(q + 1);
for ( int i = 0; i < n; i++ ){
for ( auto &j: H[i] ){
int u = abs(j);
i64 x = j < 0 ? -v[u - 1] : v[u - 1];
seg.upd(u, q, x);
fn.upd(u, x);
}
auto ok = [&](int m){
i64 mn = seg.get(m, q, 0), mx = seg.get(m, q, 1);
//~ cout << "Min on Seg " << m << " " << q << " -> " << mn << ", " << mx << ln;
if ( mx - mn >= c[i] ){
return true;
}
{ // mx case
int l = 0, r = m;
while ( l < r ){
int x = (l + r) / 2;
if ( seg.get(x, m, 1) > mx ){
l = x + 1;
} else r = x;
}
if ( mx - seg.get(l, m, 0) >= c[i] ){
return true;
}
}
{ // mn case
int l = 0, r = m;
while ( l < r ){
int x = (l + r) / 2;
if ( seg.get(x, m, 0) < mn ){
l = x + 1;
} else r = x;
}
if ( seg.get(l, m, 1) - mn >= c[i] ){
return true;
}
}
return false;
};
//~ for ( int j = 1; j <= q; j++ ){
//~ cout << (fn.get(j, j) != 0) << ' ';
//~ } cout << ln;
int l = 0, r = q + 1;
while ( l + 1 < r ){
int m = (l + r) / 2;
if ( ok(m) ) l = m;
else r = m;
}
//~ cout << i << " -> " << l << ln;
if ( l == 0 ){ // no touch
ans[i] = pf - mn;
} else{
ans[i] = fn.get(r, q);
int t = -1;
for ( int j = l; j > 0; j-- ){
if ( fn.get(j, j) ){
t = (fn.get(j, j) < 0 ? 0 : 1);
break;
}
}
assert(t != -1);
ans[i] += c[i] * t;
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
19036 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
19008 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5033 ms |
40516 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
19036 KB |
Output is correct |
| 2 |
Correct |
4 ms |
19036 KB |
Output is correct |
| 3 |
Correct |
177 ms |
28860 KB |
Output is correct |
| 4 |
Correct |
1410 ms |
27116 KB |
Output is correct |
| 5 |
Execution timed out |
5062 ms |
36364 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
19036 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
19008 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
