Submission #852431

#	Time	Username	Problem	Language	Result	Execution time	Memory
852431		mychecksedad	OGLEDALA (COI15_ogledala)	C++17	19 / 100	3480 ms	524288 KiB

ogledala

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 225e4+100, M = 1e5+10, K = 22;


ll m, n, q, a[M];
vector<tuple<ll, int>> pref, coi[N];
vector<array<ll, 2>> r;
vector<ll> al, coo(N), co(N);
vector<int> g[N];
vector<bool> vis(N);

int compressed(ll sz){
  return (lower_bound(all(al), sz) - al.begin() + 1);
}

/*add something to somewheres prefix*/
void add(ll x, ll val, ll pos){
  if(coi[x].empty()) coi[x].pb({0, 0});
  coi[x].pb({get<0>(coi[x].back()) + val, pos});
}

ll count_val(int d, int d_sz){
  vector<int> used;
  priority_queue<int> Q;
  Q.push(d);
  coo[d]++;
  while(!Q.empty()){
    int v = Q.top();
    Q.pop();
    if(vis[v]) continue;
    vis[v] = 1;
    used.pb(v);
    for(int u: g[v]){
      coo[u] += coo[v];
      Q.push(u);
    }
  }
  ll ans = coo[d_sz];
  for(auto x: used) vis[x] = coo[x] = 0;
  return ans;
}

ll tree(int d, int d_sz, ll 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(ll len){
  ll 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)
        g[i].pb(compressed(((al[i - 1] + 1) >> 1) - 1));
      g[i].pb(compressed(al[i - 1] >> 1));
    }
  }

  for(auto x: r){
    int v = compressed(x[1] - x[0] + 1);
    priority_queue<int> Q;
    vector<int> used;

    Q.push(v);
    coo[v]++;

    while(!Q.empty()){
      int v = Q.top();
      Q.pop();
      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.push(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 + get<0>(pref.back()), 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 << a[b] << '\n';
      continue;
    }
    b -= n;
    int sz_pos = lower_bound(all(pref), tuple<ll, int>{b, 0}) - pref.begin();
    ll sz = get<1>(pref[sz_pos]);
    b -= get<0>(pref[sz_pos - 1]);
    // assert(!coi[sz].empty()); 
    int pos = upper_bound(all(coi[sz]), tuple<ll, int>{b, 0}) - coi[sz].begin();
    --pos;
    // assert(pos >= 0);
    b -= get<0>(coi[sz][pos]);
    int pos_a = get<1>(coi[sz][pos + 1]);
    // 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] + 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:47:37: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   47 |   for(auto x: used) vis[x] = coo[x] = 0;
ogledala.cpp: In function 'void solve()':
ogledala.cpp:97:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   for(int i = 1; i <= al.size(); ++i){
      |                  ~~^~~~~~~~~~~~
ogledala.cpp:129:38: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  129 |     for(int x: used) vis[x] = coo[x] = 0;
ogledala.cpp:138:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |   for(int i = 1; i <= al.size(); ++i){
      |                  ~~^~~~~~~~~~~~
ogledala.cpp: In function 'int main()':
ogledala.cpp:181:15: warning: unused variable 'aa' [-Wunused-variable]
  181 |   int tt = 1, aa;
      |               ^~

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