結果

問題 No.2002 Range Swap Query
コンテスト
ユーザー vjudge1
提出日時 2025-10-01 11:33:33
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 629 ms / 2,000 ms
コード長 1,281 bytes
コンパイル時間 1,768 ms
コンパイル使用メモリ 164,148 KB
実行使用メモリ 102,064 KB
最終ジャッジ日時 2025-10-01 11:33:45
合計ジャッジ時間 10,131 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define INF 1e18
#define int long long
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define Rep(i,l,r) for(int i=(l);i>=(r);--i)
#define gc getchar()
#define pii pair<int,int> 
#define mp(x,y) make_pair((x),(y))
using namespace std;
namespace fastIO{
	int read(){
		int x=0,f=1;char ch=gc;
		while(ch<'0'||ch>'9'){
			if(ch=='-') f=-1;
			ch=gc;
		}
		while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc;
		return x*f;
	}
}
using namespace fastIO;
int n,m,q;
int a[1000009],b[1000009];
vector<pii> pos[1000009];
int nw[1000009];
int l[1000009],r[1000009],k[1000009];
vector<int> qr[1000009];
int ans[1000009];
signed main(){
//	freopen("perm.in","r",stdin);
// 	freopen("perm.out","w",stdout);
	n=read(),m=read(),q=read();
	rep(i,1,n){
		pos[i].push_back(mp(0LL,i));
		nw[i]=i;
	}
	rep(i,1,m){
		a[i]=read(),b[i]=read();
		swap(nw[a[i]],nw[b[i]]);
		pos[nw[a[i]]].push_back(mp(i,a[i]));
		pos[nw[b[i]]].push_back(mp(i,b[i]));
	}
	rep(i,1,q){
		l[i]=read(),r[i]=read(),k[i]=read();
		qr[r[i]].push_back(i);
	}
	rep(i,1,n) nw[i]=i;
	rep(i,1,m){
		swap(nw[a[i]],nw[b[i]]);
		for(auto u:qr[i]){
			 int np=nw[k[u]];
			 auto pt=lower_bound(pos[np].begin(),pos[np].end(),mp(l[u],0LL));
			 pt--;
			ans[u]=pt->second;
		}
	}
	rep(i,1,q) cout<<ans[i]<<endl;
	return 0;
}
0