結果
問題 | No.2002 Range Swap Query |
ユーザー |
|
提出日時 | 2022-04-23 17:13:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,419 bytes |
コンパイル時間 | 2,377 ms |
コンパイル使用メモリ | 207,396 KB |
最終ジャッジ日時 | 2025-01-28 21:13:11 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 RE * 1 TLE * 1 |
ソースコード
#include<bits/stdc++.h>#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")using namespace std;int P[400000],WP[400000],A[200000],B[200000],ans[200000];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) return (get<1>(a)<get<1>(b))^(get<0>(a)/sqr%2);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(N);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";}