結果
問題 | No.2002 Range Swap Query |
ユーザー |
|
提出日時 | 2022-04-25 18:00:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 779 ms / 2,000 ms |
コード長 | 1,452 bytes |
コンパイル時間 | 2,287 ms |
コンパイル使用メモリ | 205,792 KB |
最終ジャッジ日時 | 2025-01-28 21:50:40 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include<bits/stdc++.h>#pragma GCC target("avx2")#pragma GCC optimize("O3")using namespace std;int P[500000],WP[500000],A[500000],B[500000],ans[500000];tuple<int,int,int,int> query[200000];int sqr;bool compare(tuple<int,int,int,int> &a,tuple<int,int,int,int> &b){if(get<0>(a)/sqr == get<0>(b)/sqr){if(get<1>(a)!=get<1>(b))return (get<1>(a)<get<1>(b))^(get<0>(a)/sqr%2);else return get<3>(a)<get<3>(b);}else return get<0>(a)/sqr < get<0>(b)/sqr;}int main(){cin.tie(0);ios::sync_with_stdio(false);int N,K,Q;cin >> N >> K >> Q;for(int i=0;i<K;i++){cin >> A[i] >> B[i];A[i]--;B[i]--;}for(int i=0;i<Q;i++){int l,r,x;cin >> l >> r >> x;query[i] = make_tuple(l-1,r,x-1,i);}sqr = sqrt(K);sort(query,query+Q,compare);for(int i=0;i<N;i++) P[i] = WP[i] = i;int litr = 0,ritr = 0;for(int i=0;i<Q;i++){auto [l,r,x,id] = query[i];while(ritr < r){swap(P[A[ritr]],P[B[ritr]]);swap(WP[P[A[ritr]]],WP[P[B[ritr]]]);ritr++;}while(litr > l){litr--;swap(WP[A[litr]],WP[B[litr]]);swap(P[WP[A[litr]]],P[WP[B[litr]]]);}while(ritr > r){ritr--;swap(P[A[ritr]],P[B[ritr]]);swap(WP[P[A[ritr]]],WP[P[B[ritr]]]);}while(litr < l){swap(WP[A[litr]],WP[B[litr]]);swap(P[WP[A[litr]]],P[WP[B[litr]]]);litr++;}ans[id] = P[x]+1;}for(int i=0;i<Q;i++) cout << ans[i] << "\n";}