oj.uz

Submission #1001509

# Submission time Handle Problem Language Result Execution time Memory
1001509 2024-06-19T05:11:03 Z amirhoseinfar1385 Sličnost (COI23_slicnost) C++17
0 / 100
 126 ms 390488 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=300000+10,lg=19;
int n,k,q,inf=1e8;
int all[maxn],allb[maxn],lnk[maxn],allroot[maxn],root=0,kaf=(1<<lg);
set<pair<int,int>>st;
map<int,long long>mp;

struct segmentpersistant{
	struct node{
		int cl,cr,ted;
		int maxa,lazy;
		node(){
			ted=0;
			cl=cr=0;
			maxa=lazy=0;
		}
	};
	node seg[(1<<(lg+1))*lg];
	int te=1;
	pair<int,int>comp(pair<int,int>a,pair<int,int>b,int w){
		pair<int ,int> 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(int 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 ;
	}
	int upd(int i,int l,int r,int tl,int tr,int w){
		if(l>r||l>tr||r<tl||tl>tr){
			return i;
		}
		int 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;
		}
		int 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<int,int> pors(int i,int l,int r,int tl,int tr){
		return make_pair(seg[i].maxa+seg[i].lazy,seg[i].ted);
	}
}segper;

void ezaf(int u){
	if(u<k){
		return ;
	}
	pair<int,int>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(int u){
	if(u<k){
		return ;
	}
	pair<int,int>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(int i=1;i<=n;i++){
		cin>>all[i];
	}
	for(int i=1;i<=n;i++){
		cin>>allb[i];
		lnk[allb[i]]=i;
	}
}

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

void solve(){
	khor();
	for(int i=0;i<q;i++){
		int u;
		cin>>u;
		kam(u);
		root=allroot[u];
		root=segper.upd(root,0,kaf-1,max(lnk[all[u]]-k+1,1),lnk[all[u]],-1);
		root=segper.upd(root,0,kaf-1,max(lnk[all[u+1]]-k+1,1),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,1),lnk[all[u]],1);
			root=segper.upd(root,0,kaf-1,max(lnk[all[u+1]]-k+1,1),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.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 390480 KB Output is correct
2 Correct 120 ms 390480 KB Output is correct
3 Correct 126 ms 390432 KB Output is correct
4 Correct 122 ms 390484 KB Output is correct
5 Correct 124 ms 390484 KB Output is correct
6 Correct 122 ms 390480 KB Output is correct
7 Correct 126 ms 390292 KB Output is correct
8 Correct 125 ms 390488 KB Output is correct
9 Incorrect 121 ms 390480 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 390480 KB Output is correct
2 Correct 120 ms 390480 KB Output is correct
3 Correct 126 ms 390432 KB Output is correct
4 Correct 122 ms 390484 KB Output is correct
5 Correct 124 ms 390484 KB Output is correct
6 Correct 122 ms 390480 KB Output is correct
7 Correct 126 ms 390292 KB Output is correct
8 Correct 125 ms 390488 KB Output is correct
9 Incorrect 121 ms 390480 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 390480 KB Output is correct
2 Correct 120 ms 390480 KB Output is correct
3 Correct 126 ms 390432 KB Output is correct
4 Correct 122 ms 390484 KB Output is correct
5 Correct 124 ms 390484 KB Output is correct
6 Correct 122 ms 390480 KB Output is correct
7 Correct 126 ms 390292 KB Output is correct
8 Correct 125 ms 390488 KB Output is correct
9 Incorrect 121 ms 390480 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 390480 KB Output is correct
2 Correct 120 ms 390480 KB Output is correct
3 Correct 126 ms 390432 KB Output is correct
4 Correct 122 ms 390484 KB Output is correct
5 Correct 124 ms 390484 KB Output is correct
6 Correct 122 ms 390480 KB Output is correct
7 Correct 126 ms 390292 KB Output is correct
8 Correct 125 ms 390488 KB Output is correct
9 Incorrect 121 ms 390480 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 390480 KB Output is correct
2 Correct 120 ms 390480 KB Output is correct
3 Correct 126 ms 390432 KB Output is correct
4 Correct 122 ms 390484 KB Output is correct
5 Correct 124 ms 390484 KB Output is correct
6 Correct 122 ms 390480 KB Output is correct
7 Correct 126 ms 390292 KB Output is correct
8 Correct 125 ms 390488 KB Output is correct
9 Incorrect 121 ms 390480 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 390480 KB Output is correct
2 Correct 120 ms 390480 KB Output is correct
3 Correct 126 ms 390432 KB Output is correct
4 Correct 122 ms 390484 KB Output is correct
5 Correct 124 ms 390484 KB Output is correct
6 Correct 122 ms 390480 KB Output is correct
7 Correct 126 ms 390292 KB Output is correct
8 Correct 125 ms 390488 KB Output is correct
9 Incorrect 121 ms 390480 KB Output isn't correct
10 Halted 0 ms 0 KB -