oj.uz

Submission #836135

# Submission time Handle Problem Language Result Execution time Memory
836135 2023-08-24T07:50:32 Z MetalPower Sličnost (COI23_slicnost) C++14
17 / 100
 449 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define pii pair<int, int>
#define fi first
#define se second
#define ll long long
 
const int MX = 1e5 + 10;
const int INF = 1e9 + 7;
 
int N, K, Q, p[MX], q[MX], pos[MX];
 
pii merge(pii a, pii b){
	if(a.fi > b.fi) return a;
	if(b.fi > a.fi) return b;
	return make_pair(a.fi, a.se + b.se);
}
 
struct node{
	int l, r, lz; pii val;
	node *lc, *rc;
 
	node(int l = 0, int r = -1) : l(l), r(r), lz(0), lc(NULL), rc(NULL) {
		val.fi = 0;
		val.se = r - l + 1;
	}

	node* newChild(){
		node *nw = new node(l, r);
		nw -> lz = lz;
		nw -> val = val;
		int mid = l + r >> 1;
		if(lc == NULL) lc = new node(l, mid);
		if(rc == NULL) rc = new node(mid + 1, r);
		nw -> lc = lc;
		nw -> rc = rc;
		return nw;
	}
 
	void prop(){
		if(l != r){
			int mid = l + r >> 1;
			if(lc == NULL) lc = new node(l, mid);
			if(rc == NULL) rc = new node(mid + 1, r);
			lc = lc -> newChild();
			rc = rc -> newChild();
			lc -> lz += lz; lc -> val.fi += lz;
			rc -> lz += lz;	rc -> val.fi += lz;
		}
		lz = 0;
	}
 
	pii query(int lf, int rg){
		if(r < lf || l > rg) return {-INF, 1};
		if(lf <= l && r <= rg) return val;
		prop();
		return merge(lc -> query(lf, rg), rc -> query(lf, rg));
	}
};

node* upd(node *pre, int lf, int rg, int v){
	pre -> prop();
	if(pre -> r < lf || pre -> l > rg) return pre;
	if(lf <= pre -> l && pre -> r <= rg){
		node *curr = pre -> newChild();
		curr -> lz += v;
		curr -> val.fi += v;
		curr -> prop();
		return curr;
	}else{
		int mid = pre -> l + pre -> r >> 1;
		node* curr = pre -> newChild();
		curr -> lc = upd(pre -> lc, lf, rg, v);
		curr -> rc = upd(pre -> rc, lf, rg, v);
		curr -> val = merge(curr -> lc -> val, curr -> rc -> val);
		return curr;
	}
}

struct segit{
	pii st[MX << 1];

	void update(int p, pii v){
		for(p += MX, st[p] = v, p >>= 1; p > 0; p >>= 1){
			st[p] = merge(st[p << 1], st[p << 1|1]);
		}
	}

	pii que(int l, int r){
		pii res = {-INF, 0};
		for(l += MX, r += MX + 1; l < r; l >>= 1, r >>= 1){
			if(l & 1) res = merge(res, st[l++]);
			if(r & 1) res = merge(res, st[--r]);
		}
		return res;
	}
} S;

node *roots[MX];
 
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
	cin >> N >> K >> Q;
	for(int i = 0; i < N; i++) cin >> p[i];
	for(int i = 0; i < N; i++) cin >> q[i], pos[q[i]] = i;
 
	roots[K - 1] = new node(0, N - 1);
 
 	for(int i = 0; i < K; i++){
 		// cout << "update position " << i << '\n';
		roots[K - 1] = upd(roots[K - 1], max(0, pos[p[i]] - K + 1), pos[p[i]], 1);
 	}
 
	pii curr = roots[K - 1] -> query(0, N - K);
 
	S.update(K - 1, curr);
 
	for(int i = K; i < N; i++){
		roots[i] = upd(roots[i - 1], max(0, pos[p[i - K]] - K + 1), pos[p[i - K]], -1);
		roots[i] = upd(roots[i], max(0, pos[p[i]] - K + 1), pos[p[i]], 1);
		curr = roots[i] -> query(0, N - K);
		S.update(i, curr);
	}

	{
		pii ans = S.que(K - 1, N - 1);
		cout << ans.fi << " " << ans.se << '\n';
	}

	for(int x = 0; x < Q; x++){
		int loc; cin >> loc;
		{
			// update loc
			roots[loc] = upd(roots[loc], max(0, pos[p[loc]] - K + 1), pos[p[loc]], -1);
			roots[loc] = upd(roots[loc], max(0, pos[p[loc + 1]] - K + 1), pos[p[loc + 1]], 1);
			curr = roots[loc] -> query(0, N - K);
			S.update(loc, curr);
		}
		if(loc + K < N){
			// update loc + K
			roots[loc + K] = upd(roots[loc + K], max(0, pos[p[loc + 1]] - K + 1), pos[p[loc + 1]], -1);
			roots[loc + K] = upd(roots[loc + K], max(0, pos[p[loc]] - K + 1), pos[p[loc]], 1);
			curr = roots[loc + K] -> query(0, N - K);
			S.update(loc + K, curr);
		}
		swap(p[loc], p[loc + 1]);
		{
			pii ans = S.que(K - 1, N - 1);
			cout << ans.fi << " " << ans.se << '\n';
		}
	}
}

Compilation message

Main.cpp: In member function 'node* node::newChild()':
Main.cpp:33:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In member function 'void node::prop()':
Main.cpp:43:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |    int mid = l + r >> 1;
      |              ~~^~~
Main.cpp: In function 'node* upd(node*, int, int, int)':
Main.cpp:72:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |   int mid = pre -> l + pre -> r >> 1;
      |             ~~~~~~~~~^~~~~~~~~~
Main.cpp:72:7: warning: unused variable 'mid' [-Wunused-variable]
   72 |   int mid = pre -> l + pre -> r >> 1;
      |       ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 1 ms 596 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 23 ms 29140 KB Output is correct
17 Correct 29 ms 36192 KB Output is correct
18 Correct 16 ms 18004 KB Output is correct
19 Correct 34 ms 40384 KB Output is correct
20 Correct 53 ms 53740 KB Output is correct
21 Correct 44 ms 55800 KB Output is correct
22 Correct 18 ms 21460 KB Output is correct
23 Correct 44 ms 51696 KB Output is correct
24 Correct 39 ms 52676 KB Output is correct
25 Correct 40 ms 44876 KB Output is correct
26 Correct 50 ms 50372 KB Output is correct
27 Correct 47 ms 55944 KB Output is correct
28 Correct 36 ms 41756 KB Output is correct
29 Correct 34 ms 35268 KB Output is correct
30 Correct 18 ms 20924 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 23 ms 29140 KB Output is correct
17 Correct 29 ms 36192 KB Output is correct
18 Correct 16 ms 18004 KB Output is correct
19 Correct 34 ms 40384 KB Output is correct
20 Correct 53 ms 53740 KB Output is correct
21 Correct 44 ms 55800 KB Output is correct
22 Correct 18 ms 21460 KB Output is correct
23 Correct 44 ms 51696 KB Output is correct
24 Correct 39 ms 52676 KB Output is correct
25 Correct 40 ms 44876 KB Output is correct
26 Correct 50 ms 50372 KB Output is correct
27 Correct 47 ms 55944 KB Output is correct
28 Correct 36 ms 41756 KB Output is correct
29 Correct 34 ms 35268 KB Output is correct
30 Correct 18 ms 20924 KB Output is correct
31 Runtime error 449 ms 524288 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 2 ms 1236 KB Output is correct
17 Incorrect 1 ms 1492 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 23 ms 29140 KB Output is correct
17 Correct 29 ms 36192 KB Output is correct
18 Correct 16 ms 18004 KB Output is correct
19 Correct 34 ms 40384 KB Output is correct
20 Correct 53 ms 53740 KB Output is correct
21 Correct 44 ms 55800 KB Output is correct
22 Correct 18 ms 21460 KB Output is correct
23 Correct 44 ms 51696 KB Output is correct
24 Correct 39 ms 52676 KB Output is correct
25 Correct 40 ms 44876 KB Output is correct
26 Correct 50 ms 50372 KB Output is correct
27 Correct 47 ms 55944 KB Output is correct
28 Correct 36 ms 41756 KB Output is correct
29 Correct 34 ms 35268 KB Output is correct
30 Correct 18 ms 20924 KB Output is correct
31 Correct 2 ms 1236 KB Output is correct
32 Incorrect 1 ms 1492 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 23 ms 29140 KB Output is correct
17 Correct 29 ms 36192 KB Output is correct
18 Correct 16 ms 18004 KB Output is correct
19 Correct 34 ms 40384 KB Output is correct
20 Correct 53 ms 53740 KB Output is correct
21 Correct 44 ms 55800 KB Output is correct
22 Correct 18 ms 21460 KB Output is correct
23 Correct 44 ms 51696 KB Output is correct
24 Correct 39 ms 52676 KB Output is correct
25 Correct 40 ms 44876 KB Output is correct
26 Correct 50 ms 50372 KB Output is correct
27 Correct 47 ms 55944 KB Output is correct
28 Correct 36 ms 41756 KB Output is correct
29 Correct 34 ms 35268 KB Output is correct
30 Correct 18 ms 20924 KB Output is correct
31 Runtime error 449 ms 524288 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -