Submission #1271152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271152		thuhienne	Heavy Light Decomposition (CCO24_day2problem2)	C++20	7 / 25	4091 ms	4536 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e6 + 3;

int n,arr[500009];
int dp[500009];

int freq[500009];

int main() {
	ios_base::sync_with_stdio(0);cin.tie(nullptr);
	//freopen(".inp","r",stdin);
	//freopen(".out","w",stdout);
	cin >> n;
	for (int i = 1;i <= n;i++) cin >> arr[i];
	dp[0] = 1;
	for (int i = 1;i <= n;i++) {
		int lightodd = 0,lighteven = 0;
		for (int j = i;j >= 1;j--) {
			if (freq[arr[j]] == 0) {
				freq[arr[j]] = j;
				if (j % 2 == 0) lighteven++;
				else lightodd++;
			} else if (freq[arr[j]] > 0) {
				int d = freq[arr[j]];
				if (d % 2 == 0) lighteven--;
				else lightodd--;
				freq[arr[j]] = -1;
			}
			if (freq[arr[i]] > 0) { //neu i la light
				int need = (i - j + 2)/2;
				if (i % 2 == 0 && lightodd == 0 && lighteven == need) {
					dp[i] = (dp[i] + dp[j - 1])%mod;
				}
				if (i % 2 != 0 && lighteven == 0 && lightodd == need) {
					dp[i] = (dp[i] + dp[j - 1])%mod;
				}
			} else { //neu i la heavy
				int need = (i - j + 1)/2;
				if (i % 2 != 0 && lightodd == 0 && lighteven == need) {
					dp[i] = (dp[i] + dp[j - 1])%mod;
				}
				if (i % 2 == 0 && lighteven == 0 && lightodd == need) {
					dp[i] = (dp[i] + dp[j - 1])%mod;
				}
			}
		}
		for (int j = i;j >= 1;j--) freq[arr[j]] = 0;
	}
	cout << dp[n];
}

/*
  Nho doi vai em gay
			  co gai ay ngoi duoi goc pho nen tho ...
*/

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 0 / 5
• Subtask 4: 0 / 6
• Subtask 5: 0 / 7