oj.uz

Submission #1001582

# Submission time Handle Problem Language Result Execution time Memory
1001582 2024-06-19T06:13:56 Z amirhoseinfar1385 Sličnost (COI23_slicnost) C++17
67 / 100
 2551 ms 524292 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*13;
 
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){
			assert(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 170 ms 458328 KB Output is correct
2 Correct 153 ms 458336 KB Output is correct
3 Correct 175 ms 458324 KB Output is correct
4 Correct 181 ms 458328 KB Output is correct
5 Correct 168 ms 458332 KB Output is correct
6 Correct 169 ms 458592 KB Output is correct
7 Correct 158 ms 458324 KB Output is correct
8 Correct 155 ms 458332 KB Output is correct
9 Correct 161 ms 458332 KB Output is correct
10 Correct 165 ms 458328 KB Output is correct
11 Correct 155 ms 458320 KB Output is correct
12 Correct 157 ms 458320 KB Output is correct
13 Correct 156 ms 458336 KB Output is correct
14 Correct 161 ms 458388 KB Output is correct
15 Correct 161 ms 458224 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 458328 KB Output is correct
2 Correct 153 ms 458336 KB Output is correct
3 Correct 175 ms 458324 KB Output is correct
4 Correct 181 ms 458328 KB Output is correct
5 Correct 168 ms 458332 KB Output is correct
6 Correct 169 ms 458592 KB Output is correct
7 Correct 158 ms 458324 KB Output is correct
8 Correct 155 ms 458332 KB Output is correct
9 Correct 161 ms 458332 KB Output is correct
10 Correct 165 ms 458328 KB Output is correct
11 Correct 155 ms 458320 KB Output is correct
12 Correct 157 ms 458320 KB Output is correct
13 Correct 156 ms 458336 KB Output is correct
14 Correct 161 ms 458388 KB Output is correct
15 Correct 161 ms 458224 KB Output is correct
16 Correct 165 ms 458584 KB Output is correct
17 Correct 160 ms 458648 KB Output is correct
18 Correct 167 ms 458540 KB Output is correct
19 Correct 173 ms 458576 KB Output is correct
20 Correct 166 ms 458752 KB Output is correct
21 Correct 162 ms 458704 KB Output is correct
22 Correct 155 ms 458420 KB Output is correct
23 Correct 169 ms 458636 KB Output is correct
24 Correct 166 ms 458576 KB Output is correct
25 Correct 162 ms 458572 KB Output is correct
26 Correct 169 ms 458468 KB Output is correct
27 Correct 167 ms 458556 KB Output is correct
28 Correct 164 ms 458432 KB Output is correct
29 Correct 175 ms 458492 KB Output is correct
30 Correct 157 ms 458340 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 458328 KB Output is correct
2 Correct 153 ms 458336 KB Output is correct
3 Correct 175 ms 458324 KB Output is correct
4 Correct 181 ms 458328 KB Output is correct
5 Correct 168 ms 458332 KB Output is correct
6 Correct 169 ms 458592 KB Output is correct
7 Correct 158 ms 458324 KB Output is correct
8 Correct 155 ms 458332 KB Output is correct
9 Correct 161 ms 458332 KB Output is correct
10 Correct 165 ms 458328 KB Output is correct
11 Correct 155 ms 458320 KB Output is correct
12 Correct 157 ms 458320 KB Output is correct
13 Correct 156 ms 458336 KB Output is correct
14 Correct 161 ms 458388 KB Output is correct
15 Correct 161 ms 458224 KB Output is correct
16 Correct 165 ms 458584 KB Output is correct
17 Correct 160 ms 458648 KB Output is correct
18 Correct 167 ms 458540 KB Output is correct
19 Correct 173 ms 458576 KB Output is correct
20 Correct 166 ms 458752 KB Output is correct
21 Correct 162 ms 458704 KB Output is correct
22 Correct 155 ms 458420 KB Output is correct
23 Correct 169 ms 458636 KB Output is correct
24 Correct 166 ms 458576 KB Output is correct
25 Correct 162 ms 458572 KB Output is correct
26 Correct 169 ms 458468 KB Output is correct
27 Correct 167 ms 458556 KB Output is correct
28 Correct 164 ms 458432 KB Output is correct
29 Correct 175 ms 458492 KB Output is correct
30 Correct 157 ms 458340 KB Output is correct
31 Correct 231 ms 465584 KB Output is correct
32 Correct 262 ms 465516 KB Output is correct
33 Correct 195 ms 460884 KB Output is correct
34 Correct 270 ms 463328 KB Output is correct
35 Correct 316 ms 465748 KB Output is correct
36 Correct 239 ms 465232 KB Output is correct
37 Correct 203 ms 461344 KB Output is correct
38 Correct 301 ms 465732 KB Output is correct
39 Correct 241 ms 465744 KB Output is correct
40 Correct 276 ms 463612 KB Output is correct
41 Correct 300 ms 464212 KB Output is correct
42 Correct 300 ms 464976 KB Output is correct
43 Correct 288 ms 463444 KB Output is correct
44 Correct 246 ms 462928 KB Output is correct
45 Correct 205 ms 461328 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 458328 KB Output is correct
2 Correct 153 ms 458336 KB Output is correct
3 Correct 175 ms 458324 KB Output is correct
4 Correct 181 ms 458328 KB Output is correct
5 Correct 168 ms 458332 KB Output is correct
6 Correct 169 ms 458592 KB Output is correct
7 Correct 158 ms 458324 KB Output is correct
8 Correct 155 ms 458332 KB Output is correct
9 Correct 161 ms 458332 KB Output is correct
10 Correct 165 ms 458328 KB Output is correct
11 Correct 155 ms 458320 KB Output is correct
12 Correct 157 ms 458320 KB Output is correct
13 Correct 156 ms 458336 KB Output is correct
14 Correct 161 ms 458388 KB Output is correct
15 Correct 161 ms 458224 KB Output is correct
16 Correct 156 ms 458364 KB Output is correct
17 Correct 156 ms 458324 KB Output is correct
18 Correct 148 ms 458580 KB Output is correct
19 Correct 164 ms 458328 KB Output is correct
20 Correct 161 ms 458316 KB Output is correct
21 Correct 170 ms 458320 KB Output is correct
22 Correct 165 ms 458252 KB Output is correct
23 Correct 162 ms 458320 KB Output is correct
24 Correct 155 ms 458324 KB Output is correct
25 Correct 156 ms 458320 KB Output is correct
26 Correct 166 ms 458324 KB Output is correct
27 Correct 160 ms 458428 KB Output is correct
28 Correct 164 ms 458320 KB Output is correct
29 Correct 163 ms 458216 KB Output is correct
30 Correct 169 ms 458324 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 458328 KB Output is correct
2 Correct 153 ms 458336 KB Output is correct
3 Correct 175 ms 458324 KB Output is correct
4 Correct 181 ms 458328 KB Output is correct
5 Correct 168 ms 458332 KB Output is correct
6 Correct 169 ms 458592 KB Output is correct
7 Correct 158 ms 458324 KB Output is correct
8 Correct 155 ms 458332 KB Output is correct
9 Correct 161 ms 458332 KB Output is correct
10 Correct 165 ms 458328 KB Output is correct
11 Correct 155 ms 458320 KB Output is correct
12 Correct 157 ms 458320 KB Output is correct
13 Correct 156 ms 458336 KB Output is correct
14 Correct 161 ms 458388 KB Output is correct
15 Correct 161 ms 458224 KB Output is correct
16 Correct 165 ms 458584 KB Output is correct
17 Correct 160 ms 458648 KB Output is correct
18 Correct 167 ms 458540 KB Output is correct
19 Correct 173 ms 458576 KB Output is correct
20 Correct 166 ms 458752 KB Output is correct
21 Correct 162 ms 458704 KB Output is correct
22 Correct 155 ms 458420 KB Output is correct
23 Correct 169 ms 458636 KB Output is correct
24 Correct 166 ms 458576 KB Output is correct
25 Correct 162 ms 458572 KB Output is correct
26 Correct 169 ms 458468 KB Output is correct
27 Correct 167 ms 458556 KB Output is correct
28 Correct 164 ms 458432 KB Output is correct
29 Correct 175 ms 458492 KB Output is correct
30 Correct 157 ms 458340 KB Output is correct
31 Correct 156 ms 458364 KB Output is correct
32 Correct 156 ms 458324 KB Output is correct
33 Correct 148 ms 458580 KB Output is correct
34 Correct 164 ms 458328 KB Output is correct
35 Correct 161 ms 458316 KB Output is correct
36 Correct 170 ms 458320 KB Output is correct
37 Correct 165 ms 458252 KB Output is correct
38 Correct 162 ms 458320 KB Output is correct
39 Correct 155 ms 458324 KB Output is correct
40 Correct 156 ms 458320 KB Output is correct
41 Correct 166 ms 458324 KB Output is correct
42 Correct 160 ms 458428 KB Output is correct
43 Correct 164 ms 458320 KB Output is correct
44 Correct 163 ms 458216 KB Output is correct
45 Correct 169 ms 458324 KB Output is correct
46 Correct 180 ms 458588 KB Output is correct
47 Correct 181 ms 458604 KB Output is correct
48 Correct 166 ms 458580 KB Output is correct
49 Correct 171 ms 458588 KB Output is correct
50 Correct 180 ms 458832 KB Output is correct
51 Correct 174 ms 458580 KB Output is correct
52 Correct 174 ms 458580 KB Output is correct
53 Correct 196 ms 458784 KB Output is correct
54 Correct 190 ms 459068 KB Output is correct
55 Correct 172 ms 458576 KB Output is correct
56 Correct 185 ms 458836 KB Output is correct
57 Correct 181 ms 459012 KB Output is correct
58 Correct 176 ms 458580 KB Output is correct
59 Correct 185 ms 458644 KB Output is correct
60 Correct 182 ms 458580 KB Output is correct

Subtask #6
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 458328 KB Output is correct
2 Correct 153 ms 458336 KB Output is correct
3 Correct 175 ms 458324 KB Output is correct
4 Correct 181 ms 458328 KB Output is correct
5 Correct 168 ms 458332 KB Output is correct
6 Correct 169 ms 458592 KB Output is correct
7 Correct 158 ms 458324 KB Output is correct
8 Correct 155 ms 458332 KB Output is correct
9 Correct 161 ms 458332 KB Output is correct
10 Correct 165 ms 458328 KB Output is correct
11 Correct 155 ms 458320 KB Output is correct
12 Correct 157 ms 458320 KB Output is correct
13 Correct 156 ms 458336 KB Output is correct
14 Correct 161 ms 458388 KB Output is correct
15 Correct 161 ms 458224 KB Output is correct
16 Correct 165 ms 458584 KB Output is correct
17 Correct 160 ms 458648 KB Output is correct
18 Correct 167 ms 458540 KB Output is correct
19 Correct 173 ms 458576 KB Output is correct
20 Correct 166 ms 458752 KB Output is correct
21 Correct 162 ms 458704 KB Output is correct
22 Correct 155 ms 458420 KB Output is correct
23 Correct 169 ms 458636 KB Output is correct
24 Correct 166 ms 458576 KB Output is correct
25 Correct 162 ms 458572 KB Output is correct
26 Correct 169 ms 458468 KB Output is correct
27 Correct 167 ms 458556 KB Output is correct
28 Correct 164 ms 458432 KB Output is correct
29 Correct 175 ms 458492 KB Output is correct
30 Correct 157 ms 458340 KB Output is correct
31 Correct 231 ms 465584 KB Output is correct
32 Correct 262 ms 465516 KB Output is correct
33 Correct 195 ms 460884 KB Output is correct
34 Correct 270 ms 463328 KB Output is correct
35 Correct 316 ms 465748 KB Output is correct
36 Correct 239 ms 465232 KB Output is correct
37 Correct 203 ms 461344 KB Output is correct
38 Correct 301 ms 465732 KB Output is correct
39 Correct 241 ms 465744 KB Output is correct
40 Correct 276 ms 463612 KB Output is correct
41 Correct 300 ms 464212 KB Output is correct
42 Correct 300 ms 464976 KB Output is correct
43 Correct 288 ms 463444 KB Output is correct
44 Correct 246 ms 462928 KB Output is correct
45 Correct 205 ms 461328 KB Output is correct
46 Correct 156 ms 458364 KB Output is correct
47 Correct 156 ms 458324 KB Output is correct
48 Correct 148 ms 458580 KB Output is correct
49 Correct 164 ms 458328 KB Output is correct
50 Correct 161 ms 458316 KB Output is correct
51 Correct 170 ms 458320 KB Output is correct
52 Correct 165 ms 458252 KB Output is correct
53 Correct 162 ms 458320 KB Output is correct
54 Correct 155 ms 458324 KB Output is correct
55 Correct 156 ms 458320 KB Output is correct
56 Correct 166 ms 458324 KB Output is correct
57 Correct 160 ms 458428 KB Output is correct
58 Correct 164 ms 458320 KB Output is correct
59 Correct 163 ms 458216 KB Output is correct
60 Correct 169 ms 458324 KB Output is correct
61 Correct 180 ms 458588 KB Output is correct
62 Correct 181 ms 458604 KB Output is correct
63 Correct 166 ms 458580 KB Output is correct
64 Correct 171 ms 458588 KB Output is correct
65 Correct 180 ms 458832 KB Output is correct
66 Correct 174 ms 458580 KB Output is correct
67 Correct 174 ms 458580 KB Output is correct
68 Correct 196 ms 458784 KB Output is correct
69 Correct 190 ms 459068 KB Output is correct
70 Correct 172 ms 458576 KB Output is correct
71 Correct 185 ms 458836 KB Output is correct
72 Correct 181 ms 459012 KB Output is correct
73 Correct 176 ms 458580 KB Output is correct
74 Correct 185 ms 458644 KB Output is correct
75 Correct 182 ms 458580 KB Output is correct
76 Correct 596 ms 466768 KB Output is correct
77 Correct 642 ms 466512 KB Output is correct
78 Correct 268 ms 462424 KB Output is correct
79 Correct 724 ms 464724 KB Output is correct
80 Correct 1016 ms 467028 KB Output is correct
81 Correct 338 ms 463184 KB Output is correct
82 Correct 567 ms 465920 KB Output is correct
83 Correct 967 ms 466516 KB Output is correct
84 Correct 727 ms 467096 KB Output is correct
85 Runtime error 2551 ms 524292 KB Execution killed with signal 9
86 Halted 0 ms 0 KB -