結果
問題 | No.2242 Cities and Teleporters |
ユーザー |
|
提出日時 | 2023-03-10 23:09:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 518 ms / 3,000 ms |
コード長 | 2,168 bytes |
コンパイル時間 | 934 ms |
コンパイル使用メモリ | 89,352 KB |
最終ジャッジ日時 | 2025-02-11 09:11:23 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:32:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 32 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:33:31: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 33 | for (i=1; i<=n; i++) scanf("%d", &rs[i].h); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:34:31: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 34 | for (i=1; i<=n; i++) scanf("%d", &rs[i].t); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:69:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 69 | scanf("%d", &q); | ~~~~~^~~~~~~~~~ main.cpp:71:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 71 | scanf("%d %d", &a, &b); | ~~~~~^~~~~~~~~~~~~~~~~
ソースコード
#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;}