#include "candies.h"
//
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long
using namespace std;
const int maxn=2e5+100,LOG=17,mod=1e9+7;
int block = 226, timer = 0;
const ld EPS = 1e-18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define bt(i) (1 << (i))
//#define int ll
const int inf=2e9;
#define y1 yy
#define prev pre
#define pii pair <int, int>
ll pu[4*maxn];
ll tmx1[4*maxn], tmn1[4*maxn], tmx2[4*maxn], tmn2[4*maxn];
void update(int v)
{
int v1 = v * 2;
int v2 = v * 2 + 1;
if(tmx1[v1] > tmx1[v2])
{
tmx1[v] = tmx1[v1];
tmx2[v] = max(tmx1[v2], tmx2[v1]);
}
else
if(tmx1[v1] < tmx1[v2])
{
tmx1[v] = tmx1[v2];
tmx2[v] = max(tmx2[v2], tmx1[v1]);
}
else
{
tmx1[v] = tmx1[v1];
tmx2[v] = max(tmx2[v1], tmx2[v2]);
}
if(tmn1[v1] < tmn1[v2])
{
tmn1[v] = tmn1[v1];
tmn2[v] = min(tmn1[v2], tmn2[v1]);
}
else
if(tmn1[v1] > tmn1[v2])
{
tmn1[v] = tmn1[v2];
tmn2[v] = min(tmn1[v1], tmn2[v2]);
}
else
{
tmn1[v] = tmn1[v1];
tmn2[v] = min(tmn2[v1], tmn2[v2]);
}
}
void build(int v, int tl, int tr)
{
if(tl == tr)
{
tmx1[v] = 0;
tmx2[v] = -inf;
tmn1[v] = 0;
tmn2[v] = inf;
return;
}
build(v * 2, tl, (tl + tr) / 2);
build(v * 2 + 1, (tl + tr) / 2 + 1, tr);
update(v);
}
void pushadd(int v, int tl, int tr, ll val)
{
tmx1[v] += val;
if(tmx2[v] != -inf) tmx2[v] += val;
tmn1[v] += val;
if(tmn2[v] != inf) tmn2[v] += val;
pu[v] += val;
}
void pushmx(int v, int tl, int tr, int val)
{
if(val <= tmn1[v]) return;
tmn1[v] = val;
if(tl == tr) tmx1[v] = val;
else
if(tmx1[v] <= val)
{
tmx1[v] = val;
}
else if(tmx2[v] < val)
{
tmx2[v] = val;
}
}
void pushmn(int v, int tl, int tr, int val)
{
if(tmx1[v] <= val) return;
tmx1[v] = val;
if(tl == tr) tmn1[v] = val;
else
if(tmn1[v] >= val)
{
tmn1[v] = val;
}
else if(tmn2[v] > val)
{
tmn2[v] = val;
}
}
void push(int v, int tl, int tr)
{
int tm = (tl + tr) / 2;
pushadd(v * 2, tl, tm, pu[v]);
pushadd(v * 2 + 1, tm+1, tr, pu[v]);
pu[v] = 0;
pushmx(v * 2, tl, tm, tmn1[v]);
pushmx(v * 2 + 1, tm+1, tr, tmn1[v]);
pushmn(v * 2, tl, tm, tmx1[v]);
pushmn(v * 2 + 1, tm+1, tr, tmx1[v]);
}
void upd(int v, int tl, int tr, int l, int r, ll val)
{
if(l > tr || r < tl) return;
if(l <= tl && tr <= r)
{
pushadd(v, tl, tr, val);
return;
}
push(v, tl, tr);
upd(v * 2, tl, (tl + tr) / 2, l, r, val);
upd(v * 2 + 1, (tl + tr) / 2 + 1, tr, l, r, val);
update(v);
}
void updmn(int v, int tl, int tr, int l, int r, int val)
{
if(l > tr || r < tl || tmx1[v] <= val) return;
if(l <= tl && tr <= r && tmx1[v] > val && tmx2[v] <= val)
{
pushmn(v, tl, tr, val);
return;
}
push(v, tl, tr);
updmn(v * 2, tl, (tl + tr) / 2, l, r, val);
updmn(v * 2 + 1, (tl + tr) / 2 + 1, tr, l, r, val);
update(v);
}
void updmx(int v, int tl, int tr, int l, int r, int val)
{
if(l > tr || r < tl || tmn1[v] >= val) return;
if(l <= tl && tr <= r && tmn1[v] < val && tmn2[v] >= val)
{
pushmx(v, tl, tr, val);
return;
}
push(v, tl, tr);
updmx(v * 2, tl, (tl + tr) / 2, l, r, val);
updmx(v * 2 + 1, (tl + tr) / 2 + 1, tr, l, r, val);
update(v);
}
int get(int v, int tl, int tr, int pos)
{
if(tl == tr)
{
return tmn1[v];
}
push(v, tl, tr);
if(pos <= (tl + tr) / 2)
return get(v * 2, tl, (tl + tr) / 2, pos);
return get(v * 2 + 1, (tl + tr) / 2 + 1, tr, pos);
}
vector <int> distribute_candies(vector <int> c, vector <int> l, vector <int> r, vector <int> v)
{
int n = c.size();
int q = v.size();
vector <int> a;
a.assign(n, 0);
build(1, 0, n-1);
FOR(0, it, q)
{
upd(1, 0, n-1, l[it], r[it], v[it]);
updmn(1, 0, n-1, l[it], r[it], c[0]);
updmx(1, 0, n-1, l[it], r[it], 0);
/* cout << "AFTER " << it << endl;
forn(0, j, n-1)
{
cout << get(1, 0, n-1, j) << " ";
}
cout << endl;*/
}
forn(0, i, n-1)
{
a[i] = get(1, 0, n-1, i);
}
return a;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
748 ms |
32768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
168 ms |
8236 KB |
Output is correct |
| 3 |
Correct |
127 ms |
26564 KB |
Output is correct |
| 4 |
Correct |
545 ms |
33844 KB |
Output is correct |
| 5 |
Correct |
558 ms |
34256 KB |
Output is correct |
| 6 |
Correct |
804 ms |
34540 KB |
Output is correct |
| 7 |
Correct |
727 ms |
33960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
