# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
28191 | samir_droubi | OGLEDALA (COI15_ogledala) | C++14 | 3343 ms | 297808 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 <bits/stdc++.h>
#define ll long long
using namespace std;
const int mxn=(1e5)+5;
ll m;
int n,q;
ll a[mxn];
struct seg{
ll len;
int i;
ll sz;
};
bool cmp(seg x,seg y)
{
if(x.len==y.len)return x.i<y.i;
return x.len>y.len;
}
vector<seg>v;
map<ll,ll>cnt;
void divide(ll ln,int i)
{
cnt.clear();
++cnt[ln];
while(!cnt.empty())
{
map<ll,ll>::iterator it=cnt.end();
--it;
ll len=it->first;
ll sz=it->second;
seg tmp;
tmp.len=len;
tmp.sz=sz;
tmp.i=i;
v.push_back(tmp);
if(len>1)
{
if(len%2)
cnt[len/2]+=sz*2;
else
{
cnt[len/2]+=sz;
if(len/2 != 1)cnt[len/2 - 1]+=sz;
}
}
cnt.erase(it);
}
}
map<ll,ll>dis;
void dfs(ll v)
{
if(v==1)return;
if(dis.count(v/2)==0)
{
dis[v/2]=0;
dfs(v/2);
}
if(v%2==0)
{
if(v/2==1)return;
if(dis.count(v/2 - 1)==0)
{
dis[v/2 - 1]=0;
dfs(v/2 - 1);
}
}
}
ll query(ll ln,ll x,int i)
{
dis.clear();
ll l=a[i-1]+1;
ll r=a[i]-1;
dfs(r-l+1);
dis[ln]=1;
map<ll,ll>::iterator it=dis.begin();
for(it;it!=dis.end();++it)
{
ll len=it->first;
ll sz=it->second;
if(dis.count(len*2))dis[len*2]+=sz;
if(dis.count(len*2 + 1))dis[len*2 + 1]+=sz*2;
if(dis.count(len*2 + 2))dis[len*2 + 2]+=sz;
}
while(l<=r)
{
ll md=(l+r)/2;
if(r-l+1==ln)return md;
ll vl=dis[md-l];
if(vl<x)
{
x-=vl;
l=md+1;
}
else
r=md-1;
}
return 0;
}
int main()
{
scanf("%lld%d%d",&m,&n,&q);
for(int i=1;i<=n;++i)
scanf("%lld",&a[i]);
a[n+1]=m+1;
for(int i=1;i<=n+1;++i)
{
if(a[i-1]+1<=a[i]-1)
divide(a[i]-a[i-1]-1,i);
}
sort(v.begin(),v.end(),cmp);
int it=-1;
ll sm=0;
for(int i=0;i<q;++i)
{
ll x;
scanf("%lld",&x);
if(x<=n)
{
printf("%lld\n",a[x]);
continue;
}
else x-=n;
while(sm<x&&it+1<v.size())
{
++it;
sm+=v[it].sz;
v[it].sz=sm;
}
ll vl=0;
if(it>0)vl=v[it-1].sz;
printf("%lld\n",query(v[it].len,x-vl,v[it].i));
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |