#include <iostream>
#include <vector>
using namespace std;
const int stala=262144;
long long tree[5*stala];
long long tree2[5*stala];
long long Tree[5*stala];
long long Tree2[5*stala];
int index[5*stala];
int index2[5*stala];
int maks_index=0;
vector<pair<int,long long> >poczatek[stala]; //czas wartosc
vector<pair<int,long long> >koniec[stala]; //czas wartosc
vector<int>wyjscie;
void update_max(int index,int index2,long long war,long long w[],long long W[],int ind[])
{
index=index+stala-1;
index2=index2+stala-1;
w[index]+=war;
if(index!=index2)
{
w[index2]+=war;
}
while(index>0)
{
if(index/2!=index2/2)
{
if(index%2==0)
{
w[index+1]+=war;
W[index+1]=w[index+1]+max(W[2*(index+1)],W[(2*(index+1))+1]);
if(index<stala)
{
ind[index+1]=(W[2*(index+1)]>W[(2*(index+1))+1]) ? ind[2*(index+1)]:ind[(2*(index+1))+1];
}
}
if(index2%2==1)
{
w[index2-1]+=war;
W[index2-1]=w[index2-1]+max(W[2*(index2-1)],W[(2*(index2-1))+1]);
if(index2<stala)
{
ind[index2-1]=(W[2*(index2-1)]>W[(2*(index2-1))+1]) ? ind[2*(index2-1)]:ind[(2*(index2-1))+1];
}
}
}
W[index]=w[index]+max(W[2*index],W[(2*index)+1]);
W[index2]=w[index2]+max(W[2*index2],W[(2*index2)+1]);
if(index<stala)
{
ind[index]=(W[2*index]>W[(2*index)+1]) ? ind[2*index]:ind[(2*index)+1];
}
if(index2<stala)
{
ind[index2]=(W[2*index2]>W[(2*index2)+1]) ? ind[2*index2]:ind[(2*index2)+1];
}
index=index/2;
index2=index2/2;
}
}
long long query_max(int index,int index2,long long w[],long long W[],int ind[])
{
maks_index=0;
index=index+stala-1;
index2=index2+stala-1;
if(index==0)
{
return 0;
}
long long resp=0;
long long resl=0;
int indp=ind[index2];
int indl=ind[index];
while(index>0)
{
resl+=w[index];
resp+=w[index2];
if((index/2)!=(index2/2))
{
if(index%2==0)
{
indl=(resl>W[index+1]) ? indl:ind[index+1];
resl=max(resl,W[index+1]);
}
if(index2%2==1)
{
indp=(resp>W[index2-1]) ? indp:ind[index2-1];
resp=max(resp,W[index2-1]);
}
}
index=index/2;
index2=index2/2;
}
maks_index=(resp>resl) ? indp:indl;
return max(resp,resl);
}
void update_min(int index,int index2,long long war,long long w[],long long W[],int ind[])
{
index=index+stala-1;
index2=index2+stala-1;
w[index]+=war;
if(index!=index2)
{
w[index2]+=war;
}
while(index>0)
{
if(index/2!=index2/2)
{
if(index%2==0)
{
w[index+1]+=war;
W[index+1]=w[index+1]+min(W[2*(index+1)],W[(2*(index+1))+1]);
if(index<stala)
{
ind[index+1]=(W[2*(index+1)]<W[(2*(index+1))+1]) ? ind[2*(index+1)]:ind[(2*(index+1))+1];
}
}
if(index2%2==1)
{
w[index2-1]+=war;
W[index2-1]=w[index2-1]+min(W[2*(index2-1)],W[(2*(index2-1))+1]);
if(index2<stala)
{
ind[index2-1]=(W[2*(index2-1)]<W[(2*(index2-1))+1]) ? ind[2*(index2-1)]:ind[(2*(index2-1))+1];
}
}
}
W[index]=w[index]+min(W[2*index],W[(2*index)+1]);
W[index2]=w[index2]+min(W[2*index2],W[(2*index2)+1]);
if(index<stala)
{
ind[index]=(W[2*index]<W[(2*index)+1]) ? ind[2*index]:ind[(2*index)+1];
}
if(index2<stala)
{
ind[index2]=(W[2*index2]<W[(2*index2)+1]) ? ind[2*index2]:ind[(2*index2)+1];
}
index=index/2;
index2=index2/2;
}
}
long long query_min(int index,int index2,long long w[],long long W[],int ind[])
{
maks_index=0;
index=index+stala-1;
index2=index2+stala-1;
long long resp=0;
long long resl=0;
int indp=ind[index2];
int indl=ind[index];
while(index>0)
{
resl+=w[index];
resp+=w[index2];
if((index/2)!=(index2/2))
{
if(index%2==0)
{
indl=(resl<W[index+1]) ? indl:ind[index+1];
resl=min(resl,W[index+1]);
}
if(index2%2==1)
{
indp=(resp<W[index2-1]) ? indp:ind[index2-1];
resp=min(resp,W[index2-1]);
}
}
index=index/2;
index2=index2/2;
}
maks_index=(resp<resl) ? indp:indl;
return min(resp,resl);
}
void pre()
{
for(int i=stala;i<2*stala;i++)
{
index[i]=i-stala+1;
index2[i]=i-stala+1;
}
for(int i=stala-1;i>=1;i--)
{
index[i]=index[2*i];
index2[i]=index2[2*i];
}
}
vector<int>distribute_candies(vector<int>c,vector<int>l,vector<int>r,vector<int>v)
{
pre();
int czas=(int)l.size();
for(int i=0; i<(int)l.size(); i++)
{
poczatek[l[i]].push_back(make_pair(i+1,v[i]));
koniec[r[i]].push_back(make_pair(i+1,-v[i]));
}
for(int i=0; i<(int)c.size(); i++)
{
for(int j=0; j<(int)poczatek[i].size(); j++)
{
update_max(poczatek[i][j].first,czas,poczatek[i][j].second,tree,Tree,index);
update_min(poczatek[i][j].first,czas,poczatek[i][j].second,tree2,Tree2,index2);
}
int pocz=1;
int kon=czas;
while (pocz < kon)
{
int srodek = (pocz + kon) / 2;
if (query_max(srodek,czas,tree,Tree,index)-query_min(srodek,czas,tree2,Tree2,index2)<=c[i])
kon = srodek;
else
pocz = srodek + 1;
}
query_min(pocz,czas,tree2,Tree2,index2);
long long in=maks_index;
query_max(pocz,czas,tree,Tree,index);
long long in2=maks_index;
if(in<in2)
{
in=query_min(in,in,tree2,Tree2,index2);
}
else if(in==in2&&query_max(in-1,in-1,tree,Tree,index)>query_max(in,in,tree,Tree,index))
{
in=query_min(in,in,tree2,Tree2,index2);
}
else
{
in=query_max(in2,in2,tree,Tree,index)-c[i];
}
long long pom=query_max(czas,czas,tree,Tree,index);
wyjscie.push_back(pom-in);
for(int j=0; j<(int)koniec[i].size(); j++)
{
update_max(koniec[i][j].first,czas,koniec[i][j].second,tree,Tree,index);
update_min(koniec[i][j].first,czas,koniec[i][j].second,tree2,Tree2,index2);
}
}
return wyjscie;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
16844 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
16816 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1059 ms |
52700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
16828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
16844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
16844 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
16816 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
