結果

問題 No.2242 Cities and Teleporters
ユーザー lddlinanlddlinan
提出日時 2023-03-10 23:09:24
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 466 ms / 3,000 ms
コード長 2,168 bytes
コンパイル時間 1,071 ms
コンパイル使用メモリ 89,956 KB
実行使用メモリ 31,360 KB
最終ジャッジ日時 2024-09-18 05:19:40
合計ジャッジ時間 9,667 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include <map>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <algorithm>
#include <array>
#include <unordered_set>
#include <unordered_map>
#include <string>
using namespace std;

bool rcmp(int a, int b) { return a>b; }
typedef long long LL;


typedef struct {int h, t, i; } RNode;
RNode rs[200004];
bool mycmp(const RNode& a, const RNode& b) {
    return a.h<b.h;
}
int hs[200004];
int ix[200004];
int hh[200004];
int jp[30][200004];
int main() {
    int n, i, j, k, a, b, hi, na, ni, h, d, c, q;
    scanf("%d", &n);
    for (i=1; i<=n; i++) scanf("%d", &rs[i].h);
    for (i=1; i<=n; i++) scanf("%d", &rs[i].t);
    for (i=1; i<=n; i++) rs[i].i=i;
    rs[0].h=0; rs[0].t=0; rs[0].i=0;
    sort(rs, rs+n+1, mycmp);
    for (i=0; i<=n; i++) {
        hs[i]=rs[i].h;
        ix[rs[i].i]=i;
    }
    h=0; hi=0;
    for (i=0; i<=n; ) {
        j=i; while(j<=n&&rs[j].h==rs[i].h) {
            if (h<=rs[j].t) {
                h=rs[j].t;
                hi=j;
            }
            j++;
        }
        while(i<j) {
            hh[i]=hi;
            i++;
        }
    }
    for (i=0; i<=n; i++) {
        hi=upper_bound(hs, hs+(n+1), rs[i].t)-hs-1;
        hi=hh[hi];
        if (rs[hi].t<=rs[i].t) jp[0][i]=i;
        else jp[0][i]=hi;
        // printf("jp %d: %d (%d %d)\n", i, jp[0][i], rs[i].h, rs[i].t);
    }
    for (k=1; k<30; k++) {
        for (i=0; i<=n; i++) {
            ni=jp[k-1][i];
            jp[k][i]=jp[k-1][ni];
        }
    }
    scanf("%d", &q);
    for (i=0; i<q; i++) {
        scanf("%d %d", &a, &b);
        a=ix[a]; b=ix[b];
        // printf("%d(%d)-->%d\n", a, jp[29][a], b);
        na=jp[29][a];
        if (rs[na].t<rs[b].h) { printf("-1\n"); continue; }
        if (rs[a].t>=rs[b].h) { printf("1\n"); continue; }
        d=1<<29;
        c=1;
        for (k=29; k>=0; k--) {
            while(1) {
                na=jp[k][a];
                if (rs[na].t>=rs[b].h) break;
                a=na;
                c+=d;
            }
            d>>=1;
        }
        c++;
        printf("%d\n", c);
    }
    return 0;
}
0