| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 705805 | ToroTN | 사탕 분배 (IOI21_candies) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#include "candies.h"
#include "grader.cpp"
#define pb push_back
#define X first
#define Y second
int mx[800005],mn[800005],lz[800005];
vector<pair<int,int> > sweep[200005]; // pair (index of commands, updated value)
vector<int> ans;
void uptlz(int tree,int st,int ed)
{
mx[tree]+=lz[tree],mn[tree]+=lz[tree];
if(st!=ed)
{
lz[2*tree]+=lz[tree],lz[2*tree+1]+=lz[tree];
}
lz[tree]=0;
}
void update(int tree,int st,int ed,int l,int r,int val)
{
int md=(st+ed)/2;
if(st>=l&&ed<=r)
{
lz[tree]+=val;
}
uptlz(tree,st,ed);
if(st>r||ed<l)return;
if(st>=l&&ed<=r)return;
update(2*tree,st,md,l,r,val);
update(2*tree+1,md+1,ed,l,r,val);
mx[tree]=max(mx[2*tree],mx[2*tree+1]);
mn[tree]=min(mn[2*tree],mn[2*tree+1]);
}
pair<int,int> query(int tree,int st,int ed,int l,int r)
{
int md=(st+ed)/2;
uptlz(tree,st,ed);
if(st>r||ed<l)return {-1e9,1e9};
if(st>=l&&ed<=r)return {mx[tree],mn[tree]};
return {max(query(2*tree,st,md,l,r).X,query(2*tree+1,md+1,ed,l,r).X),min(query(2*tree,st,md,l,r).Y,query(2*tree+1,md+1,ed,l,r).Y)};
}
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=v.size();
for(int i=0;i<m;i++)
{
sweep[l[i]+1].pb({i+1,v[i]});
sweep[r[i]+2].pb({i+1,-v[i]});
}
/*for(int i=1;i<=n;i++)
{
printf("%d\n",i);
for(int j=0;j<sweep[i].size();j++)
{
printf("%d %d\n",sweep[i][j].X,sweep[i][j].Y);
}
printf("\n");
}*/
for(int i=1;i<=n;i++)
{
for(int j=0;j<sweep[i].size();j++)
{
int cmd=sweep[i][j].X,flag=sweep[i][j].Y;
update(1,1,m,cmd,m,flag);
}
int st=0,md,ed=m;
while(ed>=st)
{
md=(st+ed)/2;
int diff;
if(md==0)
{
diff=query(1,1,m,1,m).X;
}else
{
diff=query(1,1,m,md,m).X-query(1,1,m,md,m).Y;
}
if(diff>c[i-1])
{
st=md+1;
}else
{
ed=md-1;
}
}
int fn=query(1,1,m,m,m).X;//final point
int l1,r1,l2,r2,base;
if(ed==-1)
{
ans.pb(fn);
}else
{
if(ed==0)
{
l1=0;
r1=query(1,1,m,1,m).X;
}else
{
l1=query(1,1,m,ed,m).Y;
r1=query(1,1,m,ed,m).X;
}
l2=query(1,1,m,ed+1,m).Y;
r2=query(1,1,m,ed+1,m).X;
if(l1==l2)
{
base=l1;
}else
{
base=r1-c[i-1];
}
ans.pb(fn-base);
}
}
return ans;
}