| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1049011 | amine_aroua | Distributing Candies (IOI21_candies) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "candies.h"
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
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].mx <= M)
{
return;
}
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].mn >= 0)
{
return ;
}
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);
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], c[i]);
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();
if(n <= 2000 && (int)l.size() <= 2000)
{
return brute(c , l , r , v);
}
M = *max_element(c.begin() , c.end());
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] = min(c[i] , get(i));
}
return ret;
}
void randomly()
{
int n , q;
n = rand()%5 + 1;
q = rand()%5 + 1;
vector<int> c(n);
int m = rand()%100;
for(int i = 0 ; i <n ; i++)
{
c[i] = m;
}
vector<int> L , R , V;
for (int i = 0 ; i < q ;i++)
{
int l , r , v;
l = rand()%n;
r = rand()%(n - l) + l;
v = rand()%200 - 100;
L.push_back(l) , R.push_back(r) , V.push_back(v);
}
vector<int> ret =distribute_candies(c , L , R , V);
if(ret != brute(c , L , R , V))
{
cout<<n<<'\n';
cout<<m<<'\n';
cout<<q<<'\n';
for(int i = 0 ; i < q ; i++)
{
cout<<L[i]<<" "<<R[i]<<" "<<V[i]<<'\n';
}
for(int i = 0 ; i < n ; i++)
{
cout<<ret[i]<<' ';
}
exit(0);
}
assert(ret == brute(c , L ,R , V));
cout<<"pass\n";
}
void tle()
{
int n , q;
n = 200000;
q = n;
vector<int> c(n);
int m = rand()%1000000000 + 1;
for(int i = 0 ; i <n ; i++)
{
c[i] = m;
}
vector<int> L , R , V;
for (int i = 0 ; i < q ;i++)
{
int l , r , v;
l = rand()%n;
r = rand()%(n - l) + l;
v = rand()%200 - 100;
L.push_back(l) , R.push_back(r) , V.push_back(v);
}
distribute_candies(c, L , R , V);
cout<<"pass\n";
}
void input()
{
int n , q;
cin>>n;
vector<int> c(n);
for(int i = 0 ; i <n ; i++)
cin>>c[i];
cin>>q;
vector<int> L , R , V;
for (int i = 0 ; i < q ;i++)
{
int l , r , v;
cin>>l>>r>>v;
L.push_back(l) , R.push_back(r) , V.push_back(v);
}
vector<int> ret =distribute_candies(c , L , R , V);
assert(ret == brute(c , L ,R , V));
}
int main()
{
tle();
}