Submission #791763

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
791763	2023-07-24T09:41:04 Z	이종영(#10079)	Sličnost (COI23_slicnost)	C++17	Compilation error	0 ms	0 KB

Main

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
using ll=long long;
using pll=array<ll,2>;
const ll inf=1e18;
const int N=1e5+5,M=1e8+5;
pll mrg(pll L,pll R){
	if(L[0]<R[0]) swap(L,R);
	if(L[0]==R[0]) return {L[0],L[1]+R[1]};
	return L;
}
struct node{
	pll v={0,0}; int d=0;
	int l=0,r=0;
}T[M]; int C=1;
void init(int nd,int l,int r){
	T[nd].v={0,r-l+1};
	T[nd].d=0;
	if(l==r) return;
	int m=(l+r)>>1;
	T[nd].l=++C;
	T[nd].r=++C;
	init(T[nd].l,l,m); init(T[nd].r,m+1,r);
}
void upd(int n1,int n2,int l,int r,int s,int e,int v){
	T[n2]=T[n1];
	if(r<s||e<l) return;
	if(s<=l&&r<=e){
		T[n2].v[0]+=v;
		T[n2].d+=v;
		return;
	}
	int m=(l+r)>>1;
	T[n2].l=++C;
	T[n2].r=++C;
	upd(T[n1].l,T[n2].l,l,m,s,e,v); upd(T[n1].r,T[n2].r,m+1,r,s,e,v);
	T[n2].v=mrg(T[T[n2].l].v,T[T[n2].r].v);
	T[n2].v[0]+=T[n2].d;
}
int n,k,q,a[N],b[N],invb[N],t[N];
int root[N];
map<int,ll> mp;
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>k>>q;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		cin>>b[i];
		invb[b[i]]=i;
	}
	root[0]=1;
	init(1,1,n-k+1);
	for(int x=1;x<=n-k+1;x++){
		root[x]=++C;
		T[root[x]]=T[root[x-1]];
		if(x==1){
			for(int i=1;i<=k;i++){
				int j=invb[a[i]];
				int nroot=++C;
				upd(root[x],nroot,1,n-k+1,max(1,j-k+1),min(j,n-k+1),1);
				root[x]=nroot;
			}
		} else{
			int j=invb[a[x+k-1]];
			int nroot=++C;
			upd(root[x],nroot,1,n-k+1,max(1,j-k+1),min(j,n-k+1),1);
			root[x]=nroot;
			{
				int j=invb[a[x-1]];
				int nroot=++C;
				upd(root[x],nroot,1,n-k+1,max(1,j-k+1),min(j,n-k+1),-1);
				root[x]=nroot;
			}
		}
		mp[T[root[x]].v[0]]+=T[root[x]].v[1];
	}
	{
		pair<int,ll> ans=*mp.rbegin();
		cout<<ans.first<<" "<<ans.second<<"\n";
	}
	for(int i=1;i<=q;i++){
		cin>>t[i];
		if(k<=t[i]){
			mp[T[root[t[i]-k+1]].v[0]]-=T[root[t[i]-k+1]].v[1];
			int nroot=++C,j=invb[a[t[i]]];
			upd(root[t[i]-k+1],nroot,1,n-k+1,max(1,j-k+1),min(j,n-k+1),-1);
			root[t[i]-k+1]=nroot;
			nroot=++C; j=invb[a[t[i]+1]];
			upd(root[t[i]-k+1],nroot,1,n-k+1,max(1,j-k+1),min(j,n-k+1),1);
			root[t[i]-k+1]=nroot;
			mp[T[root[t[i]-k+1]].v[0]]+=T[root[t[i]-k+1]].v[1];
		}
		if(t[i]<=n-k){
			mp[T[root[t[i]+1]].v[0]]-=T[root[t[i]+1]].v[1];
			int nroot=++C,j=invb[a[t[i]]];
			upd(root[t[i]+1],nroot,1,n-k+1,max(1,j-k+1),min(j,n-k+1),1);
			root[t[i]+1]=nroot;
			nroot=++C; j=invb[a[t[i]+1]];
			upd(root[t[i]+1],nroot,1,n-k+1,max(1,j-k+1),min(j,n-k+1),-1);
			root[t[i]+1]=nroot;
			mp[T[root[t[i]+1]].v[0]]+=T[root[t[i]+1]].v[1];
		}
		swap(a[t[i]],a[t[i]+1]);
		{
			pair<int,ll> ans=*mp.rbegin();
			while(ans.second==0){
				mp.erase(ans.first);
				ans=*mp.rbegin();
			}
			cout<<ans.first<<" "<<ans.second<<"\n";
		}
	}
	return 0;
}

Compilation message

/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status