Submission #836136

#	Time	Username	Problem	Language	Result	Execution time	Memory
836136		MetalPower	Sličnost (COI23_slicnost)	C++14	17 / 100	384 ms	524288 KiB

Main

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

#define ll long long
#define pii pair<int, ll>
#define fi first
#define se second
 
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 (stderr)

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 / 7
• Subtask 2: 10 / 10
• Subtask 3: 0 / 33
• Subtask 4: 0 / 7
• Subtask 5: 0 / 10
• Subtask 6: 0 / 33