#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
int M;
const int BASE = (1<<18);
#define lc(x) (x<<1)
#define rc(x) (x<<1 | 1)
struct Node
{
int set , mn , mx , lz;
Node()
{
set = -1 , mn = 0 , mx = 0 , lz = 0;
}
};
vector<Node> tree(2*BASE , Node());
Node add(Node node , int x)
{
node.lz+=x;
node.mx+=x;
node.mn+=x;
return node;
}
Node apply(Node node, int x)
{
node.lz = 0;
node.mx = x;
node.mn = x;
node.set = x;
return node;
}
void propagate(int node)
{
if(tree[node].set != -1)
{
tree[lc(node)] = apply(tree[lc(node)] , tree[node].set);
tree[rc(node)] = apply(tree[rc(node)] , tree[node].set);
tree[node].set = -1;
}
if(tree[node].lz)
{
tree[lc(node)] = add(tree[lc(node)] , tree[node].lz);
tree[rc(node)] = add(tree[rc(node)] , tree[node].lz);
tree[node].lz = 0;
}
}
void upd(int node , int s , int e , int l , int r , int v)
{
if(s > r || l > e)
{
return;
}
if(l <= s && e <= r)
{
tree[node] = add(tree[node] , v);
return;
}
int mid = (s + e)>>1;
propagate(node);
upd(lc(node) , s , mid , l , r , v);
upd(rc(node) , mid + 1 , e , l , r , v);
tree[node].mn = min(tree[lc(node)].mn , tree[rc(node)].mn);
tree[node].mx = max(tree[lc(node)].mx , tree[rc(node)].mx);
}
void upd(int l , int r , int v)
{
upd(1 , 0 , BASE - 1 , l , r , v);
}
void minimize(int node , int s , int e)
{
if(tree[node].mn >= M)
{
tree[node] = apply(tree[node] , M);
return ;
}
if(s == e)
return ;
int m = (s + e)>>1;
propagate(node);
minimize(lc(node) , s , m);
minimize(rc(node) , m + 1 , e);
tree[node].mn = min(tree[lc(node)].mn , tree[rc(node)].mn);
tree[node].mx = max(tree[lc(node)].mx , tree[rc(node)].mx);
}
void maximize(int node , int s , int e)
{
if(tree[node].mx <= 0)
{
tree[node] = apply(tree[node] , 0);
return ;
}
if(s == e)
return ;
int m = (s + e)>>1;
propagate(node);
maximize(lc(node) , s , m);
maximize(rc(node) , m + 1 , e);
tree[node].mn = min(tree[lc(node)].mn , tree[rc(node)].mn);
tree[node].mx = max(tree[lc(node)].mx , tree[rc(node)].mx);
}
int get(int node, int s , int e , int i)
{
if(s == e)
{
assert(tree[node].mn == tree[node].mx);
return tree[node].mn;
}
int mid = (s + e)>>1;
propagate(node);
if(i <= mid)
{
return get(lc(node) , s , mid , i);
}
else
return get(rc(node) , mid + 1 , e , i);
}
int get(int i)
{
return get(1 , 0 , BASE - 1 , i);
}
vector<int> brute(vector<int> c , vector<int> l , vector<int> r ,vector<int>v)
{
int n = (int)c.size();
int q = (int)l.size();
vector<int> ret(n);
M = c[0];
for(int j = 0 ; j < q ; j++)
{
for(int i = l[j] ; i <= r[j] ; i++)
{
ret[i]+=v[j];
ret[i] = min(ret[i], M);
ret[i] = max(ret[i] , 0);
}
}
return ret;
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v) {
int n = c.size();
M = c[0];
int q = (int)l.size();
for(int i = 0 ; i < q ; i++)
{
upd(l[i] , r[i] , v[i]);
if(v[i] > 0)
{
minimize(1 , 0 , BASE - 1);
}
else
maximize(1 , 0 , BASE - 1);
}
vector<int> ret(n);
for(int i = 0 ;i < n ; i++)
{
ret[i] = get(i);
}
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
8540 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
8536 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5064 ms |
14676 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8540 KB |
Output is correct |
| 2 |
Execution timed out |
5066 ms |
15888 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
8540 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
8536 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
