#848401 (C++17) No.2242 Cities and Teleporters

提出ソース

結果

問題	No.2242 Cities and Teleporters
ユーザー	asaringo
提出日時	2023-03-11 15:35:36
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	11,623 bytes
コンパイル時間	3,236 ms
コンパイル使用メモリ	235,824 KB
実行使用メモリ	166,088 KB
最終ジャッジ日時	2023-10-18 09:58:12
合計ジャッジ時間	29,141 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	4 ms 6,440 KB
testcase_01	AC	4 ms 6,440 KB
testcase_02	AC	4 ms 6,440 KB
testcase_03	AC	5 ms 6,440 KB
testcase_04	WA	-
testcase_05	AC	1,816 ms 166,088 KB
testcase_06	AC	1,164 ms 166,088 KB
testcase_07	AC	1,842 ms 166,088 KB
testcase_08	AC	2,602 ms 166,088 KB
testcase_09	AC	2,500 ms 166,088 KB
testcase_10	AC	425 ms 166,088 KB
testcase_11	AC	404 ms 166,088 KB
testcase_12	AC	409 ms 166,088 KB
testcase_13	AC	608 ms 166,088 KB
testcase_14	AC	1,046 ms 166,088 KB
testcase_15	AC	611 ms 166,088 KB
testcase_16	AC	666 ms 166,088 KB
testcase_17	AC	1,194 ms 166,088 KB
testcase_18	AC	585 ms 164,444 KB
testcase_19	AC	742 ms 163,624 KB
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std ;
#define fast_input_output ios::sync_with_stdio(false); cin.tie(nullptr);
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll ;
typedef long double ld ;
typedef pair<ll,ll> P ;
typedef tuple<ll,ll,ll> TP ;
#define chmin(a,b) a = min(a,b)
#define chmax(a,b) a = max(a,b)
#define bit_count(x) __builtin_popcountll(x)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a / gcd(a,b) * b
#define rep(i,n) for(int i = 0 ; i < n ; i++)
#define rrep(i,a,b) for(int i = a ; i < b ; i++)
#define repi(it,S) for(auto it = S.begin() ; it != S.end() ; it++)
#define pt(a) cout << a << endl
#define DEBUG(...) ; cout << #__VA_ARGS__ << endl ; for(auto x : {__VA_ARGS__}) cout << x << "  " ; cout << endl ;
#define DEBUG_LIST(...) cout << #__VA_ARGS__ << endl ; DEBUG_REP(__VA_ARGS__) ;
#define DEBUG_REP(V) cout << "{ " ; repi(itr,V) cout << *itr << ", " ; cout << "}" << endl ;
#define debug(a) cout << #a << " " << a << endl
#define all(a) a.begin(), a.end()
#define endl "\n"

struct UnionFind {
    private:
        vector<int> par ; //親
        vector<int> lank ; //木の深さ
        vector<int> volume ; //構成する集合のサイズ
        vector<int> edge ; //構成する集合の辺の数

    public:
        UnionFind(int n){
            //n要素で初期化
            par.resize(n) ;
            lank.resize(n) ;
            volume.resize(n) ;
            edge.resize(n) ;
            for(int i = 0 ; i < n ; i++){
                par[i] = i ;
                lank[i] = 0 ;
                volume[i] = 1 ;
                edge[i] = 0 ;
            }
        }
        //木の根を求める
        int root(int x) {
            if(par[x] == x) return x ;
            else return par[x] = root(par[x]) ;
        }

        //xとyの属する集合を合併
        void unite(int x , int y){
            x = root(x);
            y = root(y) ;
            if(x == y) {
                edge[x]++ ;
                return ;
            }
            if(lank[x] < lank[y]){
                par[x] = y ;
                volume[y] += volume[x] ;
                edge[y] += edge[x] + 1 ;
            } else {
                par[y] = x ;
                volume[x] += volume[y] ;
                edge[x] += edge[y] + 1 ;
                if(lank[x] == lank[y]) lank[x]++ ;
            }
        }

        bool same(int x , int y) { return root(x) == root(y) ; }
        int size(int x) { return volume[root(x)] ; }
        int edge_num(int x) { return edge[root(x)] ; }
};

// 座標圧縮
template<typename T=int> struct Compress{
    private:
        vector<int> vec ; // 元の値の座標圧縮後の値
        unordered_map<T,int> mp ; // 元の値 -> 変換された値
        unordered_map<int,T> np ; // 変換された値 -> 元の値

        void build(vector<T> A){
            int n = A.size() ;
            vector<T> B(n) ;
            for(int i = 0 ; i < n ; i++) B[i] = A[i] ;
            vec.resize(n) ;
            sort(A.begin(),A.end()) ;
            for(int i = 0 ; i < n ; i++){
                auto it = lower_bound(A.begin(),A.end(),B[i]) ;
                int id = it - A.begin() ;
                vec[i] = id ;
                mp[B[i]] = id;
                np[id] = B[i] ;
            }
        }

    public:
        Compress(){}
        Compress(vector<T> A) { build(A); }
        size_t size() {return vec.size() ; }
        // 元の値 -> 変換された値
        inline int encrypt(T i) { return mp[i] ; }
        // 変換された値 -> 元の値
        inline T decrypt(int i) { return np[i] ; }
        vector<int> compress() { return vec; }
        vector<int> compress(vector<T> A) { build(A); return vec; }
        inline int operator [] (int i) { return vec[i] ; }
};

// function               : return              : description
// -----------------------------------------------------
// Compress()             : void          : コンストラクタ
// Compress(vector<ll> A) : void          : コンストラクタ, 座圧する
// encrypt(ll v)          : int           : 元の値 -> 座圧後の値
// decrypt(int v)         : ll            : 座圧後の値 -> 元の値
// compress()             : vector<int>   : 座圧後の値
// operator[i]            : int           : 座圧後の値の vector にアクセスすることが可能

template<typename S, S (*op)(S, S), S (*mapping)(S, S), S (*e)()> struct SegmentTree{
    private:
        int n_, n, log;
        vector<S> node;

        void init_(S ev) { node = {}; node.resize(2*n-1,ev); }
        
        void build(vector<S> V){
            n = 1;
            log = 0;
            while(n < n_) n *= 2, log++;
            node.resize(2*n-1,e());
            for(int i = 0; i < n_; i++) node[n-1+i] = V[i];
            for(int i = n - 2; i >= 0; i--) node[i] = op(node[2*i+1], node[2*i+2]);
        }
        
        void apply_(int k, S x){
            k += n - 1;
            node[k] = mapping(node[k],x);
            while(k > 0){
                k = (k - 1) / 2;
                node[k] = op(node[2*k+1], node[2*k+2]);
            }
        }

        S get_(int k) const { return node[k+n-1]; }

        S prod_(int l, int r) const {
            S lval = e(), rval = e();
            l += n - 1;
            r += n - 1;

            while(l < r){
                if(!(l & 1)) lval = op(lval, node[l++]);
                if(!(r & 1)) rval = op(rval, node[--r]);
                l >>= 1;
                r >>= 1;
            }
            return op(lval, rval);
        }

        S all_prod_() const { return node[0]; }

        template<bool (*f)(S)> int max_right_(int l) const {
            return max_right_(l, [](S x) { return f(x); });
        }

        template<typename F> int max_right_(int l, F f) const {

            l += n;
            S sval = e();

            do {
                while(l % 2 == 0) l >>= 1;
                if(!f(op(sval, node[l-1]))) {
                    while(l < n){
                        l = 2 * l;
                        if(f(op(sval, node[l-1]))) {
                            sval = op(sval, node[l-1]);
                            l++;
                        }
                    }
                    return l - n;
                }
                sval = op(sval, node[l-1]);
                l++;
            } while ((l & -l) != l);

            return n_;
        }

        template<bool (*f)(S)> int min_left_(int r) const {
            return min_left_(r, [](S x) { return f(x); });
        }

        template<typename F> int min_left_(int r, F f) const {
            r += n;
            S sval = e();
            do {
                r--;
                while(r > 1 && r & 1) r >>= 1;
                if(!f(op(sval, node[r-1]))) {
                    while(r < n) {
                        r = 2*r+1;
                        if(f(op(sval, node[r-1]))) {
                            sval = op(sval,node[r-1]);
                            r--;
                        }
                    }
                    return r + 1 - n;
                }
                sval = op(sval, node[r-1]);
            } while((r & -r) != r);

            return 0;
        }

    public:
        SegmentTree(int n): SegmentTree(vector<S>(n, e())) {}
        SegmentTree(const vector<S>& V): n_((int)V.size()) { build(V); }
        void init(S ev) { init_(ev); }
        void apply(int k, S x) { apply_(k, x); }
        S get(int k) const { return get_(k); }
        S prod(int l, int r) const { return prod_(l, r); }
        S all_prod() const { return all_prod_(); }
        template<bool (*f)(S)> int max_right(int l) const { return max_right_<f>(l); }
        template<bool (*f)(S)> int min_left(int  r) const { return min_left_<f>(r); }

};

namespace monoid{
    struct S{ll max; int id;};
    S e() { return S{(ll)-2e9, -1}; }
    S op(S x , S y) {
        if(x.max > y.max) return x;
        else return y;
    }
    S mapping(S x , S y) { return y;}
    int target;
    auto f = [](S x) -> bool { return x.max <= target; };
} using namespace monoid;


int n;
int q;
ll H[202020];
ll T[202020];

struct Doubling {
    private:
        const ll INF = LLONG_MAX ;

        int n ;
        vector<vector<int>> dp ;
        vector<vector<ll>> S ;

        void init(vector<int> A_ , vector<ll> T) {
            n = A_.size() ;
            dp.resize(60,vector<int>(n)) ;
            S.resize(60,vector<ll>(n)) ;
            rep(i,n){
                dp[0][i] = A_[i] ;
                S[0][i] = T[i] ;
            }
        }

        void build_(int count = 59){
            rep(i,count) {
                rep(j,n) {
                    dp[i+1][j] = dp[i][dp[i][j]] ;
                    if(INF - S[i][j] <= S[i][dp[i][j]]) S[i+1][j] = INF ;
                    else S[i+1][j] = S[i][j] + S[i][dp[i][j]] ;
                }
            }
        }

        int get_index_(int v , ll k) {
            int cnt = 0 ;
            while(k > 0){
                if(k & 1) v = dp[cnt][v] ;
                cnt++ ;
                k >>= 1 ;
            }
            return v ;
        }

        ll get_sum_(int v , ll k) {
            ll sum = 0 ;
            int cnt = 0 ;
            while(k > 0){
                if(k & 1) {
                    if(INF - sum <= S[cnt][v]) sum = INF ;
                    else sum += S[cnt][v] ;
                    v = dp[cnt][v] ;
                }
                cnt++ ;
                k >>= 1 ;
            }
            return sum ;
        }

    public:
        // A[i] = j : i が j に遷移する
        // T[i] = x : i が j に遷移する時に得る個数(通りの数)が x である
        Doubling(vector<int> A_ , vector<ll> T = vector<ll>(202020,0)){ init(A_,T) ; }

        void build() { build_() ; }
        int get_index(int v , ll k) { return get_index_(v,k) ; }
        int get_next_moving_index(int v) { return dp[0][v] ; }
        ll get_sum(int v , ll k) { return get_sum_(v,k) ; }
        ll get_next_moving_sum(int v) { return S[0][v] ; }
};

int main(){
    fast_input_output
    cin >> n;
    vector<int> V;
    vector<pair<int,int>> X;
    rep(i,n) cin >> H[i], V.push_back(H[i]);
    rep(i,n) cin >> T[i], V.push_back(T[i]), X.push_back({T[i],i});
    SegmentTree<S, op, mapping, e> segtree(n);
    sort(all(X));
    vector<int> D(n);
    for(int i = n - 1; i >= 0; i--){
        auto[t, id] = X[i];
        ll minval = 1e18;
        int gid = -1;
        if(i < n - 1) {
            S s = segtree.prod(i+1,i+2);
            minval = s.max;
            gid = s.id;
        }
        int h = H[id];
        // cout << gid << " " << minval << " ";
        if(minval > h){
            segtree.apply(i,{h,i});
        }
        else{
            segtree.apply(i,{minval,gid});
        }
        target = t;
        int maxrig = segtree.max_right<f>(i);
        // cout << maxrig << " " << t << " ";
        auto[nt,nid] = X[maxrig-1];
        // cout << id << " " << nid << endl;
        D[id] = nid;
    }
    Doubling dbg(D);
    dbg.build();

    cin >> q;
    rep(i,q){
        int a, b;
        cin >> a >> b;
        a--; b--;
        int lef = -1, rig = n;
        while(rig - lef > 1){
            int mid = (lef + rig) / 2;
            int id = dbg.get_index(a,mid);
            int t = T[id];
            // cout << mid << " " << id << " " << t << endl;
            if(H[b] <= t) rig = mid;
            else lef = mid;
        }
        if(rig == n) rig = -1;
        else rig++;
        cout << rig << endl;
    }
}

yukicoder

結果

テストケース

ソースコード