Many thanks to infinitepro, BledDest and alimq for helping me write the editorials.
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
int solveTestCase() {
int n;
cin >> n;
string s = "989";
if (n <= 3)
return cout << s.substr(0, n) << "\n", 0;
cout << s;
for (int i = 3; i < n; i++)
cout << (i - 3) % 10;
cout << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
solveTestCase();
}
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5;
int a[N], n;
int isValley(int i) {
return (i > 0 && i < n - 1 && a[i] < a[i - 1] && a[i] < a[i + 1]);
}
int isHill(int i) {
return (i > 0 && i < n - 1 && a[i] > a[i - 1] && a[i] > a[i + 1]);
}
int solveTestCase() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
int is[n] = {};
int s = 0;
for (int i = 1; i < n - 1; i++) {
if (isHill(i) || isValley(i))
is[i] = 1, s++;
}
int ans = s;
for (int i = 1; i < n - 1; i++) {
int temp = a[i];
a[i] = a[i - 1];
ans = min(ans, s - is[i - 1] - is[i] - is[i + 1] + isHill(i - 1) + isValley(i - 1) + isHill(i) + isValley(i) + isHill(i + 1) + isValley(i + 1));
a[i] = a[i + 1];
ans = min(ans, s - is[i - 1] - is[i] - is[i + 1] + isHill(i - 1) + isValley(i - 1) + isHill(i) + isValley(i) + isHill(i + 1) + isValley(i + 1));
a[i] = temp;
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
solveTestCase();
}
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5;
vector<vector<int>> a(3, vector<int>());
vector<int> n(3, 0);
int calc() {
int ans = 0, m1 = a[1][0], m2 = a[2][0], s1 = 0, s2 = 0;
for (int i : a[0]) ans += i;
for (int i = 1; i < n[1]; i++) s1 += a[1][i];
for (int i = 1; i < n[2]; i++) s2 += a[2][i];
ans += max({s2 - m1 + s1 - m2, m2 + s2 - m1 - s1, m1 + s1 - m2 - s2});
return ans;
}
int solveTestCase() {
cin >> n[0] >> n[1] >> n[2];
a[0].resize(n[0]);
a[1].resize(n[1]);
a[2].resize(n[2]);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < n[i]; j++)
cin >> a[i][j];
sort(a[i].begin(), a[i].end());
}
int ans = -1e18;
ans = max(ans, calc());
swap(a[0], a[1]), swap(n[0], n[1]);
ans = max(ans, calc());
swap(a[0], a[2]), swap(n[0], n[2]);
ans = max(ans, calc());
cout << ans;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
//cin >> t;
while (t--)
solveTestCase();
}
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5005, mod = 1e9 + 7;
int dp[N][N], cnt[N], a[N], q, n, k;
void pre() {
for (int i = 0; i < n; i++)
dp[i][0] = 1;
for (int j = 1; j < N; j++) {
dp[0][j] = dp[1][j - 1];
for (int i = 1; i < n - 1; i++)
dp[i][j] = (dp[i - 1][j - 1] + dp[i + 1][j - 1]) % mod;
dp[n - 1][j] = dp[n - 2][j - 1];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j <= k; j++)
cnt[i] += dp[i][j] * dp[i][k - j], cnt[i] %= mod;
}
}
void solveTestCase() {
int ans = 0;
for (int i = 0; i < n; i++)
cin >> a[i], ans += a[i] * cnt[i], ans %= mod;
while (q--) {
int i, x;
cin >> i >> x;
i--;
ans -= (a[i] * cnt[i]) % mod, ans += mod, ans %= mod;
a[i] = x;
ans += (a[i] * cnt[i]), ans %= mod;
cout << ans << "\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> k >> q;
pre();
int t = 1;
//cin >> t;
while (t--)
solveTestCase();
}
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5;
vector<int> adj[N];
int a[N], par[N], n;
map<int, vector<int>> v, times;
int euler[N * 2 - 1], tin[N], tout[N], c = 0;
set<pair<int, int>> g;
int dp[N], ans;
void dfs(int v, int p = -1) {
par[v] = p;
tin[v] = c;
euler[c++] = v;
for (int i : adj[v]) {
if (i == p)
continue;
dfs(i, v);
euler[c++] = v;
}
tout[v] = c - 1;
}
void examine(int v) {
int sum = 0;
for (int i : adj[v]) {
if (i == par[v])
continue;
int count = upper_bound(times[a[v]].begin(), times[a[v]].end(), tout[i]) - lower_bound(times[a[v]].begin(), times[a[v]].end(), tin[i]);
if (count > 0)
g.insert({v, i});
sum += count;
}
sum = times[a[v]].size() - sum - 1;
if (sum)
g.insert({v, par[v]});
}
int setup(int v) {
for (int i : adj[v]) {
if (i != par[v])
dp[v] += setup(i);
}
return dp[v] + g.count({v, par[v]});
}
void reroot(int v) {
if (dp[v] == g.size())
ans++;
for (int i : adj[v]) {
if (i == par[v])
continue;
dp[v] -= dp[i];
dp[v] -= g.count({i, v});
dp[i] += dp[v];
dp[i] += g.count({v, i});
reroot(i);
dp[i] -= g.count({v, i});
dp[i] -= dp[v];
dp[v] += g.count({i, v});
dp[v] += dp[i];
}
}
int solveTestCase() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--, v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(0);
for (int i = 0; i < n; i++)
v[a[i]].push_back(i);
for (auto i : v) {
if (i.second.size() == 1)
continue;
for (int j : i.second)
times[i.first].push_back(tin[j]);
sort(times[i.first].begin(), times[i.first].end());
for (int j : i.second)
examine(j);
}
setup(0);
reroot(0);
cout << ans;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
//cin >> t;
while (t--)
solveTestCase();
}
UPD: Also, have a look at this comment for an explanation of the sample test case of C.