#include <bits/stdc++.h>
using namespace std;
void test_case() {
int a, b, c, n; cin >> a >> b >> c >> n;
c = min(c, n / 100); n -= c * 100;
b = min(b, n / 10); n -= b * 10;
a = min(a, n); n -= a;
if (n == 0) cout << "YES\n";
else cout << "NO\n";
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--) test_case();
}
We only need to use $100 coins as much as possible first, then $10 coins as much as possible, and finally $1 coins.
#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt,fma")
#endif
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "../debug.h"
#else
#define dbg(...) "11-111"
#endif
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int T; cin >> T;
while(T--) {
int n; cin >> n;
vector<int> a(n), b(n);
long long ans = LLONG_MIN, sum = 0, sa = 0, sb = 0;
for(auto &i: a) cin >> i;
for(auto &i: b) cin >> i, sum += i;
ans = 2 * a.back() - sum;
for(int i = n - 1 ; i >= 0 ; i--) {
sa += a[i], sb += b[i];
ans = max(ans, min((sa - a.back()) - (sb - b[i]), sa - (sum - b.back())));
}
cout << ans << '\n';
}
return 0;
}
Consider enumerate $$$i_a$$$ from $$$1$$$ to $$$n$$$.
For a fixed $$$i_a$$$,Bob has only two possible optimal options:choose $$$i_b=1 or i_a+1(if i_a \neq n)$$$.So Bob chooses $$$min(a_{i_a}+...+a_n-(b_1+...+b_{n-1}),a_{i_a}+...+a_{n-1}-(b_{i_a+1}+...+b_n))$$$.
Note $$$score_i$$$ as the answer for fixed $$$i_a=i$$$,the final answer is $$$max(score_i)$$$.
#include <bits/stdc++.h>
using namespace std;
#define int long long
void test_case() {
int n; cin >> n;
string s; cin >> s;
int same = 1, cnt = 0;
for (int i = 1; i < n; i++) {
if (s[i] != s[i - 1]) same = 0;
same++;
if (same >= 3) cnt += same - 2;
}
for (int i = 0; i < n; i += 2) s[i] = '1' + '0' - s[i];
same = 1;
for (int i = 1; i < n; i++) {
if (s[i] != s[i - 1]) same = 0;
same++;
cnt += (same - 1) / 2;
}
cout << cnt << '\n';
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--) test_case();
}
The key observation is super palindromes are strings of length $$$\geq 3$$$ with all numbers equal, or a string with alternating $$$0-1$$$ (and has odd length).
After that, we only need to enumerate $$$i$$$ from $$$i$$$ to $$$n$$$ and count super palindromes that ends with $$$i$$$.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 210000
void test_case() {
int n; cin >> n;
int ptr = 1, need = n * (n + 1) / 4;
vector<int> bad;
for (int i = 1; i <= n; i++) {
while (ptr <= i) ptr++;
while (ptr <= n && (n + ptr) * (n - ptr + 1) / 2 >= need &&
(n + ptr) * (n - ptr + 1) / 2 - (n - i - (n - ptr + 1)) * (n - ptr + 1) > need) ptr++;
if ((n + ptr) * (n - ptr + 1) / 2 < need) {
bad.push_back(i);
need -= i;
continue;
}
cout << i << ' ';
}
for (int x : bad) cout << x << ' ';
cout << '\n';
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--) test_case();
}
Let $$$p$$$ be the lexicographically smallest balanced permutation of length $$$n$$$ and $$$x$$$ be the integer such that $$$1 \leq x < n$$$ and $$$p_1+p_2+⋯+p_x=p_{x+1}+p_{x+2}+⋯+p_n$$$. Let's take a look to the lexicographically smallest (not necessary balanced) permutation of length $$$n$$$, which is $$${1,2,\dots,n}$$$.
Let $$$m$$$ be the largest value such that $$$1+2+\dots+m \leq (m+1)+(m+2)+\dots+n$$$. Notice that since $$$m$$$ is as large as possible, $$$1+2+\dots+m+(m+1) > (m+2)+(m+3)+\dots+n$$$. Which means, $$$x < m+1$$$ for \textbf{any} balanced permutation of length $$$n$$$ (since no matter how you rearrange the permutation, $$$p_1+p_2+⋯+p_{m+1} \geq 1+2+\dots+m+(m+1)$$$). It is also worth noting that $$$m < n$$$. This will be useful later.
Since $$$p$$$ is the lexicographically smallest balanced permutation of length $$$n$$$, we want to greedily shove as much small numbers as possible to the prefix of $$$p$$$, then sort the prefix from smallest to largest. Notice that since $$$x < m+1$$$, it is possible that $$$x = m$$$ in the optimal solution and we can prove that it actually is.
Assume $$$p = {1,2,\dots,n}$$$ (in other words, $$$p_i = i$$$ for all $$$1 \leq i \leq n$$$). Focus on the $$$m$$$ first numbers in the permutation. Let $$$r = \frac{1+2+\dots+n}{2} - (1+2+\dots+m)$$$ (which means $$$r \leq 0$$$). Since $$$1+2+\dots+m+(m+1) > (m+2)+(m+3)+\dots+n$$$, $$$r < m+1$$$ which means $$$r \leq m$$$. This means that in order to make sure $$$p_1+p_2+⋯+p_m = p_{m+1}+p_{m+2}+⋯+p_n$$$, we can just add $$$1$$$ to all $$$p_j$$$ where $$$m-r+1 \leq j \leq m$$$ and $$$p_1+p_2+⋯+p_m$$$ will still be a possible prefix of the permutation, since $$$p_m \leq n$$$ and $$$p_1 < p_2 < \dots < p_m$$$ will still be satisfied after the changes (because $$$m < n$$$ and $$$p_1 < p_2 < \dots < p_{m-r} < p_{m-r+1} < \dots < p_m$$$). Now that we know $$$x = m$$$, how can we make $$$p$$$ as small lexicographically as possible?
Let's focus on the first $$$m$$$ numbers inside $$$p$$$. Set $$$p_i := i$$$ for all $$$1 \leq i \leq m$$$. We will modify this later. Now, since $$$r = \frac{1+2+\dots+n}{2} - (1+2+\dots+m)$$$, we need to add the value $$$r$$$ to the first $$$m$$$ numbers by spreading the addition. However, to make sure $$$p$$$ is as small as possible, we have to greedily add some value to some last numbers inside $$${p_1,p_2,\dots,p_m}$$$ such that the added value is $$$r$$$ and $$${p_1,p_2,\dots,p_m}$$$ is lexicographically smallest. In other words, we can do this procedure to construct the first $$$m$$$ numbers inside the permutation:
\begin{itemize} \item Set $$$p_i := i$$$ for all $$$1 \leq i \leq m$$$. \item Let $$$j = m$$$. While $$$r > 0$$$, add $$$\min(r,k-j)$$$ to $$$p_j$$$, decrease $$$r$$$ by $$$\min(r,k-j)$$$, and decrease $$$j$$$ by $$$1$$$ where $$$k$$$ is the maximum integer such that $$$k \leq n$$$ and $$$k$$$ \textbf{currently} does not appear inside $$${p_1,p_2,\dots,p_m}$$$. \end{itemize}
For the last $$$n-m$$$ numbers, notice that we can just fill these with all the numbers that are not used in the first $$$m$$$ numbers, since the sum of the numbers will automatically be equal to $$$p_1+p_2+\dots+p_m = \frac{1+2+\dots+n}{2}$$$. Do note that to make sure $$$p$$$ is as small as possible, $$$p_{m+1} < p_{m+2} < \dots < p_n$$$ need to be satisfied.
Bonus question: can you guess which $$$n$$$ values results in no possible balanced permutation?
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
int T,n;
ll sum;
int p[N],pos[N],sig[N],BIT[N];
void add(int p,int v)
{
for(int i=p;i<=n;i+=(i&-i)) BIT[i]+=v;
}
int getsum(int p)
{
int s=0;
for(int i=p;i;i-=(i&-i)) s+=BIT[i];
return s;
}
struct nod
{
int l,r,sum,tag;
nod *lc,*rc;
};
struct Segtree
{
nod *root;
Segtree()
{
build(&root,1,n);
}
void newnod(nod **p,int L,int R)
{
*p=new nod;
(*p)->l=L;(*p)->r=R;(*p)->sum=1;(*p)->tag=0;
}
void build(nod **p,int L,int R)
{
newnod(p,L,R);
if(L==R) return ;
int M=(L+R)>>1;
build(&(*p)->lc,L,M);
build(&(*p)->rc,M+1,R);
(*p)->sum=(*p)->lc->sum+(*p)->rc->sum;
}
void pushdown(nod *p)
{
if(p->tag) p->sum*=-1;
if(p->l!=p->r)
{
p->lc->tag^=p->tag;
p->rc->tag^=p->tag;
}
p->tag=0;
}
void flip(int L,int R)
{
_flip(root,L,R);
}
void _flip(nod *p,int L,int R)
{
pushdown(p);
if(p->l==L&&p->r==R)
{
p->tag^=1;
return ;
}
int M=(p->l+p->r)>>1;
if(R<=M) _flip(p->lc,L,R);
else if(L>M) _flip(p->rc,L,R);
else _flip(p->lc,L,M),_flip(p->rc,M+1,R);
pushdown(p->lc);pushdown(p->rc);
p->sum=p->lc->sum+p->rc->sum;
}
int getsum(int L,int R)
{
return _getsum(root,L,R);
}
int _getsum(nod *p,int L,int R)
{
pushdown(p);
if(p->l==L&&p->r==R) return p->sum;
int M=(p->l+p->r)>>1;
if(R<=M) return _getsum(p->lc,L,R);
else if(L>M) return _getsum(p->rc,L,R);
else return _getsum(p->lc,L,M)+_getsum(p->rc,M+1,R);
}
};
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&p[i]),pos[p[i]]=i;
Segtree TR;
sum=0;
for(int i=1;i<=n;i++) BIT[i]=0;
for(int i=1;i<=n;i++)
{
sig[i]=(getsum(p[i])&1)?-1:1;
add(p[i],1);
}
for(int i=1;i<=n;i++)
{
sum+=((pos[i]&1)?1:-1)*(ll)(pos[i]-1)*i;
sum+=(ll)(sig[pos[i]]*TR.getsum(pos[i],pos[i])*TR.getsum(pos[i],n))*i;
TR.flip(pos[i],n);
}
printf("%I64d\n",sum);
}
return 0;
}
Consider calculating the contribution of each element separately.
For an element,we can observe that only elements with values less than it and indexes greater than it increase its index by $$$1$$$.
We represent these 'influence' as a sequence $$$s$$$ containing only $$$1$$$ and $$$-1$$$.At the beginning,$$$s_i=1$$$ for all $$$1\leq i \leq n$$$.We calculate the contribution of each element in ascending order of values.
Assuming we have already calculated the contribution of $$$x$$$,then we do filp $$$s_{pos_x},...,s_n$$$ (flip denotes making $$$1$$$ to $$$-1$$$ and make $$$-1$$$ to $$$1$$$) and calculate the contribution of $$$x+1$$$ using updated $$$s$$$.
#include <bits/stdc++.h>
// v.erase( unique(all(v)) , v.end() ) -----> removes duplicates and resizes the vector as so
using namespace std;
#define IO_file freopen("output.txt","w",stdout), freopen("input.txt","r",stdin);
#define ll long long
#define lld long double
const lld pi = 3.14159265358979323846;
#define pb push_back
#define pf push_front
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
constexpr int mod = (int)(1e9 + 7);
#define log(x) (31^__builtin_clz(x)) // Easily calculate log2 on GNU G++ compilers
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int x, int y) {
return uniform_int_distribution<int>(x, y)(rng);
}
struct AhoCorasick {
//The trie
struct tr_node {
int adj[26];
int link;
int parent;
int term;
tr_node() {
link = 0;
parent = -1;
term = 0;
memset(adj, -1, sizeof(adj));
}
};
vector<tr_node> tr;
int tick = 0;//--> tick is the number of nodes in the trie
AhoCorasick() {
init();
}
void init() {
tr.clear();
tr.push_back(tr_node());
tick = 0;
tr[0].link = -1;
}
void insert(const string &s) {
int p = 0;
for(int i=0;i<s.size();i++){
if(tr[p].adj[s[i]-'a'] == -1){
tr.push_back(tr_node());
tr[p].adj[s[i]-'a'] = (++tick);
}
p = tr[p].adj[s[i]-'a'];
}
tr[p].term++;
}
//build the suffix links and transitions for each node
//in Amortized O(sizeof the strings inserted in the trie + No.nodes*sizeofAlphabet).
//this implementation has less memory usage, so you choose which to run.
//you can add an additional array "adj" to build a tree over the suffix links.
vector<int> character;
//we build the suffix links only and we calculate transitions on the run
int trans(int p, int c) {
//p is the node, c is the character
while(p != -1 && tr[p].adj[c] == -1) p = tr[p].link;
if(p == -1) return 0;//we return the root
return tr[p].adj[c];
}
void build() {
character.resize(tick+5);
queue<int> q; q.push(0);
character[0] = -1;
while(!q.empty()){
int p = q.front(); q.pop();
if(p){
if(tr[tr[p].parent].link != -1){
tr[p].link = trans(tr[tr[p].parent].link, character[p]);
}
if(tr[p].link != -1){
tr[p].term += tr[tr[p].link].term;
}
}
for(int i = 0 ; i < 26 ; i++){
if(tr[p].adj[i] != -1){
tr[tr[p].adj[i]].parent = p;
character[tr[p].adj[i]] = i;
q.push(tr[p].adj[i]);
continue;
}
}
}
}
}Aho[20];
vector<string> info[20];
void add(const string &s) {
for(int i = 0 ; i < 20 ; i++){
if(info[i].size() == 0){
for(int j = 0 ; j < i ; j++){
for(string x : info[j]){
info[i].pb(x);
}
vector<string> v;
info[j].swap(v);
Aho[j].init();
}
info[i].pb(s);
for(string x : info[i]){
Aho[i].insert(x);
}
Aho[i].build();
break;
}
}
}
ll query(const string &s) {
ll cnt = 0;
for(int i = 0 ; i < 20 ; i++){
if(info[i].empty()) continue;
int p = 0;
for(int j = 0 ; j < s.size() ; j++){
p = Aho[i].trans(p, s[j] - 'a');
cnt += Aho[i].tr[p].term;
}
}
return cnt;
}
const int N = 2e5 + 7;
const int M = 4e5 + 7;
int n, par[M], fake_node;
vector<int> adj[M];
string str[N];
string qry_str[N];
void init() {
for(int i = 0 ; i <= 2 * n ; i++){
par[i] = i;
}
fake_node = n;
}
int find(int x) {
if(x == par[x]) return x;
return par[x] = find(par[x]);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if(x == y) return;
fake_node++;
par[x] = fake_node;
par[y] = fake_node;
adj[fake_node].pb(x);
adj[fake_node].pb(y);
}
int in[M], out[M], tick, node_at[M];
void dfs(int node) {
in[node] = ++tick;
node_at[tick] = node;
for(int u : adj[node]){
dfs(u);
}
out[node] = tick;
}
vector<pair<int, bool > > queries2[M]; // the query indx, 0 pos | 1 neg
int main()
{ios_base::sync_with_stdio(0),cin.tie(0);
cin>>n;
init();
for(int i = 1 ; i <= n ; i++){
cin>>str[i];
}
int q; cin>>q;
vector<pair<int, int> > queries; // the node, the query indx
vector<int> quests;
for(int i = 0 ; i < q ; i++){
int t; cin>>t;
if(t == 1){
int a, b; cin>>a>>b;
merge(a, b);
continue;
}
int v; cin>>v;
cin>>qry_str[i];
v = find(v);
queries.pb({v, i});
quests.pb(i);
}
for(int i = 1 ; i < n ; i++){
merge(i, i + 1);
}
int root = find(1);
dfs(root);
for(pair<int, int> X : queries){
int v = X.first; int indx = X.second;
queries2[out[v]].pb({indx, 0});
if(v != root){
queries2[in[v] - 1].pb({indx, 1});
}
}
ll ans[q] = {};
for(int i = 1 ; i <= tick ; i++){
int u = node_at[i];
if(u <= n){
add(str[u]);
}
for(pair<int, int> X : queries2[i]){
int indx = X.first;
bool o = X.second;
if(o){
ans[indx] -= query(qry_str[indx]);
}
else {
ans[indx] += query(qry_str[indx]);
}
}
}
for(int i = 0 ; i < quests.size() ; i++){
cout<<ans[quests[i]]<<'\n';
}
return 0;
}
We will answer the queries offline.
We will use DSU to process queries of the first type.
For each query of the first type, we will create a new node $$$H$$$ and connect both $$$u$$$ and $$$v$$$ to it.
For each query of the second type, we will add the query to the query-list of the root of the component $$$u$$$ is in.
Now we merge all the components together and we notice that now we have a tree and each query of the second type turns out to be a subtree query in our tree.
We run euler tour on the tree and now each subtree query is a range query in the euler tour array, for example it's a query on $$$[L, R]$$$, the answer to it is the answer on $$$[1, R]$$$ minus the answer on $$$[1, L - 1]$$$.
to answer these prefix queries we will use dynamic Aho-Corasick to add the strings and answer the queries.
The amortized time complexity of this solution is $$$O(N * log(N) * AlphabetSize)$$$.
