oj.uz

Submission #791615

# Submission time Handle Problem Language Result Execution time Memory
791615 2023-07-24T08:04:25 Z 박상훈(#10047) Sličnost (COI23_slicnost) C++17
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct Node{
	int mx, cnt;
	Node(){}
	Node(int _mx, int _cnt): mx(_mx), cnt(_cnt) {}

	Node operator + (const Node &N) const{
		if (mx > N.mx) return *this;
		if (mx < N.mx) return N;
		return Node(mx, cnt + N.cnt);
	}
};

struct Seg{
	Node tree[400400];
	int lazy[400400];

	void init(int i, int l, int r){
		tree[i] = Node(0, 1);
		lazy[i] = 0;
		if (l==r) return;

		int m = (l+r)>>1;
		init(i<<1, l, m); init(i<<1|1, m+1, r);
	}

	void propagate(int i, int l, int r){
		tree[i].mx += lazy[i];

		if (l!=r){
			lazy[i<<1] += lazy[i];
			lazy[i<<1|1] += lazy[i];
		}

		lazy[i] = 0;
	}

	void update(int i, int l, int r, int s, int e, int x){
		propagate(i, l, r);
		if (r<s || e<l) return;
		if (s<=l && r<=e){
			lazy[i] += x;
			propagate(i, l, r);
			return;
		}

		int m = (l+r)>>1;
		update(i<<1, l, m, s, e, x); update(i<<1|1, m+1, r, s, e, x);
		tree[i] = tree[i<<1] + tree[i<<1|1];
	}
}tree;

int n, k, q;
int a[100100], b[100100], pos[100100];

void naive(){
	tree.init(1, 1, n-k+1);
	for (int i=1;i<=k-1;i++){
		tree.update(1, 1, n-k+1, max(1, pos[a[i]]-k+1), min(n-k+1, pos[a[i]]), 1);
	}

	Node ans(0, 0);

	for (int i=k;i<=n;i++){
		tree.update(1, 1, n-k+1, max(1, pos[a[i]]-k+1), min(n-k+1, pos[a[i]]), 1);
		ans = ans + tree.tree[1];
		tree.update(1, 1, n-k+1, max(1, pos[a[i-k+1]]-k+1), min(n-k+1, pos[a[i-k+1]]), -1);
	}

	printf("%d %d\n", ans.mx, ans.cnt);
}

int main(){
	scanf("%d %d %d", &n, &k, &q);

	for (int i=1;i<=n;i++) scanf("%d", a+i);
	for (int i=1;i<=n;i++){
		scanf("%d", b+i);
		pos[b[i]] = i;
	} 

	naive();

	while(q--){
		int x;
		scanf("%d", &x);
		swap(a[x], a[x+1]);

		naive();
	}
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |  scanf("%d %d %d", &n, &k, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:80:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  for (int i=1;i<=n;i++) scanf("%d", a+i);
      |                         ~~~~~^~~~~~~~~~~
Main.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |   scanf("%d", b+i);
      |   ~~~~~^~~~~~~~~~~
Main.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |   scanf("%d", &x);
      |   ~~~~~^~~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 33.0

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

Subtask #4
0 / 7.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 33.0

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