結果
問題 | No.905 Sorted? |
ユーザー |
![]() |
提出日時 | 2019-10-11 22:04:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,869 bytes |
コンパイル時間 | 1,652 ms |
コンパイル使用メモリ | 173,540 KB |
実行使用メモリ | 9,984 KB |
最終ジャッジ日時 | 2024-11-25 07:31:25 |
合計ジャッジ時間 | 4,199 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 WA * 4 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define rep(i,N) for(int (i)=0;(i) < (N); (i)++)#define all(V) V.begin(), V.end()using i64 = int_fast64_t;using P = pair<i64,i64>;class UnionFind{private:using uint = std::uint_fast64_t;std::vector<uint> par;std::vector<uint> sizes;uint find(uint x){if(x == par[x]) return x;return par[x] = find(par[x]);}public:UnionFind() = delete;UnionFind(uint size) : par(size), sizes(size, 1){for(uint i = 0; i < size; ++i) par[i] = i;}bool unite(uint x, uint y){x = find(x);y = find(y);if(x == y) return false;if(sizes[x] < sizes[y]) std::swap(x, y);if(sizes[x] == sizes[y] && x > y) std::swap(x, y);sizes[x] += sizes[y];sizes[y] = 0;par[y] = x;return true;}bool isSame(uint x, uint y ){ return find(par[x]) == find(par[y]);}uint getSize(uint x){return find(sizes[par[x]]);}};int main(){int N;cin >> N;vector<int> A(N);rep(i,N) cin >> A[i];UnionFind up(2*N), down(2*N);int left = 0, right = 0;int last = A[0];while(right < N){while(last <= A[right] && right < N) {up.unite(N+left, right);last = A[right];right++;}if(right < N) last = A[right];left = right;}left = 0, right = 0;last = A[0];while(right < N){while(last >= A[right] && right < N) {down.unite(N+left, right);last = A[right];right++;}if(right < N) last = A[right];left = right;}int Q, l , r;cin >> Q;rep(i, Q){cin >> l >> r;cout << (up.isSame(l, r) ? 1 : 0) << " ";cout << (down.isSame(l, r) ? 1 : 0) << endl;}}