oj.uz

답안 #1026771

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1026771 2024-07-18T10:55:16 Z vjudge1 Sličnost (COI23_slicnost) C++17
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

void f(){
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	#endif
}

struct segtree{
	int n, tl, tr, val, pos ; 
	vector<array<int , 3>> st;

	array<int, 3> TxT(array<int, 3> l, array<int, 3> r){
		// leftsum ma count
		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;
	}

	




	segtree(int _n){
		n=_n;
		st.resize(4*n);

		build(1, 0, n-1);
	}

	void build(int v, int l, int r){
		if(l==r) st[v]={0, 0, 1};
		else{
			int mid=(l+r) / 2;
			build(v*2, l, mid);
			build(v*2+1, mid+1, r);

			st[v]=TxT(st[v*2], st[v*2+1]);

		}
	}
	void update(int v, int l, int r){
		if(l==r&&l==pos){
			st[v][1]+=val;
			st[v][0]+=val;
		}
		else{
			int mid=(l+r) / 2;
			if(pos<=mid)update(v*2, l, mid);
			else update(v*2+1, mid+1, r);

			st[v]=TxT(st[v*2], st[v*2+1]);
		}


	}
	void upd(int l, int v){
		pos=l, val=v;
		update(1, 0, n-1);
	}

	array<int, 3> get(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(get(v*2, l, mid), get(v*2+1, mid+1, r));

		}
	}
	array<int, 2> get(int l, int r){
		tl = l; tr = r;

		auto x=get(1, 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;

	segtree st(n);

	vector<int> a(n), b(n), pos(n);
	int c=0;
	for(auto &i: a) cin >> i, i--;
	for(auto &i: b) cin >> i, i--, pos[i]=c++;

	auto ek=[&](int i){
		int r=pos[i];

		st.upd(max(0LL, r-k+1), 1);
		st.upd(min(n-k, r), -1);
	};
	auto cik=[&](int i){
		int r=pos[i];
		st.upd(max(0LL, r-k+1), -1);
		st.upd(min(n-k, r), 1);
	};

	for(int i=0; i<k; i++){
		ek(a[i]);
	}

	
	auto x=st.get(0, n-k);
	for(int i=k; i<n; i++){
		cik(a[i-k]); ek(a[i]);
		auto y=st.get(0, n-k);
		if(x[0]==y[0]) x[1]+=y[1];
		else if(x[0]<y[0]) x=y;	
	}

	cout<<x[0]<<" "<<x[1]<<"\n";
	while(q--){
		int p; cin >> p;
		p--;
		swap(a[p], a[p+1]);

		st.build(1, 0, n-1);


		for(int i=0; i<k; i++){
			ek(a[i]);
		}
		auto x=st.get(0, n-k);

		for(int i=k; i<n; i++){
			cik(a[i-k]); ek(a[i]);
			auto y=st.get(0, n-k);
			if(x[0]==y[0]) x[1]+=y[1];
			else if(x[0]<y[0]) x=y;
		}

		cout<<x[0]<<" "<<x[1]<<"\n";
	}
}

Compilation message

Main.cpp: In function 'void f()':
Main.cpp:8:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |  freopen("in.txt", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:9:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |  freopen("out.txt", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -