oj.uz

Submission #1001587

# Submission time Handle Problem Language Result Execution time Memory
1001587 2024-06-19T06:17:46 Z amirhoseinfar1385 Sličnost (COI23_slicnost) C++17
100 / 100
 1177 ms 520308 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,lg=17;
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;
const int sz=(lg+1)*maxn*29/2;
 
struct segmentpersistant{
	struct node{
		int cl,cr,ted;
		int maxa,lazy;
		node(){
			ted=0;
			cl=cr=0;
			maxa=lazy=0;
		}
	};
	node seg[sz];
	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(te==sz){
			exit(0);
		}
		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),min(n-k+1,lnk[all[i]]),1);
		if(i-k>=1){
			root=segper.upd(root,0,kaf-1,max(lnk[all[i-k]]-k+1,1),min(n-k+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),min(n-k+1,lnk[all[u]]),-1);
		root=segper.upd(root,0,kaf-1,max(lnk[all[u+1]]-k+1,1),min(n-k+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),min(n-k+1,lnk[all[u]]),1);
			root=segper.upd(root,0,kaf-1,max(lnk[all[u+1]]-k+1,1),min(n-k+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 217 ms 511084 KB Output is correct
2 Correct 173 ms 511056 KB Output is correct
3 Correct 180 ms 511056 KB Output is correct
4 Correct 175 ms 511024 KB Output is correct
5 Correct 165 ms 511060 KB Output is correct
6 Correct 173 ms 511024 KB Output is correct
7 Correct 171 ms 511060 KB Output is correct
8 Correct 156 ms 511064 KB Output is correct
9 Correct 163 ms 511152 KB Output is correct
10 Correct 167 ms 511320 KB Output is correct
11 Correct 158 ms 511056 KB Output is correct
12 Correct 162 ms 511244 KB Output is correct
13 Correct 164 ms 511056 KB Output is correct
14 Correct 168 ms 511184 KB Output is correct
15 Correct 167 ms 511132 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 511084 KB Output is correct
2 Correct 173 ms 511056 KB Output is correct
3 Correct 180 ms 511056 KB Output is correct
4 Correct 175 ms 511024 KB Output is correct
5 Correct 165 ms 511060 KB Output is correct
6 Correct 173 ms 511024 KB Output is correct
7 Correct 171 ms 511060 KB Output is correct
8 Correct 156 ms 511064 KB Output is correct
9 Correct 163 ms 511152 KB Output is correct
10 Correct 167 ms 511320 KB Output is correct
11 Correct 158 ms 511056 KB Output is correct
12 Correct 162 ms 511244 KB Output is correct
13 Correct 164 ms 511056 KB Output is correct
14 Correct 168 ms 511184 KB Output is correct
15 Correct 167 ms 511132 KB Output is correct
16 Correct 173 ms 511572 KB Output is correct
17 Correct 177 ms 511392 KB Output is correct
18 Correct 168 ms 511312 KB Output is correct
19 Correct 171 ms 511312 KB Output is correct
20 Correct 182 ms 511628 KB Output is correct
21 Correct 182 ms 511572 KB Output is correct
22 Correct 172 ms 511296 KB Output is correct
23 Correct 183 ms 511576 KB Output is correct
24 Correct 176 ms 511572 KB Output is correct
25 Correct 223 ms 511316 KB Output is correct
26 Correct 172 ms 511312 KB Output is correct
27 Correct 173 ms 511568 KB Output is correct
28 Correct 173 ms 511316 KB Output is correct
29 Correct 172 ms 511428 KB Output is correct
30 Correct 176 ms 511344 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 511084 KB Output is correct
2 Correct 173 ms 511056 KB Output is correct
3 Correct 180 ms 511056 KB Output is correct
4 Correct 175 ms 511024 KB Output is correct
5 Correct 165 ms 511060 KB Output is correct
6 Correct 173 ms 511024 KB Output is correct
7 Correct 171 ms 511060 KB Output is correct
8 Correct 156 ms 511064 KB Output is correct
9 Correct 163 ms 511152 KB Output is correct
10 Correct 167 ms 511320 KB Output is correct
11 Correct 158 ms 511056 KB Output is correct
12 Correct 162 ms 511244 KB Output is correct
13 Correct 164 ms 511056 KB Output is correct
14 Correct 168 ms 511184 KB Output is correct
15 Correct 167 ms 511132 KB Output is correct
16 Correct 173 ms 511572 KB Output is correct
17 Correct 177 ms 511392 KB Output is correct
18 Correct 168 ms 511312 KB Output is correct
19 Correct 171 ms 511312 KB Output is correct
20 Correct 182 ms 511628 KB Output is correct
21 Correct 182 ms 511572 KB Output is correct
22 Correct 172 ms 511296 KB Output is correct
23 Correct 183 ms 511576 KB Output is correct
24 Correct 176 ms 511572 KB Output is correct
25 Correct 223 ms 511316 KB Output is correct
26 Correct 172 ms 511312 KB Output is correct
27 Correct 173 ms 511568 KB Output is correct
28 Correct 173 ms 511316 KB Output is correct
29 Correct 172 ms 511428 KB Output is correct
30 Correct 176 ms 511344 KB Output is correct
31 Correct 260 ms 518404 KB Output is correct
32 Correct 300 ms 518224 KB Output is correct
33 Correct 211 ms 513872 KB Output is correct
34 Correct 285 ms 516176 KB Output is correct
35 Correct 355 ms 518736 KB Output is correct
36 Correct 266 ms 517968 KB Output is correct
37 Correct 241 ms 514136 KB Output is correct
38 Correct 340 ms 518224 KB Output is correct
39 Correct 289 ms 518640 KB Output is correct
40 Correct 338 ms 516688 KB Output is correct
41 Correct 372 ms 517200 KB Output is correct
42 Correct 369 ms 517968 KB Output is correct
43 Correct 296 ms 516164 KB Output is correct
44 Correct 278 ms 515592 KB Output is correct
45 Correct 232 ms 514128 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 511084 KB Output is correct
2 Correct 173 ms 511056 KB Output is correct
3 Correct 180 ms 511056 KB Output is correct
4 Correct 175 ms 511024 KB Output is correct
5 Correct 165 ms 511060 KB Output is correct
6 Correct 173 ms 511024 KB Output is correct
7 Correct 171 ms 511060 KB Output is correct
8 Correct 156 ms 511064 KB Output is correct
9 Correct 163 ms 511152 KB Output is correct
10 Correct 167 ms 511320 KB Output is correct
11 Correct 158 ms 511056 KB Output is correct
12 Correct 162 ms 511244 KB Output is correct
13 Correct 164 ms 511056 KB Output is correct
14 Correct 168 ms 511184 KB Output is correct
15 Correct 167 ms 511132 KB Output is correct
16 Correct 180 ms 511056 KB Output is correct
17 Correct 184 ms 511060 KB Output is correct
18 Correct 184 ms 511060 KB Output is correct
19 Correct 188 ms 511016 KB Output is correct
20 Correct 175 ms 511316 KB Output is correct
21 Correct 183 ms 511056 KB Output is correct
22 Correct 191 ms 511056 KB Output is correct
23 Correct 180 ms 511272 KB Output is correct
24 Correct 180 ms 511060 KB Output is correct
25 Correct 186 ms 511040 KB Output is correct
26 Correct 180 ms 511060 KB Output is correct
27 Correct 180 ms 511220 KB Output is correct
28 Correct 190 ms 511056 KB Output is correct
29 Correct 181 ms 511232 KB Output is correct
30 Correct 179 ms 511052 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 511084 KB Output is correct
2 Correct 173 ms 511056 KB Output is correct
3 Correct 180 ms 511056 KB Output is correct
4 Correct 175 ms 511024 KB Output is correct
5 Correct 165 ms 511060 KB Output is correct
6 Correct 173 ms 511024 KB Output is correct
7 Correct 171 ms 511060 KB Output is correct
8 Correct 156 ms 511064 KB Output is correct
9 Correct 163 ms 511152 KB Output is correct
10 Correct 167 ms 511320 KB Output is correct
11 Correct 158 ms 511056 KB Output is correct
12 Correct 162 ms 511244 KB Output is correct
13 Correct 164 ms 511056 KB Output is correct
14 Correct 168 ms 511184 KB Output is correct
15 Correct 167 ms 511132 KB Output is correct
16 Correct 173 ms 511572 KB Output is correct
17 Correct 177 ms 511392 KB Output is correct
18 Correct 168 ms 511312 KB Output is correct
19 Correct 171 ms 511312 KB Output is correct
20 Correct 182 ms 511628 KB Output is correct
21 Correct 182 ms 511572 KB Output is correct
22 Correct 172 ms 511296 KB Output is correct
23 Correct 183 ms 511576 KB Output is correct
24 Correct 176 ms 511572 KB Output is correct
25 Correct 223 ms 511316 KB Output is correct
26 Correct 172 ms 511312 KB Output is correct
27 Correct 173 ms 511568 KB Output is correct
28 Correct 173 ms 511316 KB Output is correct
29 Correct 172 ms 511428 KB Output is correct
30 Correct 176 ms 511344 KB Output is correct
31 Correct 180 ms 511056 KB Output is correct
32 Correct 184 ms 511060 KB Output is correct
33 Correct 184 ms 511060 KB Output is correct
34 Correct 188 ms 511016 KB Output is correct
35 Correct 175 ms 511316 KB Output is correct
36 Correct 183 ms 511056 KB Output is correct
37 Correct 191 ms 511056 KB Output is correct
38 Correct 180 ms 511272 KB Output is correct
39 Correct 180 ms 511060 KB Output is correct
40 Correct 186 ms 511040 KB Output is correct
41 Correct 180 ms 511060 KB Output is correct
42 Correct 180 ms 511220 KB Output is correct
43 Correct 190 ms 511056 KB Output is correct
44 Correct 181 ms 511232 KB Output is correct
45 Correct 179 ms 511052 KB Output is correct
46 Correct 195 ms 511572 KB Output is correct
47 Correct 189 ms 511580 KB Output is correct
48 Correct 178 ms 511332 KB Output is correct
49 Correct 195 ms 511312 KB Output is correct
50 Correct 206 ms 511572 KB Output is correct
51 Correct 182 ms 511312 KB Output is correct
52 Correct 219 ms 511572 KB Output is correct
53 Correct 221 ms 511508 KB Output is correct
54 Correct 202 ms 511572 KB Output is correct
55 Correct 183 ms 511460 KB Output is correct
56 Correct 190 ms 511568 KB Output is correct
57 Correct 204 ms 511544 KB Output is correct
58 Correct 210 ms 511312 KB Output is correct
59 Correct 198 ms 511568 KB Output is correct
60 Correct 199 ms 511316 KB Output is correct

Subtask #6
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 511084 KB Output is correct
2 Correct 173 ms 511056 KB Output is correct
3 Correct 180 ms 511056 KB Output is correct
4 Correct 175 ms 511024 KB Output is correct
5 Correct 165 ms 511060 KB Output is correct
6 Correct 173 ms 511024 KB Output is correct
7 Correct 171 ms 511060 KB Output is correct
8 Correct 156 ms 511064 KB Output is correct
9 Correct 163 ms 511152 KB Output is correct
10 Correct 167 ms 511320 KB Output is correct
11 Correct 158 ms 511056 KB Output is correct
12 Correct 162 ms 511244 KB Output is correct
13 Correct 164 ms 511056 KB Output is correct
14 Correct 168 ms 511184 KB Output is correct
15 Correct 167 ms 511132 KB Output is correct
16 Correct 173 ms 511572 KB Output is correct
17 Correct 177 ms 511392 KB Output is correct
18 Correct 168 ms 511312 KB Output is correct
19 Correct 171 ms 511312 KB Output is correct
20 Correct 182 ms 511628 KB Output is correct
21 Correct 182 ms 511572 KB Output is correct
22 Correct 172 ms 511296 KB Output is correct
23 Correct 183 ms 511576 KB Output is correct
24 Correct 176 ms 511572 KB Output is correct
25 Correct 223 ms 511316 KB Output is correct
26 Correct 172 ms 511312 KB Output is correct
27 Correct 173 ms 511568 KB Output is correct
28 Correct 173 ms 511316 KB Output is correct
29 Correct 172 ms 511428 KB Output is correct
30 Correct 176 ms 511344 KB Output is correct
31 Correct 260 ms 518404 KB Output is correct
32 Correct 300 ms 518224 KB Output is correct
33 Correct 211 ms 513872 KB Output is correct
34 Correct 285 ms 516176 KB Output is correct
35 Correct 355 ms 518736 KB Output is correct
36 Correct 266 ms 517968 KB Output is correct
37 Correct 241 ms 514136 KB Output is correct
38 Correct 340 ms 518224 KB Output is correct
39 Correct 289 ms 518640 KB Output is correct
40 Correct 338 ms 516688 KB Output is correct
41 Correct 372 ms 517200 KB Output is correct
42 Correct 369 ms 517968 KB Output is correct
43 Correct 296 ms 516164 KB Output is correct
44 Correct 278 ms 515592 KB Output is correct
45 Correct 232 ms 514128 KB Output is correct
46 Correct 180 ms 511056 KB Output is correct
47 Correct 184 ms 511060 KB Output is correct
48 Correct 184 ms 511060 KB Output is correct
49 Correct 188 ms 511016 KB Output is correct
50 Correct 175 ms 511316 KB Output is correct
51 Correct 183 ms 511056 KB Output is correct
52 Correct 191 ms 511056 KB Output is correct
53 Correct 180 ms 511272 KB Output is correct
54 Correct 180 ms 511060 KB Output is correct
55 Correct 186 ms 511040 KB Output is correct
56 Correct 180 ms 511060 KB Output is correct
57 Correct 180 ms 511220 KB Output is correct
58 Correct 190 ms 511056 KB Output is correct
59 Correct 181 ms 511232 KB Output is correct
60 Correct 179 ms 511052 KB Output is correct
61 Correct 195 ms 511572 KB Output is correct
62 Correct 189 ms 511580 KB Output is correct
63 Correct 178 ms 511332 KB Output is correct
64 Correct 195 ms 511312 KB Output is correct
65 Correct 206 ms 511572 KB Output is correct
66 Correct 182 ms 511312 KB Output is correct
67 Correct 219 ms 511572 KB Output is correct
68 Correct 221 ms 511508 KB Output is correct
69 Correct 202 ms 511572 KB Output is correct
70 Correct 183 ms 511460 KB Output is correct
71 Correct 190 ms 511568 KB Output is correct
72 Correct 204 ms 511544 KB Output is correct
73 Correct 210 ms 511312 KB Output is correct
74 Correct 198 ms 511568 KB Output is correct
75 Correct 199 ms 511316 KB Output is correct
76 Correct 605 ms 520308 KB Output is correct
77 Correct 706 ms 519504 KB Output is correct
78 Correct 279 ms 515152 KB Output is correct
79 Correct 726 ms 517368 KB Output is correct
80 Correct 1042 ms 519868 KB Output is correct
81 Correct 357 ms 516024 KB Output is correct
82 Correct 583 ms 518728 KB Output is correct
83 Correct 1010 ms 519440 KB Output is correct
84 Correct 777 ms 520276 KB Output is correct
85 Correct 424 ms 517456 KB Output is correct
86 Correct 1177 ms 519504 KB Output is correct
87 Correct 1106 ms 519256 KB Output is correct
88 Correct 469 ms 516432 KB Output is correct
89 Correct 1004 ms 518736 KB Output is correct
90 Correct 462 ms 516276 KB Output is correct