oj.uz

Submission #1001506

# Submission time Handle Problem Language Result Execution time Memory
1001506 2024-06-19T05:01:54 Z amirhoseinfar1385 Sličnost (COI23_slicnost) C++17
50 / 100
 224 ms 400312 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){
		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);
		}
		int 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(int u){
	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){
	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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 394464 KB Output is correct
2 Correct 53 ms 394500 KB Output is correct
3 Correct 55 ms 394436 KB Output is correct
4 Correct 52 ms 394580 KB Output is correct
5 Correct 62 ms 394592 KB Output is correct
6 Correct 53 ms 394580 KB Output is correct
7 Correct 54 ms 394576 KB Output is correct
8 Correct 50 ms 394508 KB Output is correct
9 Correct 50 ms 394368 KB Output is correct
10 Correct 54 ms 394576 KB Output is correct
11 Correct 48 ms 394576 KB Output is correct
12 Correct 49 ms 394456 KB Output is correct
13 Correct 53 ms 394576 KB Output is correct
14 Correct 51 ms 394580 KB Output is correct
15 Correct 50 ms 394352 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 394464 KB Output is correct
2 Correct 53 ms 394500 KB Output is correct
3 Correct 55 ms 394436 KB Output is correct
4 Correct 52 ms 394580 KB Output is correct
5 Correct 62 ms 394592 KB Output is correct
6 Correct 53 ms 394580 KB Output is correct
7 Correct 54 ms 394576 KB Output is correct
8 Correct 50 ms 394508 KB Output is correct
9 Correct 50 ms 394368 KB Output is correct
10 Correct 54 ms 394576 KB Output is correct
11 Correct 48 ms 394576 KB Output is correct
12 Correct 49 ms 394456 KB Output is correct
13 Correct 53 ms 394576 KB Output is correct
14 Correct 51 ms 394580 KB Output is correct
15 Correct 50 ms 394352 KB Output is correct
16 Correct 57 ms 394696 KB Output is correct
17 Correct 52 ms 394832 KB Output is correct
18 Correct 53 ms 394576 KB Output is correct
19 Correct 55 ms 394648 KB Output is correct
20 Correct 63 ms 394772 KB Output is correct
21 Correct 62 ms 394756 KB Output is correct
22 Correct 54 ms 392412 KB Output is correct
23 Correct 58 ms 392788 KB Output is correct
24 Correct 63 ms 394648 KB Output is correct
25 Correct 57 ms 394632 KB Output is correct
26 Correct 57 ms 394576 KB Output is correct
27 Correct 58 ms 394832 KB Output is correct
28 Correct 54 ms 394560 KB Output is correct
29 Correct 56 ms 394576 KB Output is correct
30 Correct 53 ms 394576 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 394464 KB Output is correct
2 Correct 53 ms 394500 KB Output is correct
3 Correct 55 ms 394436 KB Output is correct
4 Correct 52 ms 394580 KB Output is correct
5 Correct 62 ms 394592 KB Output is correct
6 Correct 53 ms 394580 KB Output is correct
7 Correct 54 ms 394576 KB Output is correct
8 Correct 50 ms 394508 KB Output is correct
9 Correct 50 ms 394368 KB Output is correct
10 Correct 54 ms 394576 KB Output is correct
11 Correct 48 ms 394576 KB Output is correct
12 Correct 49 ms 394456 KB Output is correct
13 Correct 53 ms 394576 KB Output is correct
14 Correct 51 ms 394580 KB Output is correct
15 Correct 50 ms 394352 KB Output is correct
16 Correct 57 ms 394696 KB Output is correct
17 Correct 52 ms 394832 KB Output is correct
18 Correct 53 ms 394576 KB Output is correct
19 Correct 55 ms 394648 KB Output is correct
20 Correct 63 ms 394772 KB Output is correct
21 Correct 62 ms 394756 KB Output is correct
22 Correct 54 ms 392412 KB Output is correct
23 Correct 58 ms 392788 KB Output is correct
24 Correct 63 ms 394648 KB Output is correct
25 Correct 57 ms 394632 KB Output is correct
26 Correct 57 ms 394576 KB Output is correct
27 Correct 58 ms 394832 KB Output is correct
28 Correct 54 ms 394560 KB Output is correct
29 Correct 56 ms 394576 KB Output is correct
30 Correct 53 ms 394576 KB Output is correct
31 Correct 176 ms 400128 KB Output is correct
32 Correct 167 ms 400076 KB Output is correct
33 Correct 111 ms 395672 KB Output is correct
34 Correct 181 ms 397944 KB Output is correct
35 Correct 224 ms 400296 KB Output is correct
36 Correct 170 ms 399952 KB Output is correct
37 Correct 109 ms 395856 KB Output is correct
38 Correct 207 ms 399956 KB Output is correct
39 Correct 165 ms 400312 KB Output is correct
40 Correct 192 ms 398420 KB Output is correct
41 Correct 203 ms 398928 KB Output is correct
42 Correct 223 ms 399696 KB Output is correct
43 Correct 178 ms 398160 KB Output is correct
44 Correct 151 ms 397524 KB Output is correct
45 Correct 121 ms 393296 KB Output is correct

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 394464 KB Output is correct
2 Correct 53 ms 394500 KB Output is correct
3 Correct 55 ms 394436 KB Output is correct
4 Correct 52 ms 394580 KB Output is correct
5 Correct 62 ms 394592 KB Output is correct
6 Correct 53 ms 394580 KB Output is correct
7 Correct 54 ms 394576 KB Output is correct
8 Correct 50 ms 394508 KB Output is correct
9 Correct 50 ms 394368 KB Output is correct
10 Correct 54 ms 394576 KB Output is correct
11 Correct 48 ms 394576 KB Output is correct
12 Correct 49 ms 394456 KB Output is correct
13 Correct 53 ms 394576 KB Output is correct
14 Correct 51 ms 394580 KB Output is correct
15 Correct 50 ms 394352 KB Output is correct
16 Correct 51 ms 390736 KB Output is correct
17 Correct 50 ms 390488 KB Output is correct
18 Correct 54 ms 390480 KB Output is correct
19 Incorrect 55 ms 390480 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 394464 KB Output is correct
2 Correct 53 ms 394500 KB Output is correct
3 Correct 55 ms 394436 KB Output is correct
4 Correct 52 ms 394580 KB Output is correct
5 Correct 62 ms 394592 KB Output is correct
6 Correct 53 ms 394580 KB Output is correct
7 Correct 54 ms 394576 KB Output is correct
8 Correct 50 ms 394508 KB Output is correct
9 Correct 50 ms 394368 KB Output is correct
10 Correct 54 ms 394576 KB Output is correct
11 Correct 48 ms 394576 KB Output is correct
12 Correct 49 ms 394456 KB Output is correct
13 Correct 53 ms 394576 KB Output is correct
14 Correct 51 ms 394580 KB Output is correct
15 Correct 50 ms 394352 KB Output is correct
16 Correct 57 ms 394696 KB Output is correct
17 Correct 52 ms 394832 KB Output is correct
18 Correct 53 ms 394576 KB Output is correct
19 Correct 55 ms 394648 KB Output is correct
20 Correct 63 ms 394772 KB Output is correct
21 Correct 62 ms 394756 KB Output is correct
22 Correct 54 ms 392412 KB Output is correct
23 Correct 58 ms 392788 KB Output is correct
24 Correct 63 ms 394648 KB Output is correct
25 Correct 57 ms 394632 KB Output is correct
26 Correct 57 ms 394576 KB Output is correct
27 Correct 58 ms 394832 KB Output is correct
28 Correct 54 ms 394560 KB Output is correct
29 Correct 56 ms 394576 KB Output is correct
30 Correct 53 ms 394576 KB Output is correct
31 Correct 51 ms 390736 KB Output is correct
32 Correct 50 ms 390488 KB Output is correct
33 Correct 54 ms 390480 KB Output is correct
34 Incorrect 55 ms 390480 KB Output isn't correct
35 Halted 0 ms 0 KB -

Subtask #6
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 394464 KB Output is correct
2 Correct 53 ms 394500 KB Output is correct
3 Correct 55 ms 394436 KB Output is correct
4 Correct 52 ms 394580 KB Output is correct
5 Correct 62 ms 394592 KB Output is correct
6 Correct 53 ms 394580 KB Output is correct
7 Correct 54 ms 394576 KB Output is correct
8 Correct 50 ms 394508 KB Output is correct
9 Correct 50 ms 394368 KB Output is correct
10 Correct 54 ms 394576 KB Output is correct
11 Correct 48 ms 394576 KB Output is correct
12 Correct 49 ms 394456 KB Output is correct
13 Correct 53 ms 394576 KB Output is correct
14 Correct 51 ms 394580 KB Output is correct
15 Correct 50 ms 394352 KB Output is correct
16 Correct 57 ms 394696 KB Output is correct
17 Correct 52 ms 394832 KB Output is correct
18 Correct 53 ms 394576 KB Output is correct
19 Correct 55 ms 394648 KB Output is correct
20 Correct 63 ms 394772 KB Output is correct
21 Correct 62 ms 394756 KB Output is correct
22 Correct 54 ms 392412 KB Output is correct
23 Correct 58 ms 392788 KB Output is correct
24 Correct 63 ms 394648 KB Output is correct
25 Correct 57 ms 394632 KB Output is correct
26 Correct 57 ms 394576 KB Output is correct
27 Correct 58 ms 394832 KB Output is correct
28 Correct 54 ms 394560 KB Output is correct
29 Correct 56 ms 394576 KB Output is correct
30 Correct 53 ms 394576 KB Output is correct
31 Correct 176 ms 400128 KB Output is correct
32 Correct 167 ms 400076 KB Output is correct
33 Correct 111 ms 395672 KB Output is correct
34 Correct 181 ms 397944 KB Output is correct
35 Correct 224 ms 400296 KB Output is correct
36 Correct 170 ms 399952 KB Output is correct
37 Correct 109 ms 395856 KB Output is correct
38 Correct 207 ms 399956 KB Output is correct
39 Correct 165 ms 400312 KB Output is correct
40 Correct 192 ms 398420 KB Output is correct
41 Correct 203 ms 398928 KB Output is correct
42 Correct 223 ms 399696 KB Output is correct
43 Correct 178 ms 398160 KB Output is correct
44 Correct 151 ms 397524 KB Output is correct
45 Correct 121 ms 393296 KB Output is correct
46 Correct 51 ms 390736 KB Output is correct
47 Correct 50 ms 390488 KB Output is correct
48 Correct 54 ms 390480 KB Output is correct
49 Incorrect 55 ms 390480 KB Output isn't correct
50 Halted 0 ms 0 KB -