Submission #852401

#	Time	Username	Problem	Language	Result	Execution time	Memory
852401		mychecksedad	OGLEDALA (COI15_ogledala)	C++17	0 / 100	4061 ms	486800 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 = 5e6+100, M = 1e5+10, K = 22;


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

/*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({coi[x].back()[0] + val, pos});
}

ll count_val(int d, int d_sz){
  vector<int> used;
  priority_queue<int> Q;
  Q.push(d);
  co_vector[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]){
      co_vector[u] += co_vector[v];
      Q.push(u);
    }
  }
  ll ans = co_vector[d_sz];
  for(auto x: used) vis[x] = co_vector[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 1 + tree(g[d][0], d_sz, pos);
  }

  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 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){
    priority_queue<ll> Q;
    map<ll, bool> vis;
    map<ll, ll> coo;

    Q.push(x[1] - x[0] + 1);
    coo[x[1] - x[0] + 1]++;

    while(!Q.empty()){
      ll v = Q.top();
      al.pb(v);
      Q.pop();
      if(vis[v]) continue;
      
      add(v, coo[v], rn);
      co[v] += coo[v];
      // cout << v << ' ' << co[v] << ' ' << coo[v] << ' ' << rn << '\n';

      vis[v] = 1;

      if(v & 1){
        if(v > 1){
          coo[v >> 1] += coo[v] * 2;
          Q.push(v >> 1);
        }
      }else{  
        coo[v >> 1] += coo[v];
        Q.push(v >> 1);
        if(v > 2){
          coo[(v >> 1) - 1] += coo[v];
          Q.push((v >> 1) - 1);
        } 
      }
    }

    ++rn;
  }
  /* compressed tree */
  sort(all(al));
  al.erase(unique(all(al)), al.end());
  for(int i = 1; i <= al.size(); ++i){
    compressed[al[i - 1]] = 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]);
    }
  }

  /* prefix build */

  vector<pair<ll, ll>> vv;
  for(auto p: co){  
    vv.pb(p);
  }
  reverse(all(vv));
  pref.pb({0ll, 0ll});
  for(auto p: vv){
    pref.pb({p.second + pref.back()[0], p.first});
    // cout << pref.back()[0] << ' ' << pref.back()[1] << '\n';
  }
  // 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), array<ll, 2>{b, 0ll}) - pref.begin();
    ll sz = pref[sz_pos][1];
    b -= pref[sz_pos - 1][0];
    int pos = upper_bound(all(coi[sz]), array<ll, 2>{b, 0ll}) - coi[sz].begin();
    --pos;
    b -= coi[sz][pos][0];
    int pos_a = coi[sz][pos + 1][1];
    // 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], compressed[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:45:43: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   45 |   for(auto x: used) vis[x] = co_vector[x] = 0;
ogledala.cpp: In function 'void solve()':
ogledala.cpp:116:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |   for(int i = 1; i <= al.size(); ++i){
      |                  ~~^~~~~~~~~~~~
ogledala.cpp: In function 'int main()':
ogledala.cpp:170:15: warning: unused variable 'aa' [-Wunused-variable]
  170 |   int tt = 1, aa;
      |               ^~

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