답안 #1027058

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1027058	2024-07-18T19:40:43 Z	vjudge1	Sličnost (COI23_slicnost)	C++17	67 / 100	407 ms	409212 KB

Main

#include <bits/stdc++.h>
using namespace std;

void f(){
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	#endif
}

int n, tl, tr, val, pos, check, id, rid; 
vector<int> roots;
int leftt[(int)1e7], rightt[(int)1e7];
array<int, 3> st[(int)1e7];



array<int, 3> TxT(array<int, 3> l, array<int, 3> r){
	
	array<int, 3> res={0, 0, 0};

	res[0]=l[0]+r[0];
	res[1]=max(l[1], l[0]+r[1]);

	if(l[1]==res[1]) res[2]+=l[2];
	if(r[1]+l[0]==res[1]) res[2]+=r[2];

	return res;
}

int add(){
	
	return id++;
}
void build(int v, int l, int r){
	if(l==r) st[v]={0, 0, 1};
	else{
		int mid=(l+r)/2;
		if(leftt[v]==-1) leftt[v]=add();
		if(rightt[v]==-1) rightt[v]=add();

		build(leftt[v], l, mid);
		build(rightt[v], mid+1, r);

		st[v]=TxT(st[leftt[v]], st[rightt[v]]);
	}
}




void update(int v, int l, int r, int nv){
	if(l==r){
		st[nv]=st[v];
		st[nv][0]+=val; st[nv][1]+=val;
	}
	else{
		int mid=(l+r) / 2;
		if(pos<=mid){
			leftt[nv]=add();
			rightt[nv]=rightt[v];
			update(leftt[v], l, mid, leftt[nv]);
		}
		else{
			leftt[nv]=leftt[v];
			rightt[nv]=add();
			update(rightt[v], mid+1, r, rightt[nv]);
		}
		st[nv]=TxT(st[leftt[nv]], st[rightt[nv]]);
	}


}
int upd(int p, int l, int v){

	if(check==0){
		pos=l, val=v;
		int id=add();
		roots.push_back(id);
		update(p, 0, n-1, id);
		return id;
	}
	else{
		pos=l, val=v;
		update(p, 0, n-1, p);
		return p;
	}
}

array<int, 3> g(int v, int l, int r){
	if(l>tr||r<tl) return {0, 0, 0};
	else if(l>=tl&&r<=tr) return st[v];
	else{
		int mid=(l+r) /2;
		return TxT(g(leftt[v], l, mid), g(rightt[v], mid+1, r));

	}
}
array<int, 2> get(int pos, int l, int r){
	tl = l; tr = r;
	auto x= g(pos, 0, n-1);

	return {x[1], x[2]};
}


signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	//f();

	int N, k, q; cin >> N >> k >> q;

	n=N+1;
	vector<int> a(N), b(N), pos(N), segt;
	int v=add();
		for(int l=0; l<1e7; l++) leftt[l]=rightt[l]=-1;

	build(v, 0, n-1);
	roots.push_back(v);
	int c=0;
	for(auto &i: a) cin >> i, i--;
	for(auto &i: b) cin >> i, i--, pos[i]=c++;

	auto ek=[&](int y, int i){
		int r=pos[i];

		int x=upd(y, max(0, r-k+1), 1);
		upd(x, r+1, -1);
		return (int) roots.back();
	
	};
	auto cik=[&](int y, int i){
		int r=pos[i];
		int x= upd(y, max(0, r-k+1), -1);
		upd(x, r+1, 1);
		return (int)roots.back();
	};

	for(int i=0; i<k; i++){
		ek(roots.back(), a[i]);
	}
	segt.push_back(roots.back());
	
	vector<array<int,2>> all(N-k+1);
	vector<long long> pf(N+3);

	auto x=get(roots.back(), 0, N-k);
	all[0]=x;
	pf[x[0]]+=x[1];
	int ma=x[0];

	for(int i=k; i<N; i++){
		cik(roots.back(), a[i-k]); 
		segt.push_back(ek(roots.back(), a[i]));
		auto y=get(segt.back(), 0, N-k);
		all[i-k+1]=y;
		pf[y[0]]+=y[1];

		ma=max(ma, y[0]);		
	}
		
	cout<<ma<<" "<<pf[ma]<<"\n";

	auto cikar=[&](int v, int value){
		if(v<0) return;
		
		pf[all[v][0]] -= all[v][1];
		segt[v]=cik(segt[v], value);
		auto x=get(segt[v], 0, N-k);
		all[v] = x;
		pf[all[v][0]] += all[v][1];
	};

	auto cikar2=[&](int v, int value){
		if(v>N-k) return;
		
		pf[all[v][0]] -= all[v][1];
		segt[v]=cik(segt[v], value);
		auto x=get(segt[v], 0, N-k);
		all[v] = x;
		pf[all[v][0]] += all[v][1];
	};
	auto ekle=[&](int v, int value){
		if(v<0) return;
		
		pf[all[v][0]] -= all[v][1];
		segt[v]=ek(segt[v], value);
		auto x=get(segt[v], 0, N-k);

		all[v] = x;
		pf[all[v][0]] += all[v][1];
	};

	auto ekle2=[&](int v, int value){
		if(v>N-k) return;
		
		pf[all[v][0]] -= all[v][1];
		segt[v]=ek(segt[v], value);
		auto x=get(segt[v], 0, N-k);

		all[v] = x;
		pf[all[v][0]] += all[v][1];
	};

	while(q--){
		int p; cin >> p; p--;
		
		cikar(p-k+1, a[p]);
		cikar2(p+1, a[p+1]);

		swap(a[p], a[p+1]);

		ekle(p-k+1, a[p]);
		ekle2(p+1, a[p+1]);

		if(pf[ma+1]>0) ma++;
		else if(pf[ma]==0) ma--;

		cout<<ma<<" "<<pf[ma]<<"\n";
	}
}

Compilation message

Main.cpp: In function 'void f()':
Main.cpp:6:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 |  freopen("in.txt", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:7:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |  freopen("out.txt", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	78936 KB	Output is correct
2	Correct	8 ms	78816 KB	Output is correct
3	Correct	9 ms	78940 KB	Output is correct
4	Correct	8 ms	78940 KB	Output is correct
5	Correct	9 ms	78840 KB	Output is correct
6	Correct	10 ms	78940 KB	Output is correct
7	Correct	9 ms	78948 KB	Output is correct
8	Correct	9 ms	78840 KB	Output is correct
9	Correct	9 ms	78940 KB	Output is correct
10	Correct	9 ms	78928 KB	Output is correct
11	Correct	9 ms	78940 KB	Output is correct
12	Correct	9 ms	78880 KB	Output is correct
13	Correct	9 ms	78940 KB	Output is correct
14	Correct	9 ms	78836 KB	Output is correct
15	Correct	9 ms	78944 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	78936 KB	Output is correct
2	Correct	8 ms	78816 KB	Output is correct
3	Correct	9 ms	78940 KB	Output is correct
4	Correct	8 ms	78940 KB	Output is correct
5	Correct	9 ms	78840 KB	Output is correct
6	Correct	10 ms	78940 KB	Output is correct
7	Correct	9 ms	78948 KB	Output is correct
8	Correct	9 ms	78840 KB	Output is correct
9	Correct	9 ms	78940 KB	Output is correct
10	Correct	9 ms	78928 KB	Output is correct
11	Correct	9 ms	78940 KB	Output is correct
12	Correct	9 ms	78880 KB	Output is correct
13	Correct	9 ms	78940 KB	Output is correct
14	Correct	9 ms	78836 KB	Output is correct
15	Correct	9 ms	78944 KB	Output is correct
16	Correct	15 ms	82520 KB	Output is correct
17	Correct	15 ms	82268 KB	Output is correct
18	Correct	13 ms	80732 KB	Output is correct
19	Correct	13 ms	81496 KB	Output is correct
20	Correct	15 ms	82524 KB	Output is correct
21	Correct	13 ms	82272 KB	Output is correct
22	Correct	12 ms	80732 KB	Output is correct
23	Correct	15 ms	82300 KB	Output is correct
24	Correct	14 ms	82524 KB	Output is correct
25	Correct	14 ms	81736 KB	Output is correct
26	Correct	15 ms	82012 KB	Output is correct
27	Correct	16 ms	82248 KB	Output is correct
28	Correct	13 ms	81500 KB	Output is correct
29	Correct	12 ms	81496 KB	Output is correct
30	Correct	12 ms	80916 KB	Output is correct

Subtask #3
33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	78936 KB	Output is correct
2	Correct	8 ms	78816 KB	Output is correct
3	Correct	9 ms	78940 KB	Output is correct
4	Correct	8 ms	78940 KB	Output is correct
5	Correct	9 ms	78840 KB	Output is correct
6	Correct	10 ms	78940 KB	Output is correct
7	Correct	9 ms	78948 KB	Output is correct
8	Correct	9 ms	78840 KB	Output is correct
9	Correct	9 ms	78940 KB	Output is correct
10	Correct	9 ms	78928 KB	Output is correct
11	Correct	9 ms	78940 KB	Output is correct
12	Correct	9 ms	78880 KB	Output is correct
13	Correct	9 ms	78940 KB	Output is correct
14	Correct	9 ms	78836 KB	Output is correct
15	Correct	9 ms	78944 KB	Output is correct
16	Correct	15 ms	82520 KB	Output is correct
17	Correct	15 ms	82268 KB	Output is correct
18	Correct	13 ms	80732 KB	Output is correct
19	Correct	13 ms	81496 KB	Output is correct
20	Correct	15 ms	82524 KB	Output is correct
21	Correct	13 ms	82272 KB	Output is correct
22	Correct	12 ms	80732 KB	Output is correct
23	Correct	15 ms	82300 KB	Output is correct
24	Correct	14 ms	82524 KB	Output is correct
25	Correct	14 ms	81736 KB	Output is correct
26	Correct	15 ms	82012 KB	Output is correct
27	Correct	16 ms	82248 KB	Output is correct
28	Correct	13 ms	81500 KB	Output is correct
29	Correct	12 ms	81496 KB	Output is correct
30	Correct	12 ms	80916 KB	Output is correct
31	Correct	162 ms	167348 KB	Output is correct
32	Correct	174 ms	166596 KB	Output is correct
33	Correct	76 ms	124620 KB	Output is correct
34	Correct	141 ms	146172 KB	Output is correct
35	Correct	210 ms	169256 KB	Output is correct
36	Correct	113 ms	163560 KB	Output is correct
37	Correct	63 ms	128048 KB	Output is correct
38	Correct	217 ms	165128 KB	Output is correct
39	Correct	132 ms	168704 KB	Output is correct
40	Correct	166 ms	149820 KB	Output is correct
41	Correct	173 ms	155852 KB	Output is correct
42	Correct	207 ms	162820 KB	Output is correct
43	Correct	158 ms	147032 KB	Output is correct
44	Correct	129 ms	142532 KB	Output is correct
45	Correct	87 ms	127948 KB	Output is correct

Subtask #4
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	78936 KB	Output is correct
2	Correct	8 ms	78816 KB	Output is correct
3	Correct	9 ms	78940 KB	Output is correct
4	Correct	8 ms	78940 KB	Output is correct
5	Correct	9 ms	78840 KB	Output is correct
6	Correct	10 ms	78940 KB	Output is correct
7	Correct	9 ms	78948 KB	Output is correct
8	Correct	9 ms	78840 KB	Output is correct
9	Correct	9 ms	78940 KB	Output is correct
10	Correct	9 ms	78928 KB	Output is correct
11	Correct	9 ms	78940 KB	Output is correct
12	Correct	9 ms	78880 KB	Output is correct
13	Correct	9 ms	78940 KB	Output is correct
14	Correct	9 ms	78836 KB	Output is correct
15	Correct	9 ms	78944 KB	Output is correct
16	Correct	10 ms	78936 KB	Output is correct
17	Correct	9 ms	79088 KB	Output is correct
18	Correct	9 ms	78940 KB	Output is correct
19	Correct	9 ms	78892 KB	Output is correct
20	Correct	9 ms	78936 KB	Output is correct
21	Correct	10 ms	78940 KB	Output is correct
22	Correct	9 ms	78940 KB	Output is correct
23	Correct	10 ms	79112 KB	Output is correct
24	Correct	9 ms	79124 KB	Output is correct
25	Correct	9 ms	78940 KB	Output is correct
26	Correct	9 ms	78940 KB	Output is correct
27	Correct	10 ms	78992 KB	Output is correct
28	Correct	9 ms	78940 KB	Output is correct
29	Correct	10 ms	78940 KB	Output is correct
30	Correct	9 ms	78940 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	78936 KB	Output is correct
2	Correct	8 ms	78816 KB	Output is correct
3	Correct	9 ms	78940 KB	Output is correct
4	Correct	8 ms	78940 KB	Output is correct
5	Correct	9 ms	78840 KB	Output is correct
6	Correct	10 ms	78940 KB	Output is correct
7	Correct	9 ms	78948 KB	Output is correct
8	Correct	9 ms	78840 KB	Output is correct
9	Correct	9 ms	78940 KB	Output is correct
10	Correct	9 ms	78928 KB	Output is correct
11	Correct	9 ms	78940 KB	Output is correct
12	Correct	9 ms	78880 KB	Output is correct
13	Correct	9 ms	78940 KB	Output is correct
14	Correct	9 ms	78836 KB	Output is correct
15	Correct	9 ms	78944 KB	Output is correct
16	Correct	15 ms	82520 KB	Output is correct
17	Correct	15 ms	82268 KB	Output is correct
18	Correct	13 ms	80732 KB	Output is correct
19	Correct	13 ms	81496 KB	Output is correct
20	Correct	15 ms	82524 KB	Output is correct
21	Correct	13 ms	82272 KB	Output is correct
22	Correct	12 ms	80732 KB	Output is correct
23	Correct	15 ms	82300 KB	Output is correct
24	Correct	14 ms	82524 KB	Output is correct
25	Correct	14 ms	81736 KB	Output is correct
26	Correct	15 ms	82012 KB	Output is correct
27	Correct	16 ms	82248 KB	Output is correct
28	Correct	13 ms	81500 KB	Output is correct
29	Correct	12 ms	81496 KB	Output is correct
30	Correct	12 ms	80916 KB	Output is correct
31	Correct	10 ms	78936 KB	Output is correct
32	Correct	9 ms	79088 KB	Output is correct
33	Correct	9 ms	78940 KB	Output is correct
34	Correct	9 ms	78892 KB	Output is correct
35	Correct	9 ms	78936 KB	Output is correct
36	Correct	10 ms	78940 KB	Output is correct
37	Correct	9 ms	78940 KB	Output is correct
38	Correct	10 ms	79112 KB	Output is correct
39	Correct	9 ms	79124 KB	Output is correct
40	Correct	9 ms	78940 KB	Output is correct
41	Correct	9 ms	78940 KB	Output is correct
42	Correct	10 ms	78992 KB	Output is correct
43	Correct	9 ms	78940 KB	Output is correct
44	Correct	10 ms	78940 KB	Output is correct
45	Correct	9 ms	78940 KB	Output is correct
46	Correct	27 ms	88640 KB	Output is correct
47	Correct	27 ms	88780 KB	Output is correct
48	Correct	12 ms	80732 KB	Output is correct
49	Correct	19 ms	84792 KB	Output is correct
50	Correct	31 ms	88860 KB	Output is correct
51	Correct	13 ms	81832 KB	Output is correct
52	Correct	21 ms	86268 KB	Output is correct
53	Correct	29 ms	88292 KB	Output is correct
54	Correct	31 ms	88480 KB	Output is correct
55	Correct	19 ms	84696 KB	Output is correct
56	Correct	31 ms	88596 KB	Output is correct
57	Correct	30 ms	88272 KB	Output is correct
58	Correct	17 ms	82792 KB	Output is correct
59	Correct	26 ms	87008 KB	Output is correct
60	Correct	16 ms	82768 KB	Output is correct

Subtask #6
0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	78936 KB	Output is correct
2	Correct	8 ms	78816 KB	Output is correct
3	Correct	9 ms	78940 KB	Output is correct
4	Correct	8 ms	78940 KB	Output is correct
5	Correct	9 ms	78840 KB	Output is correct
6	Correct	10 ms	78940 KB	Output is correct
7	Correct	9 ms	78948 KB	Output is correct
8	Correct	9 ms	78840 KB	Output is correct
9	Correct	9 ms	78940 KB	Output is correct
10	Correct	9 ms	78928 KB	Output is correct
11	Correct	9 ms	78940 KB	Output is correct
12	Correct	9 ms	78880 KB	Output is correct
13	Correct	9 ms	78940 KB	Output is correct
14	Correct	9 ms	78836 KB	Output is correct
15	Correct	9 ms	78944 KB	Output is correct
16	Correct	15 ms	82520 KB	Output is correct
17	Correct	15 ms	82268 KB	Output is correct
18	Correct	13 ms	80732 KB	Output is correct
19	Correct	13 ms	81496 KB	Output is correct
20	Correct	15 ms	82524 KB	Output is correct
21	Correct	13 ms	82272 KB	Output is correct
22	Correct	12 ms	80732 KB	Output is correct
23	Correct	15 ms	82300 KB	Output is correct
24	Correct	14 ms	82524 KB	Output is correct
25	Correct	14 ms	81736 KB	Output is correct
26	Correct	15 ms	82012 KB	Output is correct
27	Correct	16 ms	82248 KB	Output is correct
28	Correct	13 ms	81500 KB	Output is correct
29	Correct	12 ms	81496 KB	Output is correct
30	Correct	12 ms	80916 KB	Output is correct
31	Correct	162 ms	167348 KB	Output is correct
32	Correct	174 ms	166596 KB	Output is correct
33	Correct	76 ms	124620 KB	Output is correct
34	Correct	141 ms	146172 KB	Output is correct
35	Correct	210 ms	169256 KB	Output is correct
36	Correct	113 ms	163560 KB	Output is correct
37	Correct	63 ms	128048 KB	Output is correct
38	Correct	217 ms	165128 KB	Output is correct
39	Correct	132 ms	168704 KB	Output is correct
40	Correct	166 ms	149820 KB	Output is correct
41	Correct	173 ms	155852 KB	Output is correct
42	Correct	207 ms	162820 KB	Output is correct
43	Correct	158 ms	147032 KB	Output is correct
44	Correct	129 ms	142532 KB	Output is correct
45	Correct	87 ms	127948 KB	Output is correct
46	Correct	10 ms	78936 KB	Output is correct
47	Correct	9 ms	79088 KB	Output is correct
48	Correct	9 ms	78940 KB	Output is correct
49	Correct	9 ms	78892 KB	Output is correct
50	Correct	9 ms	78936 KB	Output is correct
51	Correct	10 ms	78940 KB	Output is correct
52	Correct	9 ms	78940 KB	Output is correct
53	Correct	10 ms	79112 KB	Output is correct
54	Correct	9 ms	79124 KB	Output is correct
55	Correct	9 ms	78940 KB	Output is correct
56	Correct	9 ms	78940 KB	Output is correct
57	Correct	10 ms	78992 KB	Output is correct
58	Correct	9 ms	78940 KB	Output is correct
59	Correct	10 ms	78940 KB	Output is correct
60	Correct	9 ms	78940 KB	Output is correct
61	Correct	27 ms	88640 KB	Output is correct
62	Correct	27 ms	88780 KB	Output is correct
63	Correct	12 ms	80732 KB	Output is correct
64	Correct	19 ms	84792 KB	Output is correct
65	Correct	31 ms	88860 KB	Output is correct
66	Correct	13 ms	81832 KB	Output is correct
67	Correct	21 ms	86268 KB	Output is correct
68	Correct	29 ms	88292 KB	Output is correct
69	Correct	31 ms	88480 KB	Output is correct
70	Correct	19 ms	84696 KB	Output is correct
71	Correct	31 ms	88596 KB	Output is correct
72	Correct	30 ms	88272 KB	Output is correct
73	Correct	17 ms	82792 KB	Output is correct
74	Correct	26 ms	87008 KB	Output is correct
75	Correct	16 ms	82768 KB	Output is correct
76	Runtime error	407 ms	409212 KB	Execution killed with signal 11
77	Halted	0 ms	0 KB	-

답안 #1027058

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 10.0 / 10.0

Subtask #3 33.0 / 33.0

Subtask #4 7.0 / 7.0

Subtask #5 10.0 / 10.0

Subtask #6 0 / 33.0

Subtask #1
7.0 / 7.0

Subtask #2
10.0 / 10.0

Subtask #3
33.0 / 33.0

Subtask #4
7.0 / 7.0

Subtask #5
10.0 / 10.0

Subtask #6
0 / 33.0