結果

問題 No.2002 Range Swap Query
コンテスト
ユーザー vjudge1
提出日時 2026-10-01 13:18:51
言語 C++14
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 80 ms / 2,000 ms
+ 675µs
コード長 1,003 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,889 ms
コンパイル使用メモリ 178,676 KB
実行使用メモリ 15,616 KB
最終ジャッジ日時 2026-10-01 13:20:55
合計ジャッジ時間 7,124 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n,k,q;
int cnt_l,cnt_r;
int a[1000011],b[1000011];
int p[1000011],at[1000011];
int v[1000011],ans[1000011];
int head_r[1000011],nxt_r[2000011];
int head_l[1000011],nxt_l[1000011];
int lq[1000011],rx[2000011],rq[2000011];

int main() {
	scanf("%d%d%d",&n,&k,&q);
	for(int i=1;i<=k;i++)
		scanf("%d%d",&a[i],&b[i]);
	for(int i=1;i<=q;i++) {
		int l,r,x;
		scanf("%d%d%d",&l,&r,&x);
		cnt_l++; cnt_r++;
		lq[cnt_l] = i;
		nxt_l[cnt_l] = head_l[l];
		head_l[l] = cnt_l;
		rx[cnt_r] = x;
		rq[cnt_r] = i;
		nxt_r[cnt_r] = head_r[r];
		head_r[r] = cnt_r;
	}
	for(int i=1;i<=n;i++) {
		p[i] = i;
		at[i] = i;
	}
	for(int i=k;i>=1;i--) {
		for(int j=head_r[i];j;j=nxt_r[j]) {
			int x = rx[j],qid = rq[j];
			v[qid] = p[x];
		}
		swap(p[a[i]],p[b[i]]);
		swap(at[p[a[i]]],at[p[b[i]]]);
		for(int j=head_l[i];j;j=nxt_l[j]) {
			int qid = lq[j];
			ans[qid] = at[v[qid]];
		}
	}
	for(int i=1;i<=q;i++)
		printf("%d\n",ans[i]);
	return 0;
}
0