結果
問題 | No.2242 Cities and Teleporters |
ユーザー |
![]() |
提出日時 | 2023-03-10 22:47:37 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2,228 ms / 3,000 ms |
コード長 | 2,742 bytes |
コンパイル時間 | 310 ms |
コンパイル使用メモリ | 32,384 KB |
実行使用メモリ | 34,688 KB |
最終ジャッジ日時 | 2024-09-18 04:54:25 |
合計ジャッジ時間 | 33,326 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#include <stdio.h>#include <stdlib.h>int cmp_int (const void *ap, const void *bp) {int a = *(int *)ap;int b = *(int *)bp;if (a < b) {return -1;}if (a > b) {return 1;}return 0;}int main () {int n = 0;int h[200000][2] = {};int t[200000] = {};int q = 0;int a = 0;int b = 0;int res = 0;int max[18][200000] = {};int org_h[200000] = {};int max_idx[18][200000] = {};res = scanf("%d", &n);for (int i = 0; i < n; i++) {res = scanf("%d", h[i]);h[i][1] = i;org_h[i] = h[i][0];}for (int i = 0; i < n; i++) {res = scanf("%d", t+i);}qsort(h, n, sizeof(int)*2, cmp_int);max[0][0] = t[h[0][1]];for (int j = 1; j < n; j++) {max[0][j] = t[h[j][1]];if (max[0][j] < max[0][j-1]) {max[0][j] = max[0][j-1];}}for (int i = 1; i < 18; i++) {for (int j = 0; j < n; j++) {int idx[2] = { -1, n };while (idx[1]-idx[0] > 1) {int nxt = (idx[0]+idx[1])/2;if (h[nxt][0] <= max[i-1][j]) {idx[0] = nxt;} else {idx[1] = nxt;}}if (idx[0] < 0) {max[i][j] = max[i-1][j];} else {max[i][j] = max[i-1][idx[0]];}if (max[i][j] < max[i-1][j]) {max[i][j] = max[i-1][j];}if (j > 0 && max[i][j] < max[i][j-1]) {max[i][j] = max[i][j-1];}}}for (int i = 0; i < 18; i++) {for (int j = 0; j < n; j++) {int idx[2] = { -1, n };while (idx[1]-idx[0] > 1) {int nxt = (idx[0]+idx[1])/2;if (h[nxt][0] <= max[i][j]) {idx[0] = nxt;} else {idx[1] = nxt;}}max_idx[i][j] = idx[0];}}res = scanf("%d", &q);while (q > 0) {int ans[2] = { 0, n+1 };res = scanf("%d", &a);res = scanf("%d", &b);a--;b--;while (ans[1]-ans[0] > 1) {int nxt = (ans[0]+ans[1])/2;int cnt = 0;int tmp = 0;int org_nxt = nxt;int idx = -1;int r = n;tmp = t[a];while (r-idx > 1) {int nidx = (idx+r)/2;if (h[nidx][0] <= tmp) {idx = nidx;} else {r = nidx;}}nxt--;while (nxt > 0) {if (nxt%2 == 1) {if (idx >= 0 && max[cnt][idx] > tmp) {tmp = max[cnt][idx];idx = max_idx[cnt][idx];}}nxt /= 2;cnt++;}if (org_h[b] <= tmp) {ans[1] = org_nxt;} else {ans[0] = org_nxt;}}if (ans[1] > n) {printf("-1\n");} else {printf("%d\n", ans[1]);}q--;}return 0;}