Submission #1027061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027061		vjudge1	Sličnost (COI23_slicnost)	C++17	100 / 100	1151 ms	458740 KiB

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)25*(int)1e6], rightt[(int)25*(int)1e6];
array<int, 3> st[(int)25*(int)1e6];



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<25*(int)1e6; 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 (stderr)

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