Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
s = s.substr(0, s.size() / 2);
int k = unique(s.begin(), s.end()) - s.begin();
cout << (k == 1 ? "NO" : "YES") << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
ans = 0
pr = [0] * (n + 1)
for i in range(n):
pr[i + 1] = pr[i] + a[i]
for i in range(k + 1):
ans = max(ans, pr[n - (k - i)] - pr[2 * i])
print(ans)
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (int& x : a) cin >> x;
n = unique(a.begin(), a.end()) - a.begin();
int ans = n;
for (int i = 0; i + 2 < n; ++i) {
ans -= (a[i] < a[i + 1] && a[i + 1] < a[i + 2]);
ans -= (a[i] > a[i + 1] && a[i + 1] > a[i + 2]);
}
cout << ans << '\n';
}
}
1832D1 - Red-Blue Operations (Easy Version)
Idea: BledDest
Tutorial
Tutorial is loading...
1832D2 - Red-Blue Operations (Hard Version)
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
n, q = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
pr = [10**9 for i in range(n + 1)]
for i in range(n):
pr[i + 1] = min(pr[i], a[i] - i)
s = sum(a) - n * (n - 1) // 2
ans = []
for k in map(int, input().split()):
if k < n:
ans.append(min(pr[k] + k, a[k]))
continue
if k % 2 == n % 2:
ns = s - pr[n] * n
ans.append(pr[n] + k - (max(0, (k - n) // 2 - ns) + n - 1) // n)
else:
nmn = min(pr[n - 1], a[n - 1] - k)
ns = (s + (n - 1) - k) - nmn * n
ans.append(nmn + k - (max(0, (k - (n - 1)) // 2 - ns) + n - 1) // n)
print(*ans)
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int add(int x, int y, int mod = MOD)
{
return ((x + y) % mod + mod) % mod;
}
int mul(int x, int y, int mod = MOD)
{
return (x * 1ll * y) % mod;
}
int binpow(int x, int y, int mod = MOD)
{
int z = add(1, 0, mod);
while(y > 0)
{
if(y % 2 == 1) z = mul(z, x, mod);
y /= 2;
x = mul(x, x, mod);
}
return z;
}
vector<int> psum(vector<int> v)
{
vector<int> ans(1, 0);
for(auto x : v) ans.push_back(add(ans.back(), x));
return ans;
}
int main()
{
int n;
cin >> n;
vector<int> a(n);
cin >> a[0];
int x, y, m, k;
cin >> x >> y >> m >> k;
for(int i = 1; i < n; i++)
a[i] = add(mul(a[i - 1], x, m), y, m);
for(int i = 0; i <= k; i++)
a = psum(a);
long long ans = 0;
for(int i = 1; i <= n; i++)
ans ^= (a[i + 1] * 1ll * i);
cout << ans << endl;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
struct seg{
int l, r;
};
int n;
vector<long long> dp_before, dp_cur;
vector<vector<long long>> bst;
void compute(int l, int r, int optl, int optr){
if (l > r) return;
int mid = (l + r) / 2;
pair<long long, int> best = {-1, -1};
for (int k = optl; k <= min(mid, optr); k++)
best = max(best, {(k ? dp_before[k - 1] : 0) + bst[k][mid], k});
dp_cur[mid] = best.first;
int opt = best.second;
compute(l, mid - 1, optl, opt);
compute(mid + 1, r, opt, optr);
}
struct node{
long long c0;
int c1;
};
vector<node> f;
void update(int x, int a, int b){
for (int i = x; i < int(f.size()); i |= i + 1){
f[i].c0 += b;
f[i].c1 += a;
}
}
void update(int l, int r, int a, int b){
update(l, a, b);
update(r, -a, -b);
}
long long get(int pos, int x){
long long res = 0;
for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
res += f[i].c0 + f[i].c1 * 1ll * pos;
return res;
}
int main() {
int k, x, m;
scanf("%d%d%d%d", &n, &k, &x, &m);
vector<seg> a(n);
forn(i, n) scanf("%d%d", &a[i].l, &a[i].r);
sort(a.begin(), a.end(), [&](const seg &a, const seg &b){
return a.l + a.r < b.l + b.r;
});
vector<int> pos;
forn(i, n){
pos.push_back(a[i].l);
pos.push_back(a[i].r - m);
}
sort(pos.begin(), pos.end());
pos.resize(unique(pos.begin(), pos.end()) - pos.begin());
int cds = pos.size();
vector<array<int, 4>> npos(n);
forn(i, n){
npos[i][0] = lower_bound(pos.begin(), pos.end(), a[i].l - m) - pos.begin();
npos[i][1] = lower_bound(pos.begin(), pos.end(), a[i].l) - pos.begin();
npos[i][2] = lower_bound(pos.begin(), pos.end(), a[i].r - m) - pos.begin();
npos[i][3] = lower_bound(pos.begin(), pos.end(), a[i].r) - pos.begin();
}
vector<long long> pr(n + 1);
forn(i, n) pr[i + 1] = pr[i] + x - (m + a[i].r - a[i].l);
auto upd = [&](int i){
if (a[i].r - a[i].l >= m){
update(npos[i][0], npos[i][1], 1, m - a[i].l);
update(npos[i][1], npos[i][2], 0, m);
update(npos[i][2], npos[i][3], -1, a[i].r);
}
else{
update(npos[i][0], npos[i][2], 1, m - a[i].l);
update(npos[i][2], npos[i][1], 0, a[i].r - a[i].l);
update(npos[i][1], npos[i][3], -1, a[i].r);
}
};
bst.resize(n, vector<long long>(n, -1));
vector<vector<int>> opt(n, vector<int>(n));
forn(r, n) for (int l = r; l >= 0; --l){
if (l == r) f.assign(cds, {0, 0});
upd(l);
int L = (l == r ? (l == 0 ? 0 : opt[l - 1][l - 1]) : opt[l][r - 1]);
int R = (l == r ? int(pos.size()) - 1 : opt[l + 1][r]);
for (int k = L; k <= R; ++k){
long long cur = pr[r + 1] - pr[l] + get(pos[k], k);
if (cur > bst[l][r]){
bst[l][r] = cur;
opt[l][r] = k;
}
}
}
dp_before.resize(n);
dp_cur.resize(n);
for (int i = 0; i < n; i++)
dp_before[i] = bst[0][i];
for (int i = 1; i < k; i++){
compute(0, n - 1, 0, n - 1);
dp_before = dp_cur;
}
printf("%lld\n", dp_before[n - 1]);
return 0;
}