Submission #852498

#	Time	Username	Problem	Language	Result	Execution time	Memory
852498		mychecksedad	OGLEDALA (COI15_ogledala)	C++17	19 / 100	2803 ms	451472 KiB

ogledala

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll double
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define eps 1e-1
#define ep 1e-6
const int N = 12e5+100, M = 1e5+10, K = 22;
 
 void normal(double &x){
  if(abs((double)((long long) x) - x) <= ep) x = (long long) x;
  if(abs((double)((long long) x + 1) - x) <= ep) x = (long long) (x + 1);
}

 
ll m, n, q, a[M];
vector<pair<ll, int>> pref, coi[N];
vector<array<long long, 2>> r;
vector<long long> al, coo(N), co(N);
vector<int> g[N], par[N];
vector<bool> vis(N), pushed(N);
 
int compressed(long long sz){
  return (lower_bound(all(al), sz) - al.begin() + 1);
}
 
/*add something to somewheres prefix*/
void add(int x, ll val, int pos){
  coi[x].pb({(coi[x].empty() ? 0 : coi[x].back().first) + val, pos});
}
 
long long count_val(int d, int d_sz){
  vector<int> used;
  int mn = d, mx = d;
  coo[d]++;
  used.pb(d);
  while(mx > 1){
    int v = g[mx].back();
    if(!vis[v]){
      for(int u: par[v])
        coo[v] += coo[u];
      vis[v] = 1;
      used.pb(v);
    }
    if(mn > 1){
      int vv = g[mn][0];
      if(!vis[vv]){
        for(int u: par[vv]){
          coo[vv] += coo[u];
        }
        vis[vv] = 1;
        used.pb(vv);
      }
      mn = vv;
    }

    mx = v;
  }
  ll ans = coo[d_sz];
  for(auto x: used) vis[x] = coo[x] = 0;
  return ans;
}
 
long long tree(int d, int d_sz, long long pos){
  // cout << d << ' ' << pos << 'g' << '\n';
  if(d == d_sz) return (al[d - 1] + 1) >> 1;
 
  if(g[d].size() == 1){
    return 2;
  }
 
  ll coval = count_val(g[d][0], d_sz);
  // cout << coval << ' ' << d << 'f' << pos << endl;
  if(coval >= pos)
    return tree(g[d][0], d_sz, pos);
  pos -= coval;
  return al[g[d][0] - 1] + 1 + tree(g[d][1], d_sz, pos);
}


void proc(long long len){
  long long mn = len, mx = len;
  while(mx > 0){
    if(mn > 0) al.pb(mn);
    if(mx > 0) al.pb(mx);
    mx >>= 1;
    if(mn & 1) mn >>= 1;
    else mn = (mn>>1) - 1;
  }
}
 
void solve(){
  cin >> m >> n >> q;
  ll last = 1;
  for(int i = 1; i <= n; ++i){
    cin >> a[i];
    if(a[i] - 1 >= last) r.pb({last, a[i] - 1});
    last = a[i] + 1;
  }
  if(last <= m) r.pb({last, m});
 
  int rn = 1;
  for(auto x: r){
    proc(x[1] - x[0] + 1);
  }
 
  /* compressed tree */
  sort(all(al));
  al.erase(unique(all(al)), al.end());
  // assert(al.size() < N);
  for(int i = 1; i <= al.size(); ++i){
    if(al[i - 1] > 1){
      if(al[i - 1] > 2){
        int u = compressed(((al[i - 1] + 1) >> 1) - 1);
        g[i].pb(u);
        par[u].pb(i);
      }
      int u = compressed(al[i - 1] >> 1);
      g[i].pb(u);
      par[u].pb(i);
    }
  }
 
  for(auto x: r){
    int v = compressed(x[1] - x[0] + 1);
    set<int> Q;
    vector<int> used;
 
    Q.insert(v);
    coo[v]++;
 
    while(!Q.empty()){
      auto it = prev(Q.end());
      int v = *it;
      Q.erase(it);
      if(vis[v]) continue;
      
      add(v, coo[v], rn);
      co[v] += coo[v];
      used.pb(v);
      vis[v] = 1;
 
      for(int u: g[v]){
        coo[u] += coo[v];
        Q.insert(u);
      }
    }
 
    for(int x: used) vis[x] = coo[x] = 0;
 
    ++rn;
  }
  
 
  /* prefix build */
 
  vector<pair<ll, ll>> vv;
  for(int i = 1; i <= al.size(); ++i){
    vv.pb({i, co[i]});
  }
  reverse(all(vv));
  pref.pb({0ll, 0});
  for(auto p: vv){
    pref.pb({p.second + pref.back().first, p.first});
  }
  // en;
 
  // for(auto x: coi){
  //   cout << x.first << ':';
  //   for(auto y: x.second) cout << y[0] << ' ' << y[1] << '\n';
  //   en;
  // }
  /* queries*/
  for(;q--;){
    ll b; cin >> b;
    if(b <= n){
      cout << (long long) a[int(b)] << '\n';
      continue;
    }
    b -= n;
    int sz_pos = lower_bound(all(pref), pair<ll, int>{b, 0}) - pref.begin();
    int sz = pref[sz_pos].second;
    b -= pref[sz_pos - 1].first;
    // assert(!coi[sz].empty()); 
    int pos = upper_bound(all(coi[sz]), pair<ll, int>{b, 0}) - coi[sz].begin();
    --pos;
    // assert(pos >= 0);
    if(pos >= 0)
      b -= coi[sz][pos].first;
    int pos_a = coi[sz][pos + 1].second;
    // assert(pos_a <= n);
    // cout << pos_a << '\n';
    // cout << r[pos_a - 1][1] - r[pos_a - 1][0] + 1 << ' ' << sz << ' ' << b << '\n';
    // cout << r[pos_a-1][0] << ' ' << r[pos_a-1][1] << ' ' << sz << ' ' << b << '\n';
    cout << r[pos_a - 1][0] + (long long)(tree(compressed(r[pos_a - 1][1] - r[pos_a - 1][0] + 1), sz, b)) - 1 << '\n';
  }
}
 
 
int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

Compilation message (stderr)

ogledala.cpp: In function 'long long int count_val(int, int)':
ogledala.cpp:64:37: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   64 |   for(auto x: used) vis[x] = coo[x] = 0;
ogledala.cpp: In function 'void solve()':
ogledala.cpp:101:32: warning: narrowing conversion of 'last' from 'double' to 'long long int' [-Wnarrowing]
  101 |     if(a[i] - 1 >= last) r.pb({last, a[i] - 1});
      |                                ^~~~
ogledala.cpp:101:43: warning: narrowing conversion of '(a[i] - (double)1)' from 'double' to 'long long int' [-Wnarrowing]
  101 |     if(a[i] - 1 >= last) r.pb({last, a[i] - 1});
      |                                      ~~~~~^~~
ogledala.cpp:104:23: warning: narrowing conversion of 'last' from 'double' to 'long long int' [-Wnarrowing]
  104 |   if(last <= m) r.pb({last, m});
      |                       ^~~~
ogledala.cpp:104:29: warning: narrowing conversion of 'm' from 'double' to 'long long int' [-Wnarrowing]
  104 |   if(last <= m) r.pb({last, m});
      |                             ^
ogledala.cpp:115:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |   for(int i = 1; i <= al.size(); ++i){
      |                  ~~^~~~~~~~~~~~
ogledala.cpp:153:38: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  153 |     for(int x: used) vis[x] = coo[x] = 0;
ogledala.cpp:162:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |   for(int i = 1; i <= al.size(); ++i){
      |                  ~~^~~~~~~~~~~~
ogledala.cpp: In function 'int main()':
ogledala.cpp:206:15: warning: unused variable 'aa' [-Wunused-variable]
  206 |   int tt = 1, aa;
      |               ^~

• Subtask 1: 19 / 19
• Subtask 2: 0 / 22
• Subtask 3: 0 / 59