답안 #852460

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
852460	2023-09-21T20:20:58 Z	mychecksedad	OGLEDALA (COI15_ogledala)	C++17	컴파일 오류	0 ms	0 KB

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'
const int N = 25e5+100, M = 1e5+10, K = 22;
 
 
ll m, n, q, a[M];
vector<pair<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){
  coi[x].pb({(coi[x].empty() ? 0 : coi[x].back().first) + val, pos});
}
 
ll count_val(int d, int d_sz){
  vector<int> used;
  set<int> Q;
  Q.insert(d);
  coo[d]++;
  while(!Q.empty()){
    auto it = prev(Q.end());
    int v = *it;
    Q.erase(it);
    if(vis[v]) continue;
    vis[v] = 1;
    used.pb(v);
    for(int u: g[v]){
      coo[u] += coo[v];
      Q.insert(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);
    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 << a[b] << '\n';
      continue;
    }
    b -= n;
    int sz_pos = lower_bound(all(pref), pair<ll, int>{b, 0}) - pref.begin();
    ll 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] + 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

ogledala.cpp: In function 'void add(double, double, double)':
ogledala.cpp:26:6: error: invalid types 'std::vector<std::pair<double, int> > [2500100][double]' for array subscript
   26 |   coi[x].pb({(coi[x].empty() ? 0 : coi[x].back().first) + val, pos});
      |      ^
ogledala.cpp:26:18: error: invalid types 'std::vector<std::pair<double, int> > [2500100][double]' for array subscript
   26 |   coi[x].pb({(coi[x].empty() ? 0 : coi[x].back().first) + val, pos});
      |                  ^
ogledala.cpp:26:39: error: invalid types 'std::vector<std::pair<double, int> > [2500100][double]' for array subscript
   26 |   coi[x].pb({(coi[x].empty() ? 0 : coi[x].back().first) + val, pos});
      |                                       ^
ogledala.cpp: In function 'double 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 'double tree(int, int, double)':
ogledala.cpp:53:40: error: invalid operands of types '__gnu_cxx::__alloc_traits<std::allocator<double>, double>::value_type' {aka 'double'} and 'int' to binary 'operator>>'
   53 |   if(d == d_sz) return (al[d - 1] + 1) >> 1;
      |                        ~~~~~~~~~~~~~~~ ^~ ~
      |                                   |       |
      |                                   |       int
      |                                   __gnu_cxx::__alloc_traits<std::allocator<double>, double>::value_type {aka double}
ogledala.cpp: In function 'void proc(double)':
ogledala.cpp:72:8: error: invalid operands of types 'double' and 'int' to binary 'operator>>'
   72 |     mx >>= 1;
      |     ~~~^~~~~
ogledala.cpp:72:8: note:   in evaluation of 'operator>>=(double, int)'
ogledala.cpp:73:11: error: invalid operands of types 'double' and 'int' to binary 'operator&'
   73 |     if(mn & 1) mn >>= 1;
      |        ~~ ^ ~
      |        |    |
      |        |    int
      |        double
ogledala.cpp:73:19: error: invalid operands of types 'double' and 'int' to binary 'operator>>'
   73 |     if(mn & 1) mn >>= 1;
      |                ~~~^~~~~
ogledala.cpp:73:19: note:   in evaluation of 'operator>>=(double, int)'
ogledala.cpp:74:18: error: invalid operands of types 'double' and 'int' to binary 'operator>>'
   74 |     else mn = (mn>>1) - 1;
      |                ~~^~~
      |                |   |
      |                |   int
      |                double
ogledala.cpp: In function 'void solve()':
ogledala.cpp:97:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   for(int i = 1; i <= al.size(); ++i){
      |                  ~~^~~~~~~~~~~~
ogledala.cpp:100:45: error: invalid operands of types '__gnu_cxx::__alloc_traits<std::allocator<double>, double>::value_type' {aka 'double'} and 'int' to binary 'operator>>'
  100 |         g[i].pb(compressed(((al[i - 1] + 1) >> 1) - 1));
      |                             ~~~~~~~~~~~~~~~ ^~ ~
      |                                        |       |
      |                                        |       int
      |                                        __gnu_cxx::__alloc_traits<std::allocator<double>, double>::value_type {aka double}
ogledala.cpp:101:36: error: invalid operands of types '__gnu_cxx::__alloc_traits<std::allocator<double>, double>::value_type' {aka 'double'} and 'int' to binary 'operator>>'
  101 |       g[i].pb(compressed(al[i - 1] >> 1));
ogledala.cpp:130:38: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  130 |     for(int x: used) vis[x] = coo[x] = 0;
ogledala.cpp:139:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |   for(int i = 1; i <= al.size(); ++i){
      |                  ~~^~~~~~~~~~~~
ogledala.cpp:158:16: error: invalid types 'double [100010][double]' for array subscript
  158 |       cout << a[b] << '\n';
      |                ^
ogledala.cpp:166:34: error: invalid types 'std::vector<std::pair<double, int> > [2500100][double]' for array subscript
  166 |     int pos = upper_bound(all(coi[sz]), pair<ll, int>{b, 0}) - coi[sz].begin();
      |                                  ^
ogledala.cpp:8:16: note: in definition of macro 'all'
    8 | #define all(x) x.begin(), x.end()
      |                ^
ogledala.cpp:166:34: error: invalid types 'std::vector<std::pair<double, int> > [2500100][double]' for array subscript
  166 |     int pos = upper_bound(all(coi[sz]), pair<ll, int>{b, 0}) - coi[sz].begin();
      |                                  ^
ogledala.cpp:8:27: note: in definition of macro 'all'
    8 | #define all(x) x.begin(), x.end()
      |                           ^
ogledala.cpp:166:67: error: invalid types 'std::vector<std::pair<double, int> > [2500100][double]' for array subscript
  166 |     int pos = upper_bound(all(coi[sz]), pair<ll, int>{b, 0}) - coi[sz].begin();
      |                                                                   ^
ogledala.cpp:170:15: error: invalid types 'std::vector<std::pair<double, int> > [2500100][double]' for array subscript
  170 |       b -= coi[sz][pos].first;
      |               ^
ogledala.cpp:171:20: error: invalid types 'std::vector<std::pair<double, int> > [2500100][double]' for array subscript
  171 |     int pos_a = coi[sz][pos + 1].second;
      |                    ^
ogledala.cpp: In function 'int main()':
ogledala.cpp:183:15: warning: unused variable 'aa' [-Wunused-variable]
  183 |   int tt = 1, aa;
      |               ^~