In Year 2023, 74 had coordinated $$$10$$$ rounds in total. Here's something about them:

• Good Bye 2023. This round. I don't want to say anything more. Votes of the announcement: $$$-3405$$$. (up to 2023/12/31)

• Codeforces Round 908 (Div. 1, Div. 2). No fatal problems occurred in the round, but it feels like Div1A=B=C=D for me :( And actually the performance people who solved problems range from CM to GM, so I would say that this round is of low discrimination. Votes of the announcement: $$$+175$$$.

• Codeforces Round 907 (Div. 2). Also, no fatal problems occurred in the round, but problem F is way too simple. Difficulty disorder usually happens in 74 rounds. Votes of the announcement: $$$+232$$$.

• CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!). Good contest imo, I enjoyed E very much. Qualities of the problems are above average. Votes of the announcement: $$$+394$$$.

• Codeforces Round 880 (Div. 1; Div. 2). I didn't participate in this round, and a *2500 occurred for position Div1B/Div2D. Yet another difficulty disorder. Votes of the announcement: $$$-1467$$$.

• Codeforces Round #873 (Div. 1 & 2). I didn't participate in this round, and it seems a good round. I saw problem Div1B/Div2D before the contest (guess why) and found it really cool. Votes of the announcement: $$$+439$$$.

• CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!). Great round! I enjoyed the problemset very much. Kudos to the authors! Votes of the announcement: $$$+687$$$.

• Nebius Welcome Round (Div. 1 + Div. 2, rated, t-shirts!). Good round. And a fact is that this round is coordinated by both 74 and KAN. Votes of the announcement: $$$+720$$$.

• TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!). A just-so-so round. Problem E<C imo. According to feecle6418, this round also has a known problem, but fortunately it caused little influence. Votes of the announcement: $$$+209$$$.

• Codeforces Round #846 (Div. 2). The NP-hard round. I'm really curious that why none of the authors and testers, and of course, the coordinator, did not find the error in the intended solution. Votes of the announcement: $$$-628$$$.

Out of these $$$10$$$ rounds, $$$4$$$ rounds are generally considered as good rounds, $$$3$$$ rounds have negative votes in announcement, $$$2$$$ rounds have serious problem disorder, and the average votes of these rounds is $$$-264.4$$$. In 2023, there are $$$6$$$ rounds getting negative votes in all (I didn't count educational rounds.), and 74 rounds take up half of them. Some authors said that 74 is the kind of coordinator who goes his own way. All in all, 74 should do improve his ability before coordinating rounds any more.

Indeed at most $$$\bf 4$$$ operations will be used.

If $$$r-l+1$$$ is even, and you do the operation on $$$[l,r]$$$ twice, then the subarray $$$a[l;r]$$$ will all become $$$0$$$.

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int _N = 1e5 + 5;

int T;

void solve() {
	int n; cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	if (n & 1) {
		cout << "4" << '\n';
		cout << "1 " << n - 1 << '\n';
		cout << "1 " << n - 1 << '\n';
		cout << n - 1 << ' ' << n << '\n';
		cout << n - 1 << ' ' << n << '\n';
	} else {
		cout << "2" << '\n';
		cout << "1 " << n << '\n';
		cout << "1 " << n << '\n';
	}
	return;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--) {
		solve();
	}
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

What will happen if there are no major cities?

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int _N = 1e5 + 5;

int T;

void solve() {
	int n, k, s, t; cin >> n >> k >> s >> t;
	vector<int> x(n + 1), y(n + 1);
	for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
	ll ans = llabs(x[s] - x[t]) + llabs(y[s] - y[t]);
	ll mins = LLONG_MAX / 2, mint = LLONG_MAX / 2;
	for (int i = 1; i <= k; i++) {
		mins = min(mins, llabs(x[s] - x[i]) + llabs(y[s] - y[i]));
		mint = min(mint, llabs(x[t] - x[i]) + llabs(y[t] - y[i]));
	}
	ans = min(ans, mins + mint);
	cout << ans << '\n';
	return;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--) {
		solve();
	}
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

What is the upper bound of $$$s$$$ according to $$$n$$$ and $$$m$$$? Can you construct such a matrix that reaches the upper bound?

If not, can you construct a matrix which maximizes $$$\sum_{i=1}^m v_i$$$? This is of some help to get the solution.

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int _N = 1e5 + 5;

int T;

void solve() {
	int n, m;
	cin >> n >> m;
	if (m == 1) cout << 0 << '\n';
	else if (n > m - 1) cout << m << '\n';
	else cout << n + 1 << '\n';
	for (int i = 0; i < min(m - 1, n); i++) {
		for (int j = 0; j < m; j++) {
			cout << (j + i) % m << ' ';
		}
		cout << '\n';
	}
	if (n > m - 1) {
		for (int i = m - 1; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cout << j << ' ';
			}
			cout << '\n';
		}
	}
	return;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--) {
		solve();
	}
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

You can calculate the number of candies of each person after the swap easily. Denote the number as $$$s$$$.

Since a person gives candies to and receives candies from exactly one person, assume he gives away $$$2^x$$$ candies and receives $$$2^y$$$ candies, then we have $$$a_i - 2^x + 2^y = s$$$. If $$$a_i \ne s$$$, at most how many pairs $$$(x,y)$$$ can satisfy this equation?

Do the two restrictions in the statement,

Note that one cannot give more candies than currently he has (he might receive candies from someone else before) and he cannot give candies to himself, either.

really make any difference to the answer?

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int _N = 1e5 + 5;

int T;

void solve() {
	int n; cin >> n;
	vector<ll> a(n); ll sum = 0;
	for (int i = 0; i < n; i++) cin >> a[i], sum += a[i];
	if (sum % n) return cout << "No" << '\n', void();
	sum /= n;
	vector<int> bit(31, 0);
	auto lowbit = [](int x) {
	    return x & (-x);
	};
	for (int i = 0; i < n; i++) {
		if (a[i] == sum) continue;
		int d = abs(a[i] - sum);
		int p = lowbit(d);
		int e = d + p;
		if (__builtin_popcount(e) == 1) {
		    if (a[i] > sum) bit[__lg(e)]++, bit[__lg(p)]--;
		    else bit[__lg(e)]--, bit[__lg(p)]++;
		} else {
		    cout << "No" << '\n';
		    return;
		}
	}
	for (int i = 0; i < 31; i++) {
		if (bit[i]) {
			cout << "No" << '\n';
			return;
		}
	}
	cout << "Yes" << '\n';
	return;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--) {
		solve();
	}
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

For whom may not give or receive candies?

When $$$|a_i-s|$$$ is a power of $$$2$$$, how many ways can the person gives/receives candies at most?

Try to determine some people's way to give/receive candies first, then others.

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int _N = 1e5 + 5;

int T;

void solve() {
	int n; cin >> n;
	vector<ll> a(n); ll sum = 0;
	for (int i = 0; i < n; i++) cin >> a[i], sum += a[i];
	if (sum % n) return cout << "No" << '\n', void();
	sum /= n;
	vector<int> bit(31, 0), pow1(31, 0), pow2(31, 0);
	for (int i = 0; i < n; i++) {
		int flag = 0;
		if (a[i] == sum) continue;
		for (int j = 0; j < 31; j++) {
			if (a[i] + (1 << j) == sum) {
				pow1[j]++;
				flag = 1;
				continue;
			}
			if (a[i] - (1 << j) == sum) {
				pow2[j]++;
				flag = 1;
				continue;
			}
		}
		if (flag) continue;
		flag = 0;
		for (int j = 0; j < 31; j++) {
			for (int k = 0; k < 31; k++) {
			    if (a[i] + (1 << j) - (1 << k) == sum) {
			        flag = 1;
			        bit[j]++;
			        bit[k]--;
			    }
			}
		}
		if (!flag) {
			cout << "No" << '\n';
			return;
		}
	}
	for (int i = 30; i >= 0; i--) {
		bit[i] += (pow1[i] - pow2[i]);
		if (i == 0) break;
		if (bit[i] < 0) {
			pow1[i - 1] -= -bit[i];
			bit[i - 1] -= -bit[i];
			if (pow1[i - 1] < 0) {
				cout << "No" << '\n';
				return;
			}
		} else {
			pow2[i - 1] -= bit[i];
			bit[i - 1] += bit[i];
			if (pow2[i - 1] < 0) {
				cout << "No" << '\n';
				return;
			}
		}
	}
	if (bit[0] == 0) cout << "Yes" << '\n';
	else cout << "No" << '\n';
	return;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--) {
		solve();
	}
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

For any simple path length $$$t$$$, what's the sum of the maximum value of cities in all assignments? For the cities out of the path, their value doesn't matter.

Consider an easy dp to calculate the number of paths with different lengths.

How many different subtrees are there in this tree?

What's the maximum length of the paths?

Try to optimize the dp with the conclusion you get in Hint 3 and Hint 4.

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
#pragma GCC optimize("Ofast")

ll tot[505],n,m,dp[125][125],dp2[125],g[125][125],g2[125],f[125],pw[100005][125];
const ll mod=998244353;

inline ll dep( ll root) {
	if (root>n)return 0;
	return dep(root*2)+1;
}

inline ll dep2( ll root) {
	if (root>n)return 0;
	return dep2(root*2+1)+1;
}

inline bool full( ll root) {
	return dep(root)==dep2(root);
}

void dfs( ll root) {
	if (root*2>n) {
		g2[0]=dp2[0]=1;
		return;
	}
	if (root*2==n) {
		g2[0]=2,g2[1]=1;
		dp2[0]=1,dp2[1]=1;
		return;
	}
	ll d=0;
	if (full(root*2)) {

		d=dep(root*2);
		dfs(root*2+1);
	} else {
		d=dep(root*2+1);
		dfs(root*2);
	}
	ll mx=2*d+4;
	for (ll i=0; i<=mx; i++) {
		g2[i]+=g[d][i];
		for (ll j=0; j<=min(d+2,i); j++) {
			g2[i+2]+=dp2[j]*dp[d][i-j]%mod;
		}
	}
	for (ll i=mx; i>0; i--)dp2[i]=(dp2[i-1]+dp[d][i-1])%mod;
	dp2[0]=1;
	for (ll i=0; i<=mx; i++)g2[i]+=dp2[i],g2[i]%=mod;
}

inline ll qkp(ll a,ll k) {
	ll ans=1;
	while (k) {
		if (k&1)ans*=a,ans%=mod;
		a*=a,a%=mod;
		k>>=1;
	}
	return ans;
}

int main() {
	ll t;
	scanf("%lld",&t);
	for (ll i=1; i<=60; i++) {
			dp[i][0]=1;
			for (ll j=1; j<=i-1; j++) {
				dp[i][j]=2*dp[i-1][j-1]%mod;
			}
			for (ll j=0; j<=2*i-2; j++) {
				g[i][j]+=g[i-1][j]*2;
				g[i][j]+=dp[i][j];
				g[i][j]%=mod;
				for (ll k=0; k<=j; k++) {
					g[i][j+2]+=dp[i-1][k]*dp[i-1][j-k]%mod;
					g[i][j+2]%=mod;
				}
			}
		}
	while (t--) {
		scanf("%lld%lld",&n,&m);
		
		// log n^3
		dfs(1);
		ll d=dep(1),ans=0;
		for (ll j=0; j<=m; j++) {
			pw[j][0]=1;
			for (ll i=1; i<=2*d; i++) {
				pw[j][i]=pw[j][i-1]*j%mod;
			}
		}

		for (ll i=0; i<=2*d-2; i++) {
			for (ll j=1; j<=m; j++) {
				f[i]+=(pw[j][i+2]+mod-pw[j-1][i+1]*j%mod)%mod;
				f[i]%=mod;
			}
			if (n>=i+1)
				ans+=f[i]*g2[i]%mod*qkp(m,n-i-1)%mod;
			ans%=mod;
		}
		printf("%lld\n",ans);
		for (ll i=1;i<=60;i++){
			for (ll j=0;j<=2*i-2;j++){
				f[j]=g2[j]=dp2[j]=0;
			}
		}
	}

	return 0;
}

#include <bits/stdc++.h>
#define int long long
#define double long double
#define mid ((l+r)>>1)
using namespace std;
const int mod=998244353;
int qp(int a,int b){
	int ans=1;
	while(b){
		if(b&1) ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}
int fac[1000005],inv[1000005];
void init(){
	fac[0]=1;
	for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
	inv[1000000]=qp(fac[1000000],mod-2);
	for(int i=999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int i,int j){
	if(i<0||j<0||i<j) return 0;
	return fac[i]*inv[i-j]%mod*inv[j]%mod;
}
int cnt=0;
int reg[100005][131],reg2[100005][131];
unordered_map<int,int> mp;
void dfs(int now){
	if(mp[now]) return ;
	mp[now]=++cnt;
	if(now==0) return ;
	reg[cnt][0]++,reg2[cnt][0]++;
	if(now==1) return ;
	int i=0;
	for(i=1;i<=62;i++) if((1LL<<i)-1>=now) break;
	i-=2;
	int lnum=(1LL<<i)-1,rnum=(1LL<<i)-1,lft=now-(1LL<<(i+1))+1;
	if(lft<=(1LL<<i)) lnum+=lft;
	else lnum+=(1LL<<i),rnum+=(lft-(1LL<<i));
	dfs(lnum),dfs(rnum);
	int ml=mp[lnum],mr=mp[rnum],mn=mp[now];
	for(int i=0;i<=130;i++){
		for(int j=0;j<=130;j++){
			if(i+j+2>=130) break;
			(reg2[mn][i+j+2]+=(reg[ml][i]*reg[mr][j]))%=mod; 
		}
	}
	for(int i=0;i<=129;i++) (reg[mn][i+1]+=reg[ml][i]+reg[mr][i])%=mod,(reg2[mn][i+1]+=reg[ml][i]+reg[mr][i])%=mod,(reg2[mn][i]+=reg2[ml][i]+reg2[mr][i])%=mod;
}
int pw[100005][150],tot[205];
signed main(){
	init();
	int t; cin>>t;
	while(t--){
		int n,m;
		cin>>n>>m;
		dfs(n);
		int nn=mp[n];
		int ans=0;
		tot[0]=(m-1)%mod;
		for(int i=2;i<=135;i++){
			tot[i-1]=(qp((m-1)%mod+1,i)+mod-1)%mod;
			for(int l=2;l<=i;l++) (tot[i-1]+=mod-C(i,l)*tot[i-l]%mod)%=mod;
		    (tot[i-1]*=qp(i,mod-2))%=mod;
		}
		for(int i=0;i<=min(130ll,n-1);i++){
			int tmp=(qp(m%mod,i+2)+mod-tot[i+1])%mod;
			(ans+=tmp*reg2[nn][i]%mod*qp(m%mod,n-(i+1)))%=mod;
		}
		cout<<ans<<"\n";
	}
	return 0;
}

#include <bits/stdc++.h>
#define int long long
#define double long double
#define mid ((l+r)>>1)
using namespace std;
const int mod=998244353;
int qp(int a,int b){
	int ans=1;
	while(b){
		if(b&1) ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}
int fac[1000005],inv[1000005];
void init(){
	fac[0]=1;
	for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
	inv[1000000]=qp(fac[1000000],mod-2);
	for(int i=999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int i,int j){
	if(i<0||j<0||i<j) return 0;
	return fac[i]*inv[i-j]%mod*inv[j]%mod;
}
int cnt=0;
int reg[100005][131],dep[100005],depc[100005],rett[131],invi[131];
unordered_map<int,int> mp;
void dfs(int now){
	if(mp[now]) return ;
	mp[now]=++cnt;
	if(now==0) return ;
	dep[cnt]=1,depc[cnt]=1,reg[cnt][0]++;
	if(now==1) return ;
	int i=0;
	for(i=1;i<=62;i++) if((1LL<<i)-1>=now) break;
	i-=2;
	int lnum=(1LL<<i)-1,rnum=(1LL<<i)-1,lft=now-(1LL<<(i+1))+1;
	if(lft<=(1LL<<i)) lnum+=lft;
	else lnum+=(1LL<<i),rnum+=(lft-(1LL<<i));
	dfs(lnum),dfs(rnum);
	int ml=mp[lnum],mr=mp[rnum],mn=mp[now];
	if(dep[ml]>dep[mr]){
		dep[mn]=dep[ml]+1; depc[mn]=depc[ml];
		for(int i=0;i<=129;i++) reg[mn][i]=reg[ml][i];
	}
	else{
		dep[mn]=dep[ml]+1; depc[mn]=(depc[ml]+depc[mr])%mod;
		for(int i=0;i<=129;i++) reg[mn][i]=(reg[ml][i]+reg[mr][i])%mod;
		(reg[mn][dep[mn]*2-2]+=depc[ml]*depc[mr])%=mod;
	}
}
int pw[100005][150],tot[205],pw2[135];
signed main(){
	pw2[0]=1;
	for(int i=1;i<=130;i++) pw2[i]=pw2[i-1]*2%mod,invi[i]=qp(i,mod-2);
	init();
	int t; cin>>t;
	while(t--){
		int n,m;
		cin>>n>>m;
		int lg=0,lft;
		for(int i=0;i<=130;i++) rett[i]=0;
		for(lg=61;lg>=0;lg--){
			if(n>=(1LL<<(lg+1))-1){
				lft=n-((1LL<<(lg+1))-1);
				lft%=mod;
				break;
			}
		}
		for(int i=0;i<=lg;i++){
			for(int j=0;j<=lg;j++){
				int tt=max(i,j);
				(rett[i+j]+=(pw2[lg-tt+1]-1)*pw2[max(0ll,i-1)+max(0ll,j-1)]%mod)%=mod;
			}
		}
		for(int i=1;i<=lg+1;i++){
			for(int j=0;j<i;j++){
				(rett[i+j]+=lft*pw2[max(0ll,j-1)]%mod)%=mod;
			}
		}
		dfs(n);
		int nn=mp[n];
		if(n!=(1ll<<(lg+1))-1) for(int i=0;i<=130;i++) (rett[i]+=reg[nn][i])%=mod;
		int ans=0;
		tot[0]=(m-1)%mod;
		for(int i=2;i<=130;i++){
			tot[i-1]=(qp((m-1)%mod+1,i)+mod-1)%mod;
			for(int l=2;l<=i;l++) (tot[i-1]+=mod-C(i,l)*tot[i-l]%mod)%=mod;
		    (tot[i-1]*=invi[i])%=mod;
		}
		for(int i=0;i<=min(130ll,n-1);i++){
			int tmp=(qp(m%mod,i+2)+mod-tot[i+1])%mod;
			(ans+=tmp*rett[i]%mod*qp(m%mod,n-(i+1)))%=mod;
		}
		cout<<ans<<"\n";
	}
	return 0;
}

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0,_##i##__end=(n);i<_##i##__end;++i)
#define rep1(i,n) for(int i=1,_##i##__end=(n);i<=_##i##__end;++i)
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
using namespace std;
const ll mod1=998244353;
int t;
ll n;
int m;
ll qkpw(ll a,ll b)
{
	ll ret=1;
	while(b)
	{
		if(b&1) ret=ret*a%mod1;
		a=a*a%mod1;
		b>>=1;
	}
	return ret;
}
ll val_full[114];
ll val_link[114];
pair<ll,ll> realget(ll P,unsigned long long c)
{
	if((c&(c+1))==0)
	return mp(val_link[bit_width(c)-1],val_full[bit_width(c)-1]);
	if(c==2)
	return mp((P*P+P)%mod1,(P*P+P+P)%mod1);
	if(c&(bit_floor(c)>>1))
	{
		pair<ll,ll> A=realget(P,bit_floor(c)-1),B=realget(P,c-bit_floor(c));
		return mp((A.fi+B.fi+1)*P%mod1,(A.se+B.se+(1+A.fi)*(1+B.fi)%mod1*P)%mod1);
	}
	pair<ll,ll> A=realget(P,c-(bit_floor(c)>>1)),B=realget(P,(bit_floor(c)>>1)-1);
	return mp((A.fi+B.fi+1)*P%mod1,(A.se+B.se+(1+A.fi)*(1+B.fi)%mod1*P)%mod1);
}
ll get_value(ll P,ll c)
{
	val_full[0]=P;val_link[0]=P;
	rep1(i,64)
	{
		val_full[i]=(val_full[i-1]*2+(1+val_link[i-1])*(1+val_link[i-1])%mod1*P)%mod1;
		val_link[i]=((val_link[i-1]*2+1)*P)%mod1;
	}
	return realget(P,c).second;
}
void Q()
{
	cin>>n>>m;
	ll cur=((n%mod1)*(n%mod1+1)/2%mod1)*qkpw(m,n+1)%mod1;
	ll INV_M=qkpw(m,mod1-2);
	rep(i,m) cur=(cur-qkpw(m,n)*get_value(i*INV_M%mod1,n)%mod1+mod1)%mod1;
	cout<<cur<<endl;
}
int main()
{
	cin>>t;while(t--)Q();
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

In fact, vertices with degree $$$1$$$ are useless, let's first ignore them. It's easy to see that when $$$\sum_{i=1}^nd_i=2n$$$, we can simply hang them under the vertices which haven't reached their degree limit.

In most cases, we can simply put two vertices on the cycle.

Sort $$$d_i$$$ from the largest to the smallest. Can we construct a flower-like psuedotree when $$$d_1=2$$$? Can we construct a flower-like psuedotree when $$$d_1\neq 2$$$ and $$$d_2=2$$$?

Can you find an easy way to construct the flower-like psuedotree when the number of $$$d_i>1$$$ is even?

Try to extend the solution when the number of $$$d_i>1$$$ is even to the odd case. Note some corner cases.

#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
struct node{
	int d,pos;
}a[1000005];
bool cmp(node x,node y){
	return x.d>y.d;
}
void pe(int x,int y){
	cout<<a[x].pos<<" "<<a[y].pos<<"\n";
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t; cin>>t;
	while(t--){
		int n,tot=0; cin>>n; for(int i=1;i<=n;i++) cin>>a[i].d,a[i].pos=i,tot+=a[i].d;
		if(tot!=2*n){
			cout<<"No\n"; continue;
		}
		if(n==1){
			cout<<"No\n"; continue;
		}
		sort(a+1,a+n+1,cmp);
		if(a[1].d==2){
			cout<<"Yes\n";
			for(int i=1;i<=n;i++) pe(i,i%n+1);
			continue;
		}
		if(a[2].d==2){
			cout<<"No\n"; continue;
		}
		int cntb=0;
		for(int i=3;i<=n;i++) cntb+=(a[i].d>1);
		int num[n+1]; for(int i=1;i<=n;i++) num[i]=a[i].d;
		if(!(cntb&1)){
			cout<<"Yes\n";
			pe(1,2),pe(1,2);
			num[1]-=2,num[2]-=2;
			for(int i=3;i<=cntb+2;i++) pe(i,i-2),num[i]--,num[i-2]--;
			int it=1;
			for(int i=cntb+3;i<=n;i++){
				while(!num[it]) it++;
				num[it]--,pe(i,it);
			}
			continue;
		}
		if(a[1].d==3){
			if(a[3].d==2){
				cout<<"No\n"; continue;
			}
			if(cntb==1){
				cout<<"Yes\n";
				pe(1,2),pe(2,3),pe(3,1);
				pe(1,4),pe(2,5),pe(3,6);
				continue;
			}
			if(a[5].d==2&&cntb==3){
				cout<<"No\n"; continue;
			}
			if(cntb==3){
				cout<<"Yes\n";
				pe(1,2),pe(2,3),pe(3,4),pe(4,5),pe(5,1);
				pe(1,6),pe(2,7),pe(3,8),pe(4,9),pe(5,10);
				continue;
			}
			cout<<"Yes\n";
			pe(1,2),pe(1,2),pe(1,3),pe(2,4),pe(3,5),pe(3,6),pe(4,7);
			num[1]-=3,num[2]-=3,num[3]-=3,num[4]-=2,num[5]--,num[6]--,num[7]--;
			for(int i=8;i<=cntb+2;i++) pe(i-2,i),num[i]--,num[i-2]--;
			int it=1;
			for(int i=cntb+3;i<=n;i++){
				while(!num[it]) it++;
				num[it]--,pe(i,it);
			}
			continue;
		}
		else{
			if(a[3].d==2&&cntb==1){
				cout<<"No\n"; continue;
			}
			if(cntb==1){
				cout<<"Yes\n";
				pe(1,2),pe(2,3),pe(3,1);
				num[1]-=2,num[2]-=2,num[3]-=2;
				int it=1;
				for(int i=4;i<=n;i++){
					while(!num[it]) it++;
					num[it]--,pe(i,it);
				}
				continue;
			}
			cout<<"Yes\n";
			pe(1,2),pe(1,2),pe(1,3),pe(1,4),pe(2,5);
			num[1]-=4,num[2]-=3,num[3]-=1,num[4]-=1,num[5]-=1;
			for(int i=6;i<=cntb+2;i++) pe(i,i-2),num[i]--,num[i-2]--;
			int it=1;
			for(int i=cntb+3;i<=n;i++){
				while(!num[it]) it++;
				num[it]--,pe(i,it);
			}
			continue;
		}
	}
	return 0;
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

Consider this problem on the prefix sum array.

Try to make some observations about the prefix sum array. Consider dp.

Go for a slow solution first, for example, $$$\mathcal{O}(n^6)$$$ or $$$\mathcal{O}(n^4)$$$.

The last step is to optimize your dp to $$$\mathcal{O}(n^3)$$$. :)

$$$\mathcal{O}(n^6)$$$ can pass $$$n\le 100$$$ easily so we have to raise the limit for $$$\sum n$$$ to $$$1~000$$$.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <random>
#include <ctime>
#include <string_view>
#include <queue>
#include <cassert>

using namespace std;

#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define pb emplace_back
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define ld long double

const int INF = 1e9 + 1;
const ll INFLL = 1e18;

bool contains(ll x, ll l, ll r) {
    return (x >= l) && (x <= r);
}

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (n == 1) {
        cout << 1 << "\n";
        return;
    }
    vector<ll> pr(n + 1);
    for (int i = 0; i < n; i++) pr[i + 1] = pr[i] + a[i + 1];
    vector<vector<vector<int>>> dp_leftmin(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -INF)));
    vector<vector<vector<int>>> dp_leftmax(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -INF)));
    vector<vector<vector<int>>> dp_rightmin(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -INF)));
    vector<vector<vector<int>>> dp_rightmax(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -INF)));
    vector<pair<ll, int>> b(n + 1);
    for (int i = 0; i <= n; i++) b[i] = mp(pr[i], i);
    sort(all(b));
    vector<vector<int>> next_left(n + 1, vector<int>(n + 1, -1));
    vector<vector<int>> next_right(n + 1, vector<int>(n + 1, -1));
    for (int i = 0; i <= n; i++) {
        int prev = -1;
        for (int j = 0; j <= n; j++) {
            next_left[i][j] = prev;
            if (pr[j] == pr[i]) prev = j;
        }
        prev = n + 1;
        for (int j = n; j >= 0; j--) {
            next_right[i][j] = prev;
            if (pr[j] == pr[i]) prev = j;
        }
    }
    for (int len = 0; len <= n; len++) {
        for (int i = 0; i <= n && i + len <= n; i++) {
            int j = i + len;
            for (int k = 0; k <= n; k++) {
                if (contains(pr[i], pr[i], pr[k]) && contains(pr[j], pr[i], pr[k])) dp_leftmin[i][j][k] = min(len, 1);
                if (contains(pr[i], pr[k], pr[i]) && contains(pr[j], pr[k], pr[i])) dp_leftmax[i][j][k] = min(len, 1);
                if (contains(pr[i], pr[j], pr[k]) && contains(pr[j], pr[j], pr[k])) dp_rightmin[i][j][k] = min(len, 1);
                if (contains(pr[i], pr[k], pr[j]) && contains(pr[j], pr[k], pr[j])) dp_rightmax[i][j][k] = min(len, 1);
            }
            if (len <= 1) continue;
            for (int x = i; x <= j; x++) {
                if (next_left[i][x] >= i) {
                    int y = next_left[i][x];
                    if (pr[x] >= pr[i]) dp_leftmin[i][j][x] = max(dp_leftmin[i][j][x], dp_leftmin[i][y][x] + dp_leftmax[x][j][i] + 1);
                    if (pr[x] <= pr[i]) dp_leftmax[i][j][x] = max(dp_leftmax[i][j][x], dp_leftmax[i][y][x] + dp_leftmin[x][j][i] + 1);
                }
                if (next_left[j][x] >= i) {
                    int y = next_left[j][x];
                    if (pr[x] >= pr[j]) dp_rightmin[i][j][x] = max(dp_rightmin[i][j][x], dp_rightmin[x][j][x] + dp_rightmin[i][y][x] + 1);
                    if (pr[x] <= pr[j]) dp_rightmax[i][j][x] = max(dp_rightmax[i][j][x], dp_rightmax[x][j][x] + dp_rightmax[i][y][x] + 1);
                }
                if (next_right[i][x] <= j) {
                    int y = next_right[i][x];
                    if (pr[x] >= pr[i]) dp_leftmin[i][j][x] = max(dp_leftmin[i][j][x], dp_leftmin[i][x][x] + dp_leftmin[y][j][x] + 1);
                    if (pr[x] <= pr[i]) dp_leftmax[i][j][x] = max(dp_leftmax[i][j][x], dp_leftmax[i][x][x] + dp_leftmax[y][j][x] + 1);
                }
                if (next_right[j][x] <= j) {
                    int y = next_right[j][x];
                    if (pr[x] >= pr[j]) dp_rightmin[i][j][x] = max(dp_rightmin[i][j][x], dp_rightmin[y][j][x] + dp_rightmax[i][x][j] + 1);
                    if (pr[x] <= pr[j]) dp_rightmax[i][j][x] = max(dp_rightmax[i][j][x], dp_rightmax[y][j][x] + dp_rightmin[i][x][j] + 1);
                }
            }
            int mx_left = -INF;
            int mx_right = -INF;
            for (int k = 0; k <= n; k++) {
                int p = k;
                while (p <= n && b[p].fi == b[k].fi) {
                    mx_left = max(mx_left, dp_leftmin[i][j][b[p].se]);
                    mx_right = max(mx_right, dp_rightmin[i][j][b[p].se]);
                    p++;
                }
                for (int l = k; l < p; l++) {
                    dp_leftmin[i][j][b[l].se] = mx_left;
                    dp_rightmin[i][j][b[l].se] = mx_right;
                }
                k = p - 1;
            }
            mx_left = -INF;
            mx_right = -INF;
            for (int k = n; k >= 0; k--) {
                int p = k;
                while (p >= 0 && b[p].fi == b[k].fi) {
                    mx_left = max(mx_left, dp_leftmax[i][j][b[p].se]);
                    mx_right = max(mx_right, dp_rightmax[i][j][b[p].se]);
                    p--;
                }
                for (int l = k; l > p; l--) {
                    dp_leftmax[i][j][b[l].se] = mx_left;
                    dp_rightmax[i][j][b[l].se] = mx_right;
                }
                k = p + 1;
            }
        }
    }
    int ans = -INF;
    ans = max(ans, dp_leftmin[0][n][n]);
    ans = max(ans, dp_leftmax[0][n][n]);
    for (int x = 0; x <= n; x++) {
        for (int y = x + 1; y <= n; y++) {
            ans = max(ans, dp_rightmin[0][x][y] + dp_leftmax[y][n][x] + 1);
            ans = max(ans, dp_rightmax[0][x][y] + dp_leftmin[y][n][x] + 1);
        }
    }
    cout << ans << "\n";
}

int main() {
    #ifdef LOCAL
        freopen("input", "r", stdin);
        freopen("output", "w", stdout);
    #else 
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    #endif
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

Greedy.

This problem is somehow related to geometry.

What structure will the intervals you choose each time form?

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;
using point = pair<ll, ll>;

const int _N = 5e5 + 5;

int n;
ll a[_N], pre[_N], suf[_N], ans;
struct interval{
	int l, r; 
	ll d, dneed;
	int type, pos; // type0 - l, type1 - r
};
struct cmp{
	bool operator () (const interval &a, const interval &b) {
		return a.dneed - a.d > b.dneed - b.d;
	}
};

ll ceildiv(ll a, ll b) {
	// return a/b;
	if (a * b > 0) return a / b;
	else return a / b - !!(a % b);
}

namespace sg_left{ // [l, r] -> hull of point l-1 to r-1
	vector<int> hull[_N << 2];
	point pt[_N];
	void get_hull(int p, int l, int r) {
		int head = 0, tail = -1;
		for (int i = l; i <= r; i++) {
			while (head < tail && (pt[hull[p][tail]].second - pt[hull[p][tail - 1]].second) * (pt[i].first - pt[hull[p][tail]].first) <= (pt[i].second - pt[hull[p][tail]].second) * (pt[hull[p][tail]].first - pt[hull[p][tail - 1]].first)) {
				tail--;
				hull[p].pop_back();
			}
			tail++;
			hull[p].emplace_back(i);
		}
	}
	void build(int p, int l, int r) {
		get_hull(p, l - 1, r - 1);
		if (l == r) return;
		int mid = (l + r) >> 1;
		build(p * 2, l, mid);
		build(p * 2 + 1, mid + 1, r);
	}
	pair<int, int> query(int p, int l, int r, int L, int R, point o) {
		if (l >= L && r <= R) { // do ternary search
			int tl = 1, tr = hull[p].size();
			while (tl < tr) {
				int m1 = (tl + tr) / 2, m2 = (tl + tr) / 2 + 1;
				auto p1 = pt[hull[p][m1 - 1]], p2 = pt[hull[p][m2 - 1]];
				if ((o.second - p1.second) * (o.first - p2.first) >= (o.second - p2.second) * (o.first - p1.first)) {
					tl = m1 + 1;
				} else tr = m2 - 1;
			}
			return {ceildiv((o.second - pt[hull[p][tl - 1]].second), (o.first - pt[hull[p][tl - 1]].first)), hull[p][tl - 1] + 1};
		}
		int mid = (l + r) >> 1;
		pair<int, int> res = {-1, -1};
		if (L <= mid) {
			res = query(p * 2, l, mid, L, R, o);
		} 
		if (R > mid) {
			auto res2 = query(p * 2 + 1, mid + 1, r, L, R, o);
			if (res == make_pair(-1, -1)) return res2;
			else {
				if (res2.first <= res.first) {
					return res2;
				} else return res;
			}
		}
		return res;
	}
	void test() {
		auto res = query(1, 1, n, 1, n, pt[n]);
		cout << res.first << ' ' << res.second << '\n';
	}
};
namespace sg_right{ // [l, r] -> hull of point l+1 to r+1
	vector<int> hull[_N << 2];
	point pt[_N];
	void get_hull(int p, int l, int r) {
		int head = 0, tail = -1;
		for (int i = l; i <= r; i++) {
			while (head < tail && (pt[hull[p][tail]].second - pt[hull[p][tail - 1]].second) * (pt[i].first - pt[hull[p][tail]].first) < (pt[i].second - pt[hull[p][tail]].second) * (pt[hull[p][tail]].first - pt[hull[p][tail - 1]].first)) {
				tail--;
				hull[p].pop_back();
			}
			tail++;
			hull[p].emplace_back(i);
		}
	}
	void build(int p, int l, int r) {
		get_hull(p, l + 1, r + 1);
		if (l == r) return;
		int mid = (l + r) >> 1;
		build(p * 2, l, mid);
		build(p * 2 + 1, mid + 1, r);
	}
	pair<int, int> query(int p, int l, int r, int L, int R, point o) {
		if (l >= L && r <= R) { // do ternary search
			int tl = 1, tr = hull[p].size();
			while (tl < tr) {
				int m1 = (tl + tr) / 2, m2 = (tl + tr) / 2 + 1;
				auto p1 = pt[hull[p][m1 - 1]], p2 = pt[hull[p][m2 - 1]];
				if ((o.second - p1.second) * (o.first - p2.first) <= (o.second - p2.second) * (o.first - p1.first)) {
					tl = m1 + 1;
				} else tr = m2 - 1;
			}
			return {ceildiv(-(o.second - pt[hull[p][tl - 1]].second), (o.first - pt[hull[p][tl - 1]].first)), hull[p][tl - 1] - 1};
		}
		int mid = (l + r) >> 1;
		pair<int, int> res = {-1, -1};
		if (L <= mid) {
			res = query(p * 2, l, mid, L, R, o);
		} 
		if (R > mid) {
			auto res2 = query(p * 2 + 1, mid + 1, r, L, R, o);
			if (res == make_pair(-1, -1)) return res2;
			else {
				if (res.first <= res2.first) {
					return res;
				} else return res2;
			}
		}
		return res;
	}
	void test() {
		auto res = query(1, 1, n, 1, n, pt[1]);
		cout << res.first << ' ' << res.second << '\n';
	}
};


int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	if (n == 1) {
		cout << max(a[1] + 1, 0ll) << '\n';
		return 0;
	}
	sg_left::pt[0] = {0, 0}; sg_right::pt[n + 1] = {n + 1, 0};
	for (int i = 1; i <= n; i++) {
		pre[i] = pre[i - 1] + a[i];
		sg_left::pt[i] = {i, pre[i]};
	}
	for (int i = n; i >= 1; i--) {
		suf[i] = suf[i + 1] + a[i];
		sg_right::pt[i] = {i, suf[i]};
	}
	sg_left::build(1, 1, n);
	sg_right::build(1, 1, n);
	ll ans = 0;
	priority_queue<interval, vector<interval>, cmp> q;
	pair<int, int> resL = sg_left::query(1, 1, n, 1, n, sg_left::pt[n]);
	pair<int, int> resR = sg_right::query(1, 1, n, 1, n, sg_right::pt[1]);
	if (resL.second == 1) q.push({1, n, 0, resR.first + 1, 1, resR.second});
	else if (resR.second == n) q.push({1, n, 0, resL.first + 1, 0, resL.second});
	else if (resL.first <= resR.first) q.push({1, n, 0, resL.first + 1, 0, resL.second});
	else q.push({1, n, 0, resR.first + 1, 1, resR.second});
	while (!q.empty()) {
		auto x = q.top(); q.pop();
		if (x.d < x.dneed) {
			ans += x.dneed - x.d;
			x.d = x.dneed;
		}
		//split
		if (x.type == 1) x.pos++;
		int l = x.l, r = x.r;
		resL = sg_left::query(1, 1, n, l, x.pos - 1, sg_left::pt[x.pos - 1]);
		resR = sg_right::query(1, 1, n, l, x.pos - 1, sg_right::pt[l]);
		if (l == x.pos - 1) {
			ans += max(0ll, a[l] - x.d + 1);
		} else {
			if (resL.second == l) q.push({l, x.pos - 1, x.d, resR.first + 1, 1, resR.second});
			else if (resR.second == r) q.push({l, x.pos - 1, x.d, resL.first + 1, 0, resL.second});
			else if (resL.first <= resR.first) q.push({l, x.pos - 1, x.d, resL.first + 1, 0, resL.second});
			else q.push({l, x.pos - 1, x.d, resR.first + 1, 1, resR.second});
		}
		resL = sg_left::query(1, 1, n, x.pos, r, sg_left::pt[r]);
		resR = sg_right::query(1, 1, n, x.pos, r, sg_right::pt[x.pos]);
		if (x.pos == r) {
			ans += max(0ll, a[r] - x.d + 1);
		} else {
			if (resL.second == l) q.push({x.pos, r, x.d, resR.first + 1, 1, resR.second});
			else if (resR.second == r)q.push({x.pos, r, x.d, resL.first + 1, 0, resL.second});
			else if (resL.first < resR.first) q.push({x.pos, r, x.d, resL.first + 1, 0, resL.second});
			else q.push({x.pos, r, x.d, resR.first + 1, 1, resR.second});
		}
	}
	cout << ans << '\n';
}

Can you solve this problem in $$$\mathcal{O}(n\log n+n\log V)$$$ time complexity and $$$\mathcal{O}(n)$$$ space complexity?

The solution has nothing to do with data structures.

/*  
  hmz is cute!
--------------------------------------------
  You've got to have faith
  Don't let them cut you down cut you down once more
*/
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
using namespace std;
#define TY long long
#define IL inline
#define umap unordered_map
#define ull unsigned long long
#define pq priority_queue
#define mp make_pair
#define pb push_back
#define mod (TY)(1e9+7)
#define MAXN 500005
#define MAXM 200005
#define MAXK 27
#define INF (TY)(1e9)
#define block 300
#define For(i,a,b) for(TY i=(a);i<=(b);++i)
#define FOR(i,a,b) for(TY i=(a);i<(b);++i)
#define Rof(i,a,b) for(TY i=(a);i>=(b);--i)
#define ROF(i,a,b) for(TY i=(a);i>(b);--i)
IL TY qr(){
	TY x=0,f=1;char op=getchar();
	for(;op<'0'||op>'9';op=getchar())if(op=='-')f=-1;
	for(;op>='0'&&op<='9';op=getchar())x=x*10+(op^48);
	return x*f;
}IL bool ischar(char op){
	if(op>='a'&&op<='z')return true;
	if(op>='A'&&op<='Z')return true;
	return false;
}IL char getc(){
	char op=getchar();
	while(!ischar(op))op=getchar();
	return op;
}IL string qs(){
	string op="";char u=getchar();
	while(!ischar(u))u=getchar();
	while(ischar(u))op+=u,u=getchar();
	return op;
}IL void qw(long long x){
	if(!x){putchar('0');return;}
	if(x<0)putchar('-'),x=-x;
	if(x>=10)qw(x/10);putchar(x%10+'0');
}IL void qw(long long x,char op){qw(x),putchar(op);}
IL void ws(string s){FOR(i,0,s.size())putchar(s[i]);}
IL TY Ceil(TY a,TY b){return a/b+(a%b!=0);}
IL TY Mod(TY a){return (a>=mod?a-mod:a);}
IL TY Abs(TY a,TY b){return a>b?a-b:b-a;}
IL TY Pow(TY a,TY b){
	TY ans=1,base=a;
	while(b){
		if(b&1)ans=ans*base%mod;
		base=base*base%mod;b>>=1;
	}return ans;
}TY n,a[MAXN],b[MAXN],sum[MAXN],lenx[MAXN],leny[MAXN],ans;
vector<signed> e1[MAXN],e2[MAXN],HH;
TY Sum[MAXN],SSum[MAXN];
bool vis[MAXN];
signed L[MAXN],R[MAXN],LL[MAXN],RR[MAXN],ok[MAXN],nxtx[MAXN],nxty[MAXN];
struct node{TY l,r,tag,op;};queue<node> q;
IL void init(TY l,TY r,TY tag){
    For(i,l,r)e1[i].clear(),e2[i].clear();
    vector<pair<TY,TY> > pre,nxt;
    For(i,l,r){
        while(!pre.empty()){
            TY ch=(pre.back().second*-1+tag)*(i-pre.back().first)+sum[i]-sum[pre.back().first];
            if(ch<0){
                nxtx[pre.back().first]=i;
                pre.pop_back();continue;
            }else{
                lenx[i]=pre.back().second+Ceil(ch+1,i-pre.back().first);
                pre.push_back({i,pre.back().second+Ceil(ch+1,i-pre.back().first)});
                break;
            }
        }if(pre.empty()){
            lenx[i]=Ceil(sum[i]-sum[l-1]+tag*(i-l+1)+1,i-l+1);
            pre.push_back({i,Ceil(sum[i]-sum[l-1]+tag*(i-l+1)+1,i-l+1)});
        }
    }while(!pre.empty())nxtx[pre.back().first]=r+1,pre.pop_back();
    Rof(i,r,l){
        while(!nxt.empty()){
            TY ch=(nxt.back().second*-1+tag)*(nxt.back().first-i)-sum[i-1]+sum[nxt.back().first-1];
            if(ch<0){
                nxty[nxt.back().first]=i;
                nxt.pop_back();continue;
            }else{
                leny[i]=nxt.back().second+Ceil(ch+1,nxt.back().first-i);
                nxt.push_back({i,nxt.back().second+Ceil(ch+1,nxt.back().first-i)});
                break;
            }
        }if(nxt.empty()){
            leny[i]=Ceil(sum[r]-sum[i-1]+tag*(r-i+1)+1,r-i+1);
            nxt.push_back({i,Ceil(sum[r]-sum[i-1]+tag*(r-i+1)+1,r-i+1)});
        }
    }while(!nxt.empty())nxty[nxt.back().first]=l-1,nxt.pop_back();
    For(i,l,r)if(nxtx[i]!=r+1)e1[nxtx[i]].pb(i);
    Rof(i,r,l)if(nxty[i]!=l-1)e2[nxty[i]].pb(i);
}int main(){
    //freopen("data.in","r",stdin);
    /* init */
    n=qr();For(i,1,n)a[i]=qr(),sum[i]=sum[i-1]+a[i];
    q.push({1,n,0,0});
    while(!q.empty()){
        TY l=q.front().l,r=q.front().r,tag=q.front().tag,op=q.front().op;
        if(l>r||l<=0||r>n)continue;
        q.pop();
        if(op==0){
            vector<pair<TY,TY> > tmp;
            TY c=0;TY lst=-1;
            For(i,l,r)b[i]=a[i]+tag;
            For(i,l,r){
                if((b[i]>=0)!=lst){
                    lst=(b[i]>=0);
                    ++c;L[c]=R[c]=i;
                    Sum[c]=b[i];
                }else R[c]=i,Sum[c]+=b[i];
            }For(i,1,c)LL[i]=i,RR[i]=i,SSum[i]=Sum[i],ok[i]=0,vis[i]=1;
            Sum[c+1]=0;RR[c+1]=INF;
            For(i,1,c)if(Sum[i]<0){
                ok[i]=(Sum[i-1]+Sum[i]>=0)+(Sum[i+1]+Sum[i]>=0);
                if(ok[i]==2)HH.pb(i),ok[i]=INF;
            }else{
                ok[i]=(Sum[i-1]+Sum[i]<0)+(Sum[i+1]+Sum[i]<0);
                if(ok[i]==2)HH.pb(i),ok[i]=INF;
            }while(!HH.empty()){
                TY now=HH.back(),nowL=LL[now],nowR=RR[now];
                TY k=SSum[nowL]+SSum[nowL-1]+SSum[nowR+1],pre=LL[LL[nowL-1]-1],nxt=RR[nowR+1]+1;
                HH.pop_back();
                if(SSum[nowL]>=0){
                    if(pre>=1&&nxt<=c){
                        ok[LL[nowL-1]]=(k+SSum[pre]>=0)+(k+SSum[nxt]>=0);
                        if(ok[LL[nowL-1]]==2)HH.pb(LL[nowL-1]),ok[LL[nowL-1]]=INF;
                    }else ok[LL[nowL-1]]=INF;
                    if(pre>=1){
                        ok[pre]+=-(SSum[nowL-1]+SSum[pre]<0)+(SSum[pre]+k<0);
                        if(ok[pre]==2&&SSum[nowL-1]+SSum[pre]>=0)HH.pb(pre),ok[pre]=INF;
                    }if(nxt<=c){
                        ok[nxt]+=-(SSum[nowR+1]+SSum[nxt]<0)+(SSum[nxt]+k<0);
                        if(ok[nxt]==2&&SSum[nowR+1]+SSum[nxt]>=0)HH.pb(nxt),ok[nxt]=INF;
                    }
                }else{
                    if(pre>=1&&nxt<=c){
                        ok[LL[nowL-1]]=(k+SSum[pre]<0)+(k+SSum[nxt]<0);
                        if(ok[LL[nowL-1]]==2)HH.pb(LL[nowL-1]),ok[LL[nowL-1]]=INF;
                    }else ok[LL[nowL-1]]=INF;
                    if(pre>=1){
                        ok[pre]+=-(SSum[nowL-1]+SSum[pre]>=0)+(SSum[pre]+k>=0);
                        if(ok[pre]==2&&SSum[nowL-1]+SSum[pre]<0)HH.pb(pre),ok[pre]=INF;
                    }if(nxt<=c){
                        ok[nxt]+=-(SSum[nowR+1]+SSum[nxt]>=0)+(SSum[nxt]+k>=0);
                        if(ok[nxt]==2&&SSum[nowR+1]+SSum[nxt]<0)HH.pb(nxt),ok[nxt]=INF;
                    }
                }SSum[LL[nowL-1]]=SSum[RR[nowR+1]]=k;
                RR[LL[nowL-1]]=RR[nowR+1];
                LL[RR[nowR+1]]=LL[nowL-1];
            }Rof(i,c,1)if(Sum[i]>=0&&vis[i]){
                Rof(j,i,LL[i])vis[j]=0;
                tmp.pb({L[LL[i]],R[RR[i]]});
            }Rof(i,tmp.size()-1,0)q.push({tmp[i].first,tmp[i].second,tag,1});
        }else{
            if(l==r){
                ans+=a[l]+tag+1;
                continue;
            }queue<TY> fir,sec;
            init(l,r,tag);
            For(i,l,r)if(nxtx[i]==r+1)fir.push(i);
            Rof(i,r,l)if(nxty[i]==l-1)sec.push(i);
            TY lstl=l,lstr=r,lstcnt=0;
            while(lstl<lstr){
                while(!fir.empty()&&(lstl>fir.front()||fir.front()>lstr))fir.pop();
                while(!sec.empty()&&(lstl>sec.front()||sec.front()>lstr))sec.pop();
                TY id1=(fir.empty()?INF:fir.front()),id2=(sec.empty()?INF:sec.front());
                TY cnt1=(id1==INF?INF:lenx[id1]-lstcnt);
                TY cnt2=(id2==INF?INF:leny[id2]-lstcnt);
                if(cnt1<=cnt2){
                    fir.pop();
                    lstcnt=lenx[id1];
                    For(j,lstl,id1){FOR(i,0,e2[j].size())sec.push(e2[j][i]);e2[j].clear();}
                    q.push({lstl,id1,-lstcnt+tag,0});
                    lstl=id1+1;
                }else{
                    sec.pop();
                    lstcnt=leny[id2];
                    Rof(j,lstr,id2){FOR(i,0,e1[j].size())fir.push(e1[j][i]);e1[j].clear();}
                    q.push({id2,lstr,-lstcnt+tag,0});
                    lstr=id2-1;
                }
            }if(lstl==lstr)q.push({lstl,lstl,-lstcnt+tag,1});
            ans+=lstcnt;
        }
    }qw(ans);
    return 0;
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve: