Submission #835603

#	Time	Username	Problem	Language	Result	Execution time	Memory
835603		MetalPower	Sličnost (COI23_slicnost)	C++14	50 / 100	142 ms	11932 KiB

Main

#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;
	}

	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 -> 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));
	}

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

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;

	node *root = new node(0, N - 1);

	for(int i = 0; i < K; i++)
		root -> upd(max(0, pos[p[i]] - K + 1), pos[p[i]], 1);

	pii curr = root -> query(0, N - K);

	int mx = -INF; ll cnt = 0;
	if(curr.fi > mx) mx = curr.fi, cnt = curr.se;
	else if(curr.fi == mx) cnt += curr.se;

	for(int i = K; i < N; i++){
		root -> upd(max(0, pos[p[i - K]] - K + 1), pos[p[i - K]], -1);
		root -> upd(max(0, pos[p[i]] - K + 1), pos[p[i]], 1);
		curr = root -> query(0, N - K);
		if(curr.fi > mx) mx = curr.fi, cnt = curr.se;
		else if(curr.fi == mx) cnt += curr.se;
	}

	cout << mx << " " << cnt << '\n';
}

Compilation message (stderr)

Main.cpp: In member function 'void node::prop()':
Main.cpp:31:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |    int mid = l + r >> 1;
      |              ~~^~~
Main.cpp: In member function 'void node::upd(int, int, int)':
Main.cpp:55:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |    int mid = l + r >> 1;
      |              ~~^~~
Main.cpp:55:8: warning: unused variable 'mid' [-Wunused-variable]
   55 |    int mid = l + r >> 1;
      |        ^~~

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 33 / 33
• Subtask 4: 0 / 7
• Subtask 5: 0 / 10
• Subtask 6: 0 / 33