結果
問題 |
No.1055 牛歩
|
ユーザー |
![]() |
提出日時 | 2019-09-26 18:56:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 71 ms / 1,000 ms |
コード長 | 1,980 bytes |
コンパイル時間 | 1,784 ms |
コンパイル使用メモリ | 177,948 KB |
実行使用メモリ | 10,624 KB |
最終ジャッジ日時 | 2024-09-22 09:03:12 |
合計ジャッジ時間 | 5,724 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 70 |
ソースコード
#include <bits/stdc++.h> int ri() { int n; scanf("%d", &n); return n; } bool solve(int n, int m, int *a, int q, int *b) { assert(std::is_sorted(a, a + m)); std::vector<int> list[m]; for (int i = 0; i < q; i++) list[b[i]].push_back(i); int pos[q]; for (int i = 0; i < q; i++) pos[i] = -2; // 0-th koma { int cur = a[0]; for (auto i : list[0]) { if (!cur) cur++; else cur--; pos[i] = cur; } } for (int i = 1; i < m; i++) { std::deque<std::pair<int, int> > clearance; // {pos, clearance} { // init clearance with slide maximum int head = 0; int cur_pos = a[i]; for (auto j : list[i - 1]) { while (head < (int) list[i].size() && list[i][head] < j) head++, cur_pos++; int cur_clearance = cur_pos - pos[j]; if (cur_clearance <= 0) return false; while (clearance.size() && clearance.back().second >= cur_clearance) clearance.pop_back(); clearance.push_back({j, cur_clearance}); } } int head = 0; int cur_pos = a[i]; int prev_pos = a[i - 1]; int clearance_minus = 0; for (auto j : list[i - 1]) { while (head < (int) list[i].size() && list[i][head] < j) { if (prev_pos < cur_pos - 1 && (!clearance.size() || clearance.front().second - clearance_minus > 2)) { // -1 cur_pos--; clearance_minus += 2; } else cur_pos++; pos[list[i][head]] = cur_pos; head++; } if (clearance.size() && clearance.front().first == j) clearance.pop_front(); prev_pos = pos[j]; } while (head < (int) list[i].size()) { if (prev_pos < cur_pos - 1) cur_pos--; else cur_pos++; pos[list[i][head]] = cur_pos; head++; } } assert(!std::count(pos, pos + q, -2)); for (int i = 0; i < q; i++) if (pos[i] >= n) return false; return true; } int main() { int n = ri(), m = ri(); int a[m]; for (int i = 0; i < m; i++) a[i] = ri() - 1; int q = ri(); int b[q]; for (int i = 0; i < q; i++) b[i] = ri() - 1; std::cout << (solve(n, m, a, q, b) ? "YES" : "NO") << std::endl; return 0; }