Submission #1001500

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001500		amirhoseinfar1385	Sličnost (COI23_slicnost)	C++17	0 / 100	66 ms	524288 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const long long maxn=300000+10,lg=19;
long long n,k,q,inf=1e8;
long long all[maxn],allb[maxn],lnk[maxn],allroot[maxn],root=0,kaf=(1<<lg);
set<pair<long long,long long>>st;
map<long long,long long>mp;

struct segmentpersistant{
	struct node{
		long long cl,cr,maxa,lazy,ted;
		node(){
			ted=0;
			cl=cr=0;
			maxa=lazy=0;
		}
	};
	node seg[(1<<(lg+1))*lg];
	long long te=1;
	pair<long long,long long>comp(pair<long long,long long>a,pair<long long,long long>b,long long w){
		pair<long long ,long long> ret=a;
		if(b.first==a.first){
			ret.second+=b.second;
		}else if(b.first>a.first){
			ret=b;
		}
		ret.first+=w;
		return ret;
	}
	void calc(long long u,int l,int r){
		int len=r-l+1;
		len/=2;
		seg[u].ted=0;
		seg[u].maxa=max(seg[seg[u].cl].maxa+seg[seg[u].cl].lazy,seg[seg[u].cr].maxa+seg[seg[u].cr].lazy);
		if(seg[seg[u].cl].maxa+seg[seg[u].cl].lazy==seg[u].maxa){
			seg[u].ted+=seg[seg[u].cl].ted;
		}
		if(seg[seg[u].cr].maxa+seg[seg[u].cr].lazy==seg[u].maxa){
			seg[u].ted+=seg[seg[u].cr].ted;
		}
		if(seg[u].maxa==0){
			if(seg[u].cl==0){
				seg[u].ted+=len;
			}
			if(seg[u].cr==0){
				seg[u].ted+=len;
			}
		}
		return ;
	}
	long long upd(long long i,long long l,long long r,long long tl,long long tr,long long w){
		if(l>r||l>tr||r<tl||tl>tr){
			return i;
		}
		long long u=te;
		seg[te]=seg[i];
		te++;
		if(l>=tl&&r<=tr){
			seg[u].lazy+=w;
			if(seg[u].cl==0&&seg[u].cr==0){
				seg[u].ted=r-l+1;
			}
			return u;
		}
		long long m=(l+r)>>1;
		seg[u].cl=upd(seg[u].cl,l,m,tl,tr,w);
		seg[u].cr=upd(seg[u].cr,m+1,r,tl,tr,w);
		calc(u,l,r);
		return u;
	}
	pair<long long,long long> pors(long long i,long long l,long long r,long long tl,long long tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return make_pair(-inf,0);
		}
		if(l>=tl&&r<=tr){
			if(i==0){
				return make_pair(0,r-l+1);
			}
			return make_pair(seg[i].maxa+seg[i].lazy,seg[i].ted);
		}
		long long m=(l+r)>>1;
		return comp(pors(seg[i].cl,l,m,tl,tr),pors(seg[i].cr,m+1,r,tl,tr),seg[i].lazy);
	}
}segper;

void ezaf(long long u){
	pair<long long,long long>z=segper.pors(allroot[u],0,kaf-1,1,n-k+1);
	st.insert(make_pair(z.first,u));
	mp[z.first]+=z.second;
	//cout<<"ziad: "<<u<<" "<<z.first<<" "<<z.second<<endl;
}

void kam(long long u){
	pair<long long,long long>z=segper.pors(allroot[u],0,kaf-1,1,n-k+1);
	st.erase(make_pair(z.first,u));
	mp[z.first]-=z.second;
	//cout<<"kam: "<<u<<" "<<z.first<<" "<<z.second<<endl;
}

void khor(){
	auto x=(*st.rbegin());
	cout<<x.first<<" "<<mp[x.first]<<"\n";
}

void vorod(){
	cin>>n>>k>>q;
	for(long long i=1;i<=n;i++){
		cin>>all[i];
	}
	for(long long i=1;i<=n;i++){
		cin>>allb[i];
		lnk[allb[i]]=i;
	}
}

void pre(){
	for(long long i=1;i<=n;i++){
		root=segper.upd(root,0,kaf-1,max(lnk[all[i]]-k+1,1ll),lnk[all[i]],1);
		if(i-k>=1){
			root=segper.upd(root,0,kaf-1,max(lnk[all[i-k]]-k+1,1ll),lnk[all[i-k]],-1);
		}
		allroot[i]=root;
		if(i>=k){
			ezaf(i);
		}
	}
}

void solve(){
	khor();
	for(long long i=0;i<q;i++){
		long long u;
		cin>>u;
		kam(u);
		root=allroot[u];
		root=segper.upd(root,0,kaf-1,max(lnk[all[u]]-k+1,1ll),lnk[all[u]],-1);
		root=segper.upd(root,0,kaf-1,max(lnk[all[u+1]]-k+1,1ll),lnk[all[u+1]],1);
		allroot[u]=root;
		ezaf(u);
		if(u+k<=n){
			kam(u+k);
			root=allroot[u+k];
			root=segper.upd(root,0,kaf-1,max(lnk[all[u]]-k+1,1ll),lnk[all[u]],1);
			root=segper.upd(root,0,kaf-1,max(lnk[all[u+1]]-k+1,1ll),lnk[all[u+1]],-1);
			allroot[u+k]=root;
			ezaf(u+k);
		}
		swap(all[u],all[u+1]);
		khor();
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen("inp.txt","r",stdin);
	vorod();
	pre();
	solve();
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 33
• Subtask 4: 0 / 7
• Subtask 5: 0 / 10
• Subtask 6: 0 / 33