oj.uz

Submission #28191

# Submission time Handle Problem Language Result Execution time Memory
28191 2017-07-15T14:31:31 Z samir_droubi OGLEDALA (COI15_ogledala) C++14
100 / 100
 3343 ms 297808 KB 
#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

ogledala.cpp: In function 'long long int query(long long int, long long int, int)':
ogledala.cpp:77:9: warning: statement has no effect [-Wunused-value]
   for(it;it!=dis.end();++it)
         ^
ogledala.cpp: In function 'int main()':
ogledala.cpp:125:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(sm<x&&it+1<v.size())
                     ^
ogledala.cpp:103:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%d%d",&m,&n,&q);
                             ^
ogledala.cpp:105:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&a[i]);
                        ^
ogledala.cpp:118:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&x);
                     ^

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2812 KB Output is correct
2 Correct 0 ms 2812 KB Output is correct
3 Correct 73 ms 5200 KB Output is correct
4 Correct 93 ms 5200 KB Output is correct
5 Correct 99 ms 12112 KB Output is correct
6 Correct 113 ms 12112 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 3180 KB Output is correct
2 Correct 36 ms 3180 KB Output is correct
3 Correct 2273 ms 297808 KB Output is correct
4 Correct 2149 ms 297808 KB Output is correct
5 Correct 2633 ms 297808 KB Output is correct
6 Correct 2463 ms 297808 KB Output is correct

Subtask #3
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 1543 ms 150352 KB Output is correct
2 Correct 1663 ms 150352 KB Output is correct
3 Correct 2409 ms 297808 KB Output is correct
4 Correct 2389 ms 297808 KB Output is correct
5 Correct 3343 ms 297808 KB Output is correct
6 Correct 3283 ms 297808 KB Output is correct