We hope you enjoyed the problems!↵
↵
<spoiler summary="Rate the contest!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:21,option1] Excellent contest↵
- [likes:21,option2] Good contest↵
- [likes:21,option3] Average contest↵
- [likes:21,option4] Bad contest↵
- [likes:21,option5] Horrible contest↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:22,option1] Trivial contest↵
- [likes:22,option2] Easy contest↵
- [likes:22,option3] Average contest↵
- [likes:22,option4] Hard contest↵
- [likes:22,option5] Impossible contest↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
[problem:2209A]↵
↵
- Idea: [user:OtterZ,2026-03-21]↵
↵
- Solution: [user:OtterZ,2026-03-21]↵
↵
- Editorial: [user:OtterZ,2026-03-21]↵
↵
↵
<spoiler summary="Solution">↵
[tutorial:2209A]↵
</spoiler>↵
↵
↵
<spoiler summary="Code (C++)">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
int n,a[109],k;↵
long long C;↵
int main(){↵
int t;↵
scanf("%d",&t);↵
while(t--){↵
scanf("%d %lld %d",&n,&C,&k);↵
for(int i = 1; i <= n; i ++){↵
scanf("%d",&a[i]);↵
}↵
sort(a + 1,a + n + 1);↵
for(int i = 1; i <= n; i ++){↵
if(a[i] > C)↵
break;↵
int o = min(1ll * k,C - a[i]);↵
k -= o;↵
C += a[i] + o;↵
}↵
printf("%lld\n",C);↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:1,option1] Excellent problem↵
- [likes:1,option2] Good problem↵
- [likes:1,option3] Average problem↵
- [likes:1,option4] Bad problem↵
- [likes:1,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:2,option1] Trivial problem↵
- [likes:2,option2] Easy problem↵
- [likes:2,option3] Average problem↵
- [likes:2,option4] Hard problem↵
- [likes:2,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
[problem:2209B]↵
↵
- Idea: [user:OtterZ,2026-03-21]↵
↵
- Solution: [user:OtterZ,2026-03-21]↵
↵
- Editorial: [user:OtterZ,2026-03-21]↵
↵
<spoiler summary="Solution">↵
[tutorial:2209B]↵
</spoiler>↵
↵
<spoiler summary="Code (Python)">↵
~~~~~↵
for _ in range(int(input())):↵
n = int(input())↵
a = list(map(int, input().split()))↵
print(*[max(sum(a[j] < a[i] for j in range(i + 1, n)), sum(a[j] > a[i] for j in range(i + 1, n))) for i in range(n)])↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Code (C++) ">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
int n,a[5009],bcnt,f1[5009],f2[5009];↵
int main(){↵
int t;↵
scanf("%d",&t);↵
while(t--){↵
scanf("%d",&n);↵
for(int i = 1; i <= n; i ++){↵
scanf("%d",&a[i]);↵
}↵
for(int i = n; i >= 1; i --){↵
f1[i] = f2[i] = 0;↵
for(int j = i + 1; j <= n; j ++)↵
f1[i] += (a[i] > a[j]),f2[i] += (a[i] < a[j]);↵
f1[i] = max(f1[i],f2[i]);↵
}↵
for(int i = 1; i < n; i ++)↵
printf("%d ",f1[i]);↵
printf("%d\n",f1[n]);↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:3,option1] Excellent problem↵
- [likes:3,option2] Good problem↵
- [likes:3,option3] Average problem↵
- [likes:3,option4] Bad problem↵
- [likes:3,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:4,option1] Trivial problem↵
- [likes:4,option2] Easy problem↵
- [likes:4,option3] Average problem↵
- [likes:4,option4] Hard problem↵
- [likes:4,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
[problem:2209C]↵
↵
- Idea: [user:__baozii__,2026-01-29]↵
↵
- Solution: [user:__baozii__,2026-01-29]↵
↵
- Editorial: [user:__baozii__,2026-01-29]↵
↵
<spoiler summary="Solution">↵
[tutorial:2209C]↵
</spoiler>↵
↵
<spoiler summary="Code (Python)">↵
~~~~~↵
for _ in range(int(input())):↵
n = int(input())↵
ans = -1↵
for i in range(1, n):↵
print("?", 2 * i + 1, 2 * i + 2, flush=True)↵
if int(input()):↵
ans = 2 * i + 1 ↵
break↵
else:↵
print("?", 1, 3, flush=True)↵
if int(input()):↵
ans = 1↵
else:↵
print("?", 1, 4, flush=True)↵
if int(input()):↵
ans = 1↵
else:↵
ans = 2↵
print("!", ans, flush=True)↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:5,option1] Excellent problem↵
- [likes:5,option2] Good problem↵
- [likes:5,option3] Average problem↵
- [likes:5,option4] Bad problem↵
- [likes:5,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:6,option1] Trivial problem↵
- [likes:6,option2] Easy problem↵
- [likes:6,option3] Average problem↵
- [likes:6,option4] Hard problem↵
- [likes:6,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
[problem:2209D]↵
↵
- Idea: [user:OtterZ,2026-03-21]↵
↵
- Solution: [user:OtterZ,2026-03-21]↵
↵
- Editorial: [user:OtterZ,2026-03-21]↵
↵
<spoiler summary="Solution">↵
[tutorial:2209D]↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
int t,r,g,b,rb,gb,rg;↵
int main(){↵
scanf("%d",&t);↵
while(t--){↵
scanf("%d %d %d",&r,&g,&b);↵
while(((r > 0) + (g > 0) + (b > 0)) >> 1){↵
if(r <= g && r <= b)↵
gb ++,g --,b --;↵
else if(g <= r && g <= b)↵
rb ++,r --,b --;↵
else if(b <= r && b <= g)↵
rg ++,r --,g --;↵
}↵
if(g > 0){↵
putchar('G');↵
while(rg > 0)↵
putchar('R'),putchar('G'),rg --;↵
bool flg = false;↵
while(gb > 0)↵
putchar('B'),putchar('G'),gb --,flg = true;↵
if(flg){↵
while(rb > 0)↵
putchar('B'),putchar('R'),rb --;↵
}↵
else{↵
while(rb > 0)↵
putchar('R'),putchar('B'),rb --;↵
}↵
}↵
else if(r > 0){↵
putchar('R');↵
while(rg > 0)↵
putchar('G'),putchar('R'),rg --;↵
bool flg = false;↵
while(rb > 0)↵
putchar('B'),putchar('R'),rb --,flg = true;↵
if(flg){↵
while(gb > 0)↵
putchar('B'),putchar('G'),gb --;↵
}↵
else{↵
while(gb > 0)↵
putchar('G'),putchar('B'),gb --;↵
}↵
}↵
else{↵
if(b > 0)↵
putchar('B');↵
while(gb > 0)↵
putchar('G'),putchar('B'),gb --;↵
bool flg = false;↵
while(rb > 0)↵
putchar('R'),putchar('B'),rb --,flg = true;↵
if(flg){↵
while(rg > 0)↵
putchar('R'),putchar('G'),rg --;↵
}↵
else{↵
while(rg > 0)↵
putchar('G'),putchar('R'),rg --;↵
}↵
}↵
puts("");↵
}↵
} ↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:7,option1] Excellent problem↵
- [likes:7,option2] Good problem↵
- [likes:7,option3] Average problem↵
- [likes:7,option4] Bad problem↵
- [likes:7,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:8,option1] Trivial problem↵
- [likes:8,option2] Easy problem↵
- [likes:8,option3] Average problem↵
- [likes:8,option4] Hard problem↵
- [likes:8,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
[problem:2209E]↵
↵
- Idea: [user:__baozii__,2026-01-29]↵
↵
- Solution: [user:__baozii__,2026-01-29]↵
↵
- Editorial: [user:__baozii__,2026-01-29]↵
↵
<spoiler summary="Solution">↵
[tutorial:2209E]↵
</spoiler>↵
↵
<spoiler summary="Code (Python)">↵
~~~~~↵
import sys↵
input = lambda: sys.stdin.readline().strip()↵
def work(s):↵
n = len(s)↵
p = [0] * n↵
b = [0] * n↵
for i in range(1, n):↵
j = p[i - 1]↵
while j and s[i] != s[j]:↵
j = p[j - 1]↵
if s[i] == s[j]:↵
j += 1↵
p[i] = j↵
if j == 0:↵
b[i] = 0↵
elif p[j - 1] == 0:↵
b[i] = j↵
else:↵
b[i] = b[j - 1]↵
ans = 0↵
for i in range(n):↵
p[i] = 0↵
p[i] = p[i - b[i]] + 1↵
ans += p[i]↵
return ans↵
↵
for _ in range(int(input())):↵
n, q = map(int, input().split())↵
s = input()↵
for _ in range(q):↵
l, r = map(int, input().split())↵
print(work(s[l - 1:r]))↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:9,option1] Excellent problem↵
- [likes:9,option2] Good problem↵
- [likes:9,option3] Average problem↵
- [likes:9,option4] Bad problem↵
- [likes:9,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:10,option1] Trivial problem↵
- [likes:10,option2] Easy problem↵
- [likes:10,option3] Average problem↵
- [likes:10,option4] Hard problem↵
- [likes:10,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
[problem:2209F]↵
↵
- Idea: [user:OtterZ,2026-03-21]↵
↵
- Solution: [user:OtterZ,2026-03-21]↵
↵
- Editorial: [user:OtterZ,2026-03-21]↵
↵
<spoiler summary="Solution">↵
[tutorial:2209F]↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
const int N = 300009;↵
int n,k,t,a[N],tt[N];↵
long long b[N],ans[N],sum,mxa;↵
struct FLONG{↵
long long val;↵
int nd;↵
FLONG(long long v = 0,int d = 0):↵
val(v),nd(d)↵
{}↵
bool operator<(const FLONG &b)const{↵
return val > b.val || (val == b.val && nd < b.nd);↵
}↵
};↵
set<FLONG>s;↵
set<FLONG> :: iterator o;↵
struct pir{↵
int to,len;↵
pir(int t = 0,int l = 0):↵
to(t),len(l)↵
{}↵
bool operator<(const pir &b)const{↵
return len > b.len || (len == b.len && to < b.to);↵
}↵
}mn[N],se[N],lf[N];↵
vector<int>e[N];↵
void srh(int v,int fa){↵
mn[v] = pir(v,0);↵
se[v] = pir(0,~0x3f3f3f3f);↵
lf[v] = pir(0,~0x3f3f3f3f);↵
for(unsigned i = 0; i < e[v].size(); i ++){↵
if(e[v][i] != fa){↵
srh(e[v][i],v);↵
pir th = mn[e[v][i]];↵
th.len ++;↵
if(th < se[v])↵
swap(th,se[v]);↵
if(se[v] < mn[v])↵
swap(se[v],mn[v]);↵
}↵
}↵
}↵
void gt1(){↵
sum = ans[1] = 0;↵
ans[1] += a[1];↵
for(int i = 2; i <= n; i ++){↵
b[mn[i].to] += a[i];↵
tt[i] = mn[i].to;↵
//printf("%d %d\n",i,tt[i]);↵
}↵
s.clear();↵
for(int i = 2; i <= n; i ++){↵
s.insert(FLONG(b[i],i));↵
}↵
o = s.begin();↵
ans[1] += o -> val;↵
sum += o -> val;↵
for(int i = 1; i < k - 1; i ++){↵
o ++;↵
ans[1] += o -> val;↵
sum += o -> val;↵
}↵
s.insert(FLONG(-1ll,0));↵
s.insert(FLONG(-2ll,0));↵
}↵
void era(int x){↵
FLONG u = FLONG(b[x],x);↵
if(!(*o < u)){↵
o ++;↵
sum += o -> val;↵
sum -= b[x];↵
}↵
s.erase(u);↵
//printf("%d %lld\n",x,sum);↵
}↵
void ins(int x){↵
FLONG u = FLONG(b[x],x);↵
s.insert(u);↵
if(!(*o < u)){↵
sum -= o -> val;↵
sum += b[x];↵
o --;↵
}↵
//printf("%d %lld\n",x,sum);↵
}↵
void stp(int x){↵
era(tt[x]);↵
b[tt[x]] -= a[x];↵
ins(tt[x]);↵
tt[x] = 0; ↵
}↵
void sett(int x,int ttp){↵
tt[x] = ttp;↵
era(tt[x]);↵
b[tt[x]] += a[x];↵
ins(tt[x]);↵
}↵
void srho(int v,int fa){↵
//printf(" %d %d\n",v,fa);↵
if(fa != 0){↵
stp(v);↵
era(v);↵
ins(fa);↵
sett(fa,lf[fa].to);↵
ans[v] = sum + a[v];↵
}↵
for(unsigned i = 0; i < e[v].size(); i ++){↵
if(e[v][i] != fa){↵
pir u = lf[fa];↵
u.len ++;↵
if(mn[v].to == mn[e[v][i]].to)↵
lf[v] = min(u,se[v]);↵
else↵
lf[v] = min(u,mn[v]);↵
srho(e[v][i],v);↵
}↵
}↵
if(fa != 0){↵
ins(v);↵
sett(v,mn[v].to);↵
stp(fa);↵
era(fa);↵
}↵
}↵
int main(){↵
scanf("%d",&t);↵
while(t--){↵
scanf("%d %d",&n,&k);↵
mxa = 0;↵
for(int i = 1; i <= n; i ++){↵
scanf("%d",&a[i]);↵
mxa = max(mxa,1ll * a[i]);↵
e[i].clear();↵
b[i] = 0;↵
}↵
for(int i = 1; i < n; i ++){↵
int u,v;↵
scanf("%d %d",&u,&v);↵
e[u].emplace_back(v);↵
e[v].emplace_back(u);↵
}↵
if(k == 1){↵
printf("%lld\n",mxa);↵
continue;↵
}↵
lf[0].len = ~0x3f3f3f3f;↵
srh(1,0);↵
gt1();↵
srho(1,0);↵
for(int i = 1; i <= n; i ++){↵
mxa = max(mxa,ans[i]);↵
//printf("%lld\n",ans[i]);↵
}↵
printf("%lld\n",mxa);↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:11,option1] Excellent problem↵
- [likes:11,option2] Good problem↵
- [likes:11,option3] Average problem↵
- [likes:11,option4] Bad problem↵
- [likes:11,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:12,option1] Trivial problem↵
- [likes:12,option2] Easy problem↵
- [likes:12,option3] Average problem↵
- [likes:12,option4] Hard problem↵
- [likes:12,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Rate the contest!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:21,option1] Excellent contest↵
- [likes:21,option2] Good contest↵
- [likes:21,option3] Average contest↵
- [likes:21,option4] Bad contest↵
- [likes:21,option5] Horrible contest↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:22,option1] Trivial contest↵
- [likes:22,option2] Easy contest↵
- [likes:22,option3] Average contest↵
- [likes:22,option4] Hard contest↵
- [likes:22,option5] Impossible contest↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
[problem:2209A]↵
↵
- Idea: [user:OtterZ,2026-03-21]↵
↵
- Solution: [user:OtterZ,2026-03-21]↵
↵
- Editorial: [user:OtterZ,2026-03-21]↵
↵
↵
<spoiler summary="Solution">↵
[tutorial:2209A]↵
</spoiler>↵
↵
↵
<spoiler summary="Code (C++)">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
int n,a[109],k;↵
long long C;↵
int main(){↵
int t;↵
scanf("%d",&t);↵
while(t--){↵
scanf("%d %lld %d",&n,&C,&k);↵
for(int i = 1; i <= n; i ++){↵
scanf("%d",&a[i]);↵
}↵
sort(a + 1,a + n + 1);↵
for(int i = 1; i <= n; i ++){↵
if(a[i] > C)↵
break;↵
int o = min(1ll * k,C - a[i]);↵
k -= o;↵
C += a[i] + o;↵
}↵
printf("%lld\n",C);↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:1,option1] Excellent problem↵
- [likes:1,option2] Good problem↵
- [likes:1,option3] Average problem↵
- [likes:1,option4] Bad problem↵
- [likes:1,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:2,option1] Trivial problem↵
- [likes:2,option2] Easy problem↵
- [likes:2,option3] Average problem↵
- [likes:2,option4] Hard problem↵
- [likes:2,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
[problem:2209B]↵
↵
- Idea: [user:OtterZ,2026-03-21]↵
↵
- Solution: [user:OtterZ,2026-03-21]↵
↵
- Editorial: [user:OtterZ,2026-03-21]↵
↵
<spoiler summary="Solution">↵
[tutorial:2209B]↵
</spoiler>↵
↵
<spoiler summary="Code (Python)">↵
~~~~~↵
for _ in range(int(input())):↵
n = int(input())↵
a = list(map(int, input().split()))↵
print(*[max(sum(a[j] < a[i] for j in range(i + 1, n)), sum(a[j] > a[i] for j in range(i + 1, n))) for i in range(n)])↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Code (C++) ">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
int n,a[5009],bcnt,f1[5009],f2[5009];↵
int main(){↵
int t;↵
scanf("%d",&t);↵
while(t--){↵
scanf("%d",&n);↵
for(int i = 1; i <= n; i ++){↵
scanf("%d",&a[i]);↵
}↵
for(int i = n; i >= 1; i --){↵
f1[i] = f2[i] = 0;↵
for(int j = i + 1; j <= n; j ++)↵
f1[i] += (a[i] > a[j]),f2[i] += (a[i] < a[j]);↵
f1[i] = max(f1[i],f2[i]);↵
}↵
for(int i = 1; i < n; i ++)↵
printf("%d ",f1[i]);↵
printf("%d\n",f1[n]);↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:3,option1] Excellent problem↵
- [likes:3,option2] Good problem↵
- [likes:3,option3] Average problem↵
- [likes:3,option4] Bad problem↵
- [likes:3,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:4,option1] Trivial problem↵
- [likes:4,option2] Easy problem↵
- [likes:4,option3] Average problem↵
- [likes:4,option4] Hard problem↵
- [likes:4,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
[problem:2209C]↵
↵
- Idea: [user:__baozii__,2026-01-29]↵
↵
- Solution: [user:__baozii__,2026-01-29]↵
↵
- Editorial: [user:__baozii__,2026-01-29]↵
↵
<spoiler summary="Solution">↵
[tutorial:2209C]↵
</spoiler>↵
↵
<spoiler summary="Code (Python)">↵
~~~~~↵
for _ in range(int(input())):↵
n = int(input())↵
ans = -1↵
for i in range(1, n):↵
print("?", 2 * i + 1, 2 * i + 2, flush=True)↵
if int(input()):↵
ans = 2 * i + 1 ↵
break↵
else:↵
print("?", 1, 3, flush=True)↵
if int(input()):↵
ans = 1↵
else:↵
print("?", 1, 4, flush=True)↵
if int(input()):↵
ans = 1↵
else:↵
ans = 2↵
print("!", ans, flush=True)↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:5,option1] Excellent problem↵
- [likes:5,option2] Good problem↵
- [likes:5,option3] Average problem↵
- [likes:5,option4] Bad problem↵
- [likes:5,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:6,option1] Trivial problem↵
- [likes:6,option2] Easy problem↵
- [likes:6,option3] Average problem↵
- [likes:6,option4] Hard problem↵
- [likes:6,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
[problem:2209D]↵
↵
- Idea: [user:OtterZ,2026-03-21]↵
↵
- Solution: [user:OtterZ,2026-03-21]↵
↵
- Editorial: [user:OtterZ,2026-03-21]↵
↵
<spoiler summary="Solution">↵
[tutorial:2209D]↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
int t,r,g,b,rb,gb,rg;↵
int main(){↵
scanf("%d",&t);↵
while(t--){↵
scanf("%d %d %d",&r,&g,&b);↵
while(((r > 0) + (g > 0) + (b > 0)) >> 1){↵
if(r <= g && r <= b)↵
gb ++,g --,b --;↵
else if(g <= r && g <= b)↵
rb ++,r --,b --;↵
else if(b <= r && b <= g)↵
rg ++,r --,g --;↵
}↵
if(g > 0){↵
putchar('G');↵
while(rg > 0)↵
putchar('R'),putchar('G'),rg --;↵
bool flg = false;↵
while(gb > 0)↵
putchar('B'),putchar('G'),gb --,flg = true;↵
if(flg){↵
while(rb > 0)↵
putchar('B'),putchar('R'),rb --;↵
}↵
else{↵
while(rb > 0)↵
putchar('R'),putchar('B'),rb --;↵
}↵
}↵
else if(r > 0){↵
putchar('R');↵
while(rg > 0)↵
putchar('G'),putchar('R'),rg --;↵
bool flg = false;↵
while(rb > 0)↵
putchar('B'),putchar('R'),rb --,flg = true;↵
if(flg){↵
while(gb > 0)↵
putchar('B'),putchar('G'),gb --;↵
}↵
else{↵
while(gb > 0)↵
putchar('G'),putchar('B'),gb --;↵
}↵
}↵
else{↵
if(b > 0)↵
putchar('B');↵
while(gb > 0)↵
putchar('G'),putchar('B'),gb --;↵
bool flg = false;↵
while(rb > 0)↵
putchar('R'),putchar('B'),rb --,flg = true;↵
if(flg){↵
while(rg > 0)↵
putchar('R'),putchar('G'),rg --;↵
}↵
else{↵
while(rg > 0)↵
putchar('G'),putchar('R'),rg --;↵
}↵
}↵
puts("");↵
}↵
} ↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:7,option1] Excellent problem↵
- [likes:7,option2] Good problem↵
- [likes:7,option3] Average problem↵
- [likes:7,option4] Bad problem↵
- [likes:7,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:8,option1] Trivial problem↵
- [likes:8,option2] Easy problem↵
- [likes:8,option3] Average problem↵
- [likes:8,option4] Hard problem↵
- [likes:8,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
[problem:2209E]↵
↵
- Idea: [user:__baozii__,2026-01-29]↵
↵
- Solution: [user:__baozii__,2026-01-29]↵
↵
- Editorial: [user:__baozii__,2026-01-29]↵
↵
<spoiler summary="Solution">↵
[tutorial:2209E]↵
</spoiler>↵
↵
<spoiler summary="Code (Python)">↵
~~~~~↵
import sys↵
input = lambda: sys.stdin.readline().strip()↵
def work(s):↵
n = len(s)↵
p = [0] * n↵
b = [0] * n↵
for i in range(1, n):↵
j = p[i - 1]↵
while j and s[i] != s[j]:↵
j = p[j - 1]↵
if s[i] == s[j]:↵
j += 1↵
p[i] = j↵
if j == 0:↵
b[i] = 0↵
elif p[j - 1] == 0:↵
b[i] = j↵
else:↵
b[i] = b[j - 1]↵
ans = 0↵
for i in range(n):↵
p[i] = 0↵
p[i] = p[i - b[i]] + 1↵
ans += p[i]↵
return ans↵
↵
for _ in range(int(input())):↵
n, q = map(int, input().split())↵
s = input()↵
for _ in range(q):↵
l, r = map(int, input().split())↵
print(work(s[l - 1:r]))↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:9,option1] Excellent problem↵
- [likes:9,option2] Good problem↵
- [likes:9,option3] Average problem↵
- [likes:9,option4] Bad problem↵
- [likes:9,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:10,option1] Trivial problem↵
- [likes:10,option2] Easy problem↵
- [likes:10,option3] Average problem↵
- [likes:10,option4] Hard problem↵
- [likes:10,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
[problem:2209F]↵
↵
- Idea: [user:OtterZ,2026-03-21]↵
↵
- Solution: [user:OtterZ,2026-03-21]↵
↵
- Editorial: [user:OtterZ,2026-03-21]↵
↵
<spoiler summary="Solution">↵
[tutorial:2209F]↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
const int N = 300009;↵
int n,k,t,a[N],tt[N];↵
long long b[N],ans[N],sum,mxa;↵
struct FLONG{↵
long long val;↵
int nd;↵
FLONG(long long v = 0,int d = 0):↵
val(v),nd(d)↵
{}↵
bool operator<(const FLONG &b)const{↵
return val > b.val || (val == b.val && nd < b.nd);↵
}↵
};↵
set<FLONG>s;↵
set<FLONG> :: iterator o;↵
struct pir{↵
int to,len;↵
pir(int t = 0,int l = 0):↵
to(t),len(l)↵
{}↵
bool operator<(const pir &b)const{↵
return len > b.len || (len == b.len && to < b.to);↵
}↵
}mn[N],se[N],lf[N];↵
vector<int>e[N];↵
void srh(int v,int fa){↵
mn[v] = pir(v,0);↵
se[v] = pir(0,~0x3f3f3f3f);↵
lf[v] = pir(0,~0x3f3f3f3f);↵
for(unsigned i = 0; i < e[v].size(); i ++){↵
if(e[v][i] != fa){↵
srh(e[v][i],v);↵
pir th = mn[e[v][i]];↵
th.len ++;↵
if(th < se[v])↵
swap(th,se[v]);↵
if(se[v] < mn[v])↵
swap(se[v],mn[v]);↵
}↵
}↵
}↵
void gt1(){↵
sum = ans[1] = 0;↵
ans[1] += a[1];↵
for(int i = 2; i <= n; i ++){↵
b[mn[i].to] += a[i];↵
tt[i] = mn[i].to;↵
//printf("%d %d\n",i,tt[i]);↵
}↵
s.clear();↵
for(int i = 2; i <= n; i ++){↵
s.insert(FLONG(b[i],i));↵
}↵
o = s.begin();↵
ans[1] += o -> val;↵
sum += o -> val;↵
for(int i = 1; i < k - 1; i ++){↵
o ++;↵
ans[1] += o -> val;↵
sum += o -> val;↵
}↵
s.insert(FLONG(-1ll,0));↵
s.insert(FLONG(-2ll,0));↵
}↵
void era(int x){↵
FLONG u = FLONG(b[x],x);↵
if(!(*o < u)){↵
o ++;↵
sum += o -> val;↵
sum -= b[x];↵
}↵
s.erase(u);↵
//printf("%d %lld\n",x,sum);↵
}↵
void ins(int x){↵
FLONG u = FLONG(b[x],x);↵
s.insert(u);↵
if(!(*o < u)){↵
sum -= o -> val;↵
sum += b[x];↵
o --;↵
}↵
//printf("%d %lld\n",x,sum);↵
}↵
void stp(int x){↵
era(tt[x]);↵
b[tt[x]] -= a[x];↵
ins(tt[x]);↵
tt[x] = 0; ↵
}↵
void sett(int x,int ttp){↵
tt[x] = ttp;↵
era(tt[x]);↵
b[tt[x]] += a[x];↵
ins(tt[x]);↵
}↵
void srho(int v,int fa){↵
//printf(" %d %d\n",v,fa);↵
if(fa != 0){↵
stp(v);↵
era(v);↵
ins(fa);↵
sett(fa,lf[fa].to);↵
ans[v] = sum + a[v];↵
}↵
for(unsigned i = 0; i < e[v].size(); i ++){↵
if(e[v][i] != fa){↵
pir u = lf[fa];↵
u.len ++;↵
if(mn[v].to == mn[e[v][i]].to)↵
lf[v] = min(u,se[v]);↵
else↵
lf[v] = min(u,mn[v]);↵
srho(e[v][i],v);↵
}↵
}↵
if(fa != 0){↵
ins(v);↵
sett(v,mn[v].to);↵
stp(fa);↵
era(fa);↵
}↵
}↵
int main(){↵
scanf("%d",&t);↵
while(t--){↵
scanf("%d %d",&n,&k);↵
mxa = 0;↵
for(int i = 1; i <= n; i ++){↵
scanf("%d",&a[i]);↵
mxa = max(mxa,1ll * a[i]);↵
e[i].clear();↵
b[i] = 0;↵
}↵
for(int i = 1; i < n; i ++){↵
int u,v;↵
scanf("%d %d",&u,&v);↵
e[u].emplace_back(v);↵
e[v].emplace_back(u);↵
}↵
if(k == 1){↵
printf("%lld\n",mxa);↵
continue;↵
}↵
lf[0].len = ~0x3f3f3f3f;↵
srh(1,0);↵
gt1();↵
srho(1,0);↵
for(int i = 1; i <= n; i ++){↵
mxa = max(mxa,ans[i]);↵
//printf("%lld\n",ans[i]);↵
}↵
printf("%lld\n",mxa);↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:11,option1] Excellent problem↵
- [likes:11,option2] Good problem↵
- [likes:11,option3] Average problem↵
- [likes:11,option4] Bad problem↵
- [likes:11,option5] Horrible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:12,option1] Trivial problem↵
- [likes:12,option2] Easy problem↵
- [likes:12,option3] Average problem↵
- [likes:12,option4] Hard problem↵
- [likes:12,option5] Impossible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
