oj.uz

Submission #957347

# Submission time Handle Problem Language Result Execution time Memory
957347 2024-04-03T14:11:24 Z ono_de206 Sličnost (COI23_slicnost) C++14
0 / 100
 11 ms 51292 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

// #define int long long

typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
// typedef pair<int, int> P;

template<typename T, typename U>
ostream & operator << (ostream &out, const pair<T, U> &c) {
	out << c.first << ' ' << c.second;
	return out;
}

template<typename T>
ostream & operator << (ostream &out, vector<T> &v) {
	const int sz = v.size();
	for (int i = 0; i < sz; i++) {
		if (i) out << ' ';
		out << v[i];
	}
	return out;
}

template<typename T>
istream & operator >> (istream &in, vector<T> &v) {
	for (T &x : v) in >> x;
	return in;
}

template<typename T, typename U>
	istream & operator >> (istream &in, pair<T, U> &c) {
	in >> c.first;
	in >> c.second;
	return in;
}

template<typename T>
void mxx(T &a, T b){if(b > a) a = b;}
template<typename T>
void mnn(T &a, T b){if(b < a) a = b;}

const int mxn = 1e5 + 10, MXLOG = 22, mod = 1e9 + 7, P = 1181, D = 1523, N = 2500;
const long long inf = 2e18 + 10;

struct node {
	int mx, cnt, sum;
	node() : mx(0), cnt(0), sum(0) {}
	node(int _mx, int _cnt, int _sum) : mx(_mx), cnt(_cnt), sum(_sum) {}
} d[mxn * 40];

node operator+(const node &a, const node &b) {
	node ret(0, 0, 0);
	ret.mx = max(a.mx, a.sum + b.mx);
	ret.sum = a.sum + b.sum;
	if(ret.mx == a.mx) ret.cnt += a.cnt;
	if(ret.mx == b.mx + a.sum) ret.cnt += b.cnt;
	return ret;
}

int lch[mxn * 40], rch[mxn * 40], p[mxn], q[mxn], pos[mxn], root[mxn], T;

int update(int l, int r, int i, int x, int y) {
	int save = ++T;
	if(l == r) {
		d[save] = d[i];
		d[save].mx += y;
		d[save].sum += y;
		d[save].cnt = 1;
		return save;
	}
	int m = (l + r) / 2;
	if(x <= m) {
		lch[save] = update(l, m, lch[i], x, y);
		rch[save] = rch[i];
	} else {
		lch[save] = lch[i];
		rch[save] = update(m + 1, r, rch[i], x, y);
	}
	d[save] = d[lch[save]] + d[rch[save]];
	return save;
}

map<int, int> mp;

void add(node x) {
	mp[x.mx] += x.cnt;
}

void rem(node x) {
	mp[x.mx] -= x.cnt;
	if(mp[x.mx] == 0) mp.erase(x.mx);
}

void print_ans() {
	auto val = *mp.rbegin();
	assert(val.ss != 0);
	cout << val.ff << ' ' << val.ss << endl;
}

void go() {
	int n, k, Q;
	cin >> n >> k >> Q;
	for(int i = 1; i <= n; i++) {
		cin >> p[i];
	}
	for(int i = 1; i <= n; i++) {
		cin >> q[i];
		pos[q[i]] = i;
	}
	for(int i = 1; i <= n; i++) {
		root[i] = update(1, n, root[i - 1], max(k, pos[p[i]]), 1);
		if(pos[p[i]] + k <= n) root[i] = update(1, n, root[i], pos[p[i]] + k, -1);
		if(i - k > 0) {
			root[i] = update(1, n, root[i], max(k, pos[p[i - k]]), -1);
			if(pos[p[i - k]] + k <= n) root[i] = update(1, n, root[i], pos[p[i - k]] + k, 1);
		}
		if(i >= k) add(d[root[i]]);
	}
	print_ans();
	// cout << endl;
	while(Q--) {
		int x;
		cin >> x;
		if(x >= k) {
			rem(d[root[x]]);
			root[x] = update(1, n, root[x], max(k, pos[p[x]]), -1);
			if(pos[p[x]] + k <= n) root[x] = update(1, n, root[x], pos[p[x]] + k, 1);
			root[x] = update(1, n, root[x], max(k, pos[p[x + 1]]), 1);
			if(pos[p[x + 1]] + k <= n) root[x] = update(1, n, root[x], pos[p[x + 1]] + k, -1);
			add(d[root[x]]);
		}
		if(x + k <= n) {
			rem(d[root[x + k]]);
			root[x + k] = update(1, n, root[x + k], max(k, pos[p[x + 1]]), -1);
			if(pos[p[x + 1]] + k <= n) root[x + k] = update(1, n, root[x + k], pos[p[x + 1]] + k, 1);
			root[x + k] = update(1, n, root[x + k], max(k, pos[p[x]]), 1);
			if(pos[p[x]] + k <= n) root[x + k] = update(1, n, root[x + k], pos[p[x]] + k, -1);
			add(d[root[x + k]]);
		}
		swap(p[x], p[x + 1]);
		// cout << "------------------------------\n";
		// for(int i = 1; i <= n; i++) {
		// 	cout << p[i] << ' ';
		// }
		// cout << endl;
		// for(int i = 1; i <= n; i++) {
		// 	cout << q[i] << ' ';
		// }
		// cout << endl;
		// cout << "----------------------------\n";
		// for(int i = 1; i <= n; i++) {
		// 	cout << d[root[i]].mx << ' ' << d[root[i]].cnt << ' ' << d[root[i]].sum << endl;
		// }
		print_ans();
		// cout << "---------------------fuckkkk ends here\n";
		// cout << '\n';
	}
}

signed main() {
	fast;
	int t = 1;
	// cin >> t;
	while(t--) {
		go();
	}
	return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 51292 KB Output is correct
2 Correct 11 ms 51288 KB Output is correct
3 Correct 10 ms 51288 KB Output is correct
4 Correct 10 ms 51292 KB Output is correct
5 Correct 10 ms 51292 KB Output is correct
6 Correct 10 ms 51288 KB Output is correct
7 Correct 11 ms 51292 KB Output is correct
8 Correct 10 ms 51292 KB Output is correct
9 Incorrect 11 ms 51292 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 51292 KB Output is correct
2 Correct 11 ms 51288 KB Output is correct
3 Correct 10 ms 51288 KB Output is correct
4 Correct 10 ms 51292 KB Output is correct
5 Correct 10 ms 51292 KB Output is correct
6 Correct 10 ms 51288 KB Output is correct
7 Correct 11 ms 51292 KB Output is correct
8 Correct 10 ms 51292 KB Output is correct
9 Incorrect 11 ms 51292 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 51292 KB Output is correct
2 Correct 11 ms 51288 KB Output is correct
3 Correct 10 ms 51288 KB Output is correct
4 Correct 10 ms 51292 KB Output is correct
5 Correct 10 ms 51292 KB Output is correct
6 Correct 10 ms 51288 KB Output is correct
7 Correct 11 ms 51292 KB Output is correct
8 Correct 10 ms 51292 KB Output is correct
9 Incorrect 11 ms 51292 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 51292 KB Output is correct
2 Correct 11 ms 51288 KB Output is correct
3 Correct 10 ms 51288 KB Output is correct
4 Correct 10 ms 51292 KB Output is correct
5 Correct 10 ms 51292 KB Output is correct
6 Correct 10 ms 51288 KB Output is correct
7 Correct 11 ms 51292 KB Output is correct
8 Correct 10 ms 51292 KB Output is correct
9 Incorrect 11 ms 51292 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 51292 KB Output is correct
2 Correct 11 ms 51288 KB Output is correct
3 Correct 10 ms 51288 KB Output is correct
4 Correct 10 ms 51292 KB Output is correct
5 Correct 10 ms 51292 KB Output is correct
6 Correct 10 ms 51288 KB Output is correct
7 Correct 11 ms 51292 KB Output is correct
8 Correct 10 ms 51292 KB Output is correct
9 Incorrect 11 ms 51292 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 51292 KB Output is correct
2 Correct 11 ms 51288 KB Output is correct
3 Correct 10 ms 51288 KB Output is correct
4 Correct 10 ms 51292 KB Output is correct
5 Correct 10 ms 51292 KB Output is correct
6 Correct 10 ms 51288 KB Output is correct
7 Correct 11 ms 51292 KB Output is correct
8 Correct 10 ms 51292 KB Output is correct
9 Incorrect 11 ms 51292 KB Output isn't correct
10 Halted 0 ms 0 KB -