結果

問題 No.1862 Copy and Paste
ユーザー vjudge1vjudge1
提出日時 2024-11-13 11:04:24
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,953 bytes
コンパイル時間 2,655 ms
コンパイル使用メモリ 220,560 KB
実行使用メモリ 94,300 KB
最終ジャッジ日時 2024-11-13 11:04:37
合計ジャッジ時間 13,172 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,q,a[N],b[N];
priority_queue<int> que[N]; 
set<int> s[N];
map<int,int> ma[N];
struct TREE {
	int l,r,val;
}tr[N<<2];
void pushup(int p) {
	tr[p].val=max(tr[p<<1].val,tr[p<<1|1].val);
}
void build(int p,int pl,int pr) {
	tr[p].l=pl; tr[p].r=pr;
	if(pl==pr) {
		tr[p].val=b[pl];
		return;
	}
	int mid=(pl+pr)>>1;
	build(p<<1,pl,mid);
	build(p<<1|1,mid+1,pr);
	pushup(p);
}
void init() {
	cin>>n>>q;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		s[a[i]].insert(i);
	}
	for(int i=0;i<=n+1;i++) {
		s[i].insert(0);
		s[i].insert(n+1);
	}
	for(int i=0;i<=n+1;i++) {
		int las=0;
		for(auto j:s[i]) {
			int dis=j-las-1;
			b[i]=max(b[i],dis);
			que[i].push(dis);
			las=j;
		}
	}
	build(1,0,n+1);
}
void update(int p,int L,int d) {
	if(tr[p].l==L&&L==tr[p].r) {
		tr[p].val=d;
		return;
	}
	int mid=(tr[p].l+tr[p].r)>>1;
	if(L<=mid) update(p<<1,L,d);
	else update(p<<1|1,L,d);
	pushup(p);
}
int query(int p,int x) {
//	cout<<p<<" "<<tr[p].l<<" "<<tr[p].r<<" "<<tr[p].val<<endl;
	if(tr[p].l==tr[p].r) return tr[p].l;
	int mid=(tr[p].l+tr[p].r)>>1;
	if(tr[p<<1].val>=x) return query(p<<1,x);
	else return query(p<<1|1,x);
}
void upd(int x,int y,int z) {
	auto op1=s[x].lower_bound(y),opp=op1; //??  
	int l=*(--opp),r;
	opp=op1; r=*(++opp);
	ma[x][y-l-1]++; ma[x][r-y-1]++;
	
	s[x].erase(y);
	s[x].insert(z);
	
	op1=s[x].lower_bound(z),opp=op1; //?? 
	l=*(--opp);
	opp=op1; r=*(++opp);
	que[x].push(z-l-1); que[x].push(r-z-1);
	
	while(ma[x][que[x].top()]) {
		ma[x][que[x].top()]--;
		que[x].pop();
	}
	update(1,x,que[x].top());
}
signed main() {
	ios::sync_with_stdio(false);
//	freopen("star.in","r",stdin);
//	freopen("star.out","w",stdout);
	init();
	while(q--) {
		int op,x;
		cin>>op>>x;
		if(op==1) {
			upd(a[x],x,x+1);
			upd(a[x+1],x+1,x);
			swap(a[x],a[x+1]);
//			cout<<"MAN "<<que[a[x+1]].top()<<" "<<que[a[x]].top()<<endl;
		} else {
			cout<<query(1,x)<<endl;
		}
	}
	return 0;
}
0