結果

問題 No.2242 Cities and Teleporters
コンテスト
ユーザー Shell-Wataru
提出日時 2023-03-10 23:27:54
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,226 bytes
コンパイル時間 1,240 ms
コンパイル使用メモリ 119,084 KB
実行使用メモリ 44,812 KB
最終ジャッジ日時 2024-09-18 05:40:11
合計ジャッジ時間 18,846 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <limits>
#include <cmath>
#include <iomanip>
#include <functional>
#include <random>
#include <set>
using namespace std;
using ll = long long;

template <typename T>
struct Compress
{
    vector<T> xs;

    Compress() = default;

    Compress(const vector<T> &vs)
    {
        add(vs);
    }

    Compress(const initializer_list<vector<T>> &vs)
    {
        for (auto &p : vs)
            add(p);
    }

    void add(const vector<T> &vs)
    {
        copy(begin(vs), end(vs), back_inserter(xs));
    }

    void add(const T &x)
    {
        xs.emplace_back(x);
    }

    void build()
    {
        sort(begin(xs), end(xs));
        xs.erase(unique(begin(xs), end(xs)), end(xs));
    }

    vector<int> get(const vector<T> &vs) const
    {
        vector<int> ret;
        transform(begin(vs), end(vs), back_inserter(ret), [&](const T &x)
                  { return lower_bound(begin(xs), end(xs), x) - begin(xs); });
        return ret;
    }

    int get(const T &x) const
    {
        return lower_bound(begin(xs), end(xs), x) - begin(xs);
    }

    size_t size() const
    {
        return xs.size();
    }
    const T &operator[](int k) const
    {
        return xs[k];
    }
};

struct Doubling
{
  const int LOG;
  vector< vector< int > > table;

  Doubling(int sz, int64_t lim_t) : LOG(64 - __builtin_clzll(lim_t))
  {
    table.assign(LOG, vector< int >(sz, -1));
  }

  void set_next(int k, int x)
  {
    table[0][k] = x;
  }

  void build()
  {
    for(int k = 0; k + 1 < LOG; k++) {
      for(int i = 0; i < table[k].size(); i++) {
        if(table[k][i] == -1) table[k + 1][i] = -1;
        else table[k + 1][i] = table[k][table[k][i]];
      }
    }
  }

  int query(int k, int64_t t)
  {
    for(int i = LOG - 1; i >= 0; i--) {
      if((t >> i) & 1) k = table[i][k];
      if (k == -1){
        return -1;
      }
    }
    return k;
  }
};


ll answer(Doubling &d,ll Tfrom,ll Tto,ll l,ll r){
    if (l+1 == r){
        return r;
    }
    ll center = (l+r)/2;
    if (d.query(Tfrom,center) >= Tto){
        return answer(d,Tfrom,Tto,l,center);
    }else{
        return answer(d,Tfrom,Tto,center,r);
    }
}
int main()
{
    // 整数の入力
    ll N;
    cin >> N;
    Compress<ll> C;
    vector<ll> H(N);
    vector<ll> T(N);

    for(int i = 0;i < N;i++){
        cin >> H[i];
        C.add(H[i]);
    }
    for(int i = 0;i < N;i++){
        cin >> T[i];
        C.add(T[i]);
    }
    C.build();
    vector<ll>  maximumT(C.size(),-1);
    for(int i = 0;i < N;i++){
        maximumT[C.get(H[i])] = max(maximumT[C.get(H[i])],(ll)C.get(T[i]));
    }
    for(ll i = 1;i < C.size();i++){
        maximumT[i] = max(max(maximumT[i],maximumT[i-1]),i);
    }
    Doubling d(C.size(),C.size());
    for(int i = 0;i < C.size();i++){
        d.set_next(i,maximumT[i]);
    }
    ll Q;
    cin >> Q;
    for(int i = 0;i < Q;i++){
        ll a,b;
        cin >> a >> b;
        a--;b--;
        ll t = answer(d,C.get(T[a]),C.get(H[b]),-1,N);
        if (t == N){
            cout << -1 << endl;
        }else{
            cout << t + 1 << endl;
        }
    }
    return 0;
}
0