# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
746070 | 2023-05-21T11:00:13 Z | nguyentunglam | Railway Trip 2 (JOI22_ho_t4) | C++17 | 2000 ms | 1968 KB |
#include<bits/stdc++.h> #define fi first #define se second #define endl "\n" #define ii pair<int, int> using namespace std; const int N = 5010; int l[20][N], r[20][N]; int n, m, k; int main() { #define task "" cin.tie(0) -> sync_with_stdio(0); if (fopen ("task.inp", "r")) { freopen ("task.inp", "r", stdin); freopen ("task.out", "w", stdout); } if (fopen (task".inp", "r")) { freopen (task".inp", "r", stdin); freopen (task".out", "w", stdout); } cin >> n >> k >> m; for(int i = 1; i <= n; i++) l[0][i] = r[0][i] = i; for(int i = 1; i <= m; i++) { int a, b; cin >> a >> b; if (a < b) for(int j = a; j <= min(a + k - 1, b - 1); j++) for(int k = j + 1; k <= b; k++) r[0][j] = max(r[0][j], b); else for(int j = a; j >= max(a - k + 1, b + 1); j--) for(int k = j - 1; k >= b; k--) l[0][j] = min(l[0][j], b); } int lg = log2(n); for(int j = 1; j <= lg; j++) for(int i = 1; i <= n; i++) { l[j][i] = r[j][i] = i; for(int k = l[j - 1][i]; k <= r[j - 1][i]; k++) { l[j][i] = min(l[j][i], l[j - 1][k]); r[j][i] = max(r[j][i], r[j - 1][k]); } } int q; cin >> q; while (q--) { int s, t; cin >> s >> t; int left = s, right = s, ans = 0; for(int j = lg; j >= 0; j--) { int ll = left, rr = right; for(int k = left; k <= right; k++) { ll = min(ll, l[j][k]); rr = max(rr, r[j][k]); } if (t > rr || t < ll) { left = ll; right = rr; ans += (1 << j); } } if (ans == (1 << lg << 1) - 1) ans = -2; cout << ans + 1 << endl; } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 2 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 2 ms | 332 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 9 ms | 336 KB | Output is correct |
7 | Correct | 3 ms | 340 KB | Output is correct |
8 | Correct | 4 ms | 340 KB | Output is correct |
9 | Correct | 4 ms | 340 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 2 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 2 ms | 332 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 9 ms | 336 KB | Output is correct |
7 | Correct | 3 ms | 340 KB | Output is correct |
8 | Correct | 4 ms | 340 KB | Output is correct |
9 | Correct | 4 ms | 340 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
13 | Correct | 42 ms | 600 KB | Output is correct |
14 | Correct | 28 ms | 596 KB | Output is correct |
15 | Correct | 8 ms | 596 KB | Output is correct |
16 | Correct | 206 ms | 508 KB | Output is correct |
17 | Correct | 14 ms | 724 KB | Output is correct |
18 | Execution timed out | 2079 ms | 340 KB | Time limit exceeded |
19 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2067 ms | 1968 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2071 ms | 1108 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2068 ms | 1108 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 2 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 2 ms | 332 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 9 ms | 336 KB | Output is correct |
7 | Correct | 3 ms | 340 KB | Output is correct |
8 | Correct | 4 ms | 340 KB | Output is correct |
9 | Correct | 4 ms | 340 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
13 | Correct | 42 ms | 600 KB | Output is correct |
14 | Correct | 28 ms | 596 KB | Output is correct |
15 | Correct | 8 ms | 596 KB | Output is correct |
16 | Correct | 206 ms | 508 KB | Output is correct |
17 | Correct | 14 ms | 724 KB | Output is correct |
18 | Execution timed out | 2079 ms | 340 KB | Time limit exceeded |
19 | Halted | 0 ms | 0 KB | - |