oj.uz

답안 #792747

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
792747 2023-07-25T08:28:50 Z 박상훈(#10052) Line Town (CCO23_day1problem3) C++17
13 / 25
 743 ms 23840 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

constexpr ll INF = 4e18;

struct Seg{
	int tree[2002000];
	int sz;

	void init(int n){
		sz = n;
		fill(tree, tree+sz*2, 0);
	}

	void update(int p, ll x){
		p += sz;
		tree[p] = x;
		for (p>>=1;p;p>>=1) tree[p] = tree[p<<1] + tree[p<<1|1];
	}

	int query(int l, int r){
		++r;
		int ret = 0;
		for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
			if (l&1) ret += tree[l++];
			if (r&1) ret += tree[--r];
		}

		return ret;
	}
}tree, tree2;

int a[500500], I[500500];
ll dp[2][500500];

int cnt2[2], col_b[500500], col_f[500500], col[500500];

int f(int s, int e, int val){
	if ((e-s)%2 == 0) return val;
	return -val;
}

int main(){
	int n;
	scanf("%d", &n);
	for (int i=1;i<=n;i++) scanf("%d", a+i);

	for (int i=1;i<=n;i++){
		if (f(i, 0, a[i]) == -abs(a[i])) col[i] = 0;
		else col[i] = 1;
	}

	for (int i=1;i<=n;i++) I[i] = i;
	sort(I+1, I+n+1, [&](int i, int j){return abs(a[i]) < abs(a[j]);});
	tree.init(n+1);
	tree2.init(n+1);

	for (int i=1,r;i<=n;i=r+1){
		r = i;
		while(r+1<=n && abs(a[I[i]]) == abs(a[I[r+1]])) r++;

		for (int t=i;t<=r;t++) tree.update(I[t], 1);

		if (abs(a[I[i]])==0){
			dp[0][r] = 0;
			dp[1][r] = 0;
			continue;
		}

		for (int t=i;t<=r;t++) tree2.update(I[t], 1);

		for (int z=0;z<2;z++){
			int len = r;
			int cnt = r-i+1;
			dp[z][len] = INF;

			for (int s=0;s<2;s++){

				// init here
				vector<int> V[2], V2[2];
				cnt2[0] = cnt2[1] = 0;

				for (int t=i;t<=r;t++){
					int idx = I[t];

					V[col[idx]].push_back(tree.query(1, idx));
					V2[col[idx]].push_back(tree2.query(1, idx));
				}

				sort(V[0].begin(), V[0].end());
				sort(V[1].begin(), V[1].end());
				sort(V2[0].begin(), V2[0].end());
				sort(V2[1].begin(), V2[1].end());


				col_f[0] = z^1;
				for (int i=1;i<=cnt;i++){
					col_f[i] = col_f[i-1] ^ 1;
					if (i<=s) cnt2[col_f[i]]++; 
				}

				col_b[len] = ((z+len-1)&1) ^ 1;
				if (len >= len-(cnt-s)+1) cnt2[col_b[len]]++;
				for (int i=len-1;i>=len-(cnt-s)+1;i--){
					col_b[i] = col_b[i+1] ^ 1;
					cnt2[col_b[i]]++;
				}

				// printf("\ni = %d, z = %d, s = %d -> cnt = (%d, %d) / sz = (%d, %d)\n", i, z, s, cnt2[0], cnt2[1], (int)V[0].size(), (int)V[1].size());

				if (cnt2[0]!=(int)V[0].size() || cnt2[1]!=(int)V[1].size()) continue;

				int cp[2] = {col_f[s+1], col_f[s+2]};
				int cq[2] = {col_b[len - (cnt-s) + 1], col_b[len - (cnt-s) + 2]};

				int pp[2] = {0, 0}, pq[2] = {0, 0};
				if (s==1) {
					pp[1] = 1;
					if (cq[0]==z) pq[0]++;
					else pq[1]++;
				}

				ll cst = 0, cst2 = 0;
				cnt2[0] = cnt2[1] = 0;
				for (int i=1;i<=s;i++){
					cst += abs(V[col_f[i]][cnt2[col_f[i]]] - i);
					cst2 += abs(V2[col_f[i]][cnt2[col_f[i]]] - i);
					
					cnt2[col_f[i]]++;
				} 

				for (int i=len-(cnt-s)+1;i<=len;i++){
					cst += abs(V[col_b[i]][cnt2[col_b[i]]] - i);
					cst2 += abs(V2[col_b[i]][cnt2[col_b[i]]] - (i-len+cnt));
					
					cnt2[col_b[i]]++;
				}

				int nz = z ^ s;

				// printf("i = %d, z = %d, s = %d -> cst = %lld\n", i, z, s, cst);


				for (int k=s;k<=cnt;k+=2){
					dp[z][len] = min(dp[z][len], dp[nz][i-1] + cst - cst2 / 2);
					if (k+2 > cnt) break;

					cst -= abs(V[cq[0]][pq[0]] - (len - (cnt-k) + 1));
					cst -= abs(V[cq[1]][pq[1]] - (len - (cnt-k) + 2));

					cst2 -= abs(V2[cq[0]][pq[0]] - (k+1));
					cst2 -= abs(V2[cq[1]][pq[1]] - (k+2));

					pq[0]++, pq[1]++;

					cst += abs(V[cp[0]][pp[0]] - (k+1));
					cst += abs(V[cp[1]][pp[1]] - (k+2));

					cst2 += abs(V2[cp[0]][pp[0]] - (k+1));
					cst2 += abs(V2[cp[1]][pp[1]] - (k+2));

					pp[0]++, pp[1]++;
				}
			}

			// printf("%d %d -> %lld\n", i, z, dp[z][i]);
		}

		for (int t=i;t<=r;t++) tree2.update(I[t], 0);


		// assert(i==r);

		// // abs distinct
		// int pos = I[i];
		// for (int z=0;z<2;z++){
		// 	dp[z][i] = INF;

		// 	if (f(pos, z, a[pos]) == -abs(a[pos])) dp[z][i] = min(dp[z][i], dp[z^1][i-1] + tree.query(1, pos-1));
		// 	if (f(pos, z+i-1, a[pos]) == abs(a[pos])) dp[z][i] = min(dp[z][i], dp[z][i-1] + tree.query(pos+1, n));

		// 	if (i==1) dp[z][i] = 0;

		// 	// printf("%d %d -> %lld\n", z, i, dp[z][i]);
		// }

		// tree.update(pos, 1);
	}

	if (dp[1][n]==INF) printf("-1\n");
	else printf("%lld\n", dp[1][n]);
}

Compilation message

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

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 340 KB Output is correct

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 461 ms 23344 KB Output is correct
16 Correct 470 ms 23628 KB Output is correct
17 Correct 471 ms 23444 KB Output is correct
18 Correct 461 ms 23632 KB Output is correct
19 Correct 467 ms 23076 KB Output is correct
20 Correct 494 ms 23188 KB Output is correct
21 Correct 478 ms 23284 KB Output is correct
22 Correct 460 ms 23220 KB Output is correct
23 Correct 471 ms 23220 KB Output is correct
24 Correct 462 ms 23260 KB Output is correct

Subtask #3
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Incorrect 0 ms 340 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 461 ms 23344 KB Output is correct
16 Correct 470 ms 23628 KB Output is correct
17 Correct 471 ms 23444 KB Output is correct
18 Correct 461 ms 23632 KB Output is correct
19 Correct 467 ms 23076 KB Output is correct
20 Correct 494 ms 23188 KB Output is correct
21 Correct 478 ms 23284 KB Output is correct
22 Correct 460 ms 23220 KB Output is correct
23 Correct 471 ms 23220 KB Output is correct
24 Correct 462 ms 23260 KB Output is correct
25 Incorrect 0 ms 340 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #5
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct

Subtask #6
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 480 ms 23692 KB Output is correct
15 Correct 674 ms 23768 KB Output is correct
16 Correct 662 ms 23796 KB Output is correct
17 Correct 660 ms 23716 KB Output is correct
18 Correct 743 ms 23792 KB Output is correct
19 Correct 663 ms 23780 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 530 ms 23736 KB Output is correct
23 Correct 504 ms 23784 KB Output is correct
24 Correct 471 ms 23840 KB Output is correct

Subtask #7
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Incorrect 0 ms 340 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 461 ms 23344 KB Output is correct
16 Correct 470 ms 23628 KB Output is correct
17 Correct 471 ms 23444 KB Output is correct
18 Correct 461 ms 23632 KB Output is correct
19 Correct 467 ms 23076 KB Output is correct
20 Correct 494 ms 23188 KB Output is correct
21 Correct 478 ms 23284 KB Output is correct
22 Correct 460 ms 23220 KB Output is correct
23 Correct 471 ms 23220 KB Output is correct
24 Correct 462 ms 23260 KB Output is correct
25 Incorrect 0 ms 340 KB Output isn't correct
26 Halted 0 ms 0 KB -