結果

問題 No.2242 Cities and Teleporters
ユーザー lddlinanlddlinan
提出日時 2023-03-10 23:09:24
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 505 ms / 3,000 ms
コード長 2,168 bytes
コンパイル時間 1,031 ms
コンパイル使用メモリ 89,816 KB
実行使用メモリ 31,276 KB
最終ジャッジ日時 2023-10-18 08:52:44
合計ジャッジ時間 9,853 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7 ms
29,776 KB
testcase_01 AC 7 ms
29,712 KB
testcase_02 AC 7 ms
29,776 KB
testcase_03 AC 8 ms
29,776 KB
testcase_04 AC 7 ms
29,712 KB
testcase_05 AC 362 ms
31,276 KB
testcase_06 AC 328 ms
31,276 KB
testcase_07 AC 350 ms
31,276 KB
testcase_08 AC 505 ms
31,276 KB
testcase_09 AC 336 ms
31,276 KB
testcase_10 AC 172 ms
31,276 KB
testcase_11 AC 256 ms
31,276 KB
testcase_12 AC 259 ms
31,276 KB
testcase_13 AC 271 ms
31,276 KB
testcase_14 AC 319 ms
31,276 KB
testcase_15 AC 269 ms
31,276 KB
testcase_16 AC 326 ms
31,276 KB
testcase_17 AC 403 ms
31,276 KB
testcase_18 AC 176 ms
31,248 KB
testcase_19 AC 174 ms
31,172 KB
testcase_20 AC 259 ms
31,172 KB
testcase_21 AC 253 ms
31,184 KB
testcase_22 AC 163 ms
31,112 KB
testcase_23 AC 178 ms
31,212 KB
testcase_24 AC 176 ms
31,212 KB
testcase_25 AC 173 ms
31,212 KB
権限があれば一括ダウンロードができます

ソースコード

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