oj.uz

Submission #1026667

# Submission time Handle Problem Language Result Execution time Memory
1026667 2024-07-18T09:05:49 Z vjudge1 Sličnost (COI23_slicnost) C++17
0 / 100
 1 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; 
	vector<array<int , 2>> st;
	vector<int>lazy;

	array<int, 2> TxT(array<int, 2> a, array<int, 2> b){
		
		if(a[0]==b[0]){
			a[1]+=b[1];
			return a;
		}
		else if(a[0]<b[0]) return b;

		return a;
	}

	array<int, 2> TxU(array<int, 2> a, int b){
		a[0]+=b;
		return a;
	}

	int UxU(int a, int b){
		return a+b;
	}

	void push(int v, int l, int r){
		if(lazy[v]&&l<r){
			st[v*2] = TxU(st[v*2], lazy[v]);
			lazy[v*2] = UxU(lazy[v*2], lazy[v]);

			st[v*2+1] = TxU(st[v*2+1], lazy[v]);
			lazy[v*2+1] = UxU(lazy[v+1*2], lazy[v]);
		
			st[v] = TxT(st[v*2], st[v*2+1]);
		}
		lazy[v]=0;
	}


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

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

	void build(int v, int l, int r){
		lazy[v]=0;
		if(l==r) st[v]={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){
		push(v, l, r);
		if(l>tr || r <tl) return;
		else if(l>=tl && r<=tr){
			st[v]=TxU(st[v], val);
			lazy[v]=UxU(lazy[v], val);
		}
		else{
			int mid=(l+r) / 2;
			update(v*2, l, mid);
			update(v*2+1, mid+1, r);

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


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

	array<int, 2> get(int v, int l, int r){
		push(v, l, r);
		if(l>tr||r<tl) return {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;

		return get(1, 0, n-1);
	}
};

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), min(n-k, r), 1);
	};
	auto cik=[&](int i){
		int r=pos[i];
		st.upd(max(0LL, r-k+1), 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]);
		x=st.TxT(x, st.get(0, n-k));


	}

	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]);
			x=st.TxT(x, st.get(0, n-k));
		}

		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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -