Hope to have good grades and quality.(qp)

Notice that the point of problem A is abnormal, so I hope that this contest will not be a bad one. GL & HF!

all the best everyone! excited for this

祝大家取得好成绩

祝大家取得好成绩

Why Sunday again?

good luck everyone!

RP++

Missing one testcase in ABC C

I messed up, could not get one test case in C. could implement E but suprise suprise, no time left as I invested all of it in C

How to solve F?

In problem E, there is a solution with asymptotics O(q * max(a)) , where I just count for each segment with what coefficient the number ai will enter

really annoyed with problem C

Problem C is too hard!I used about 35 minutes to solve A,B,D,E,F.But more than 40 to solve C...

What's the expected TC in E? I did a $$$O(Q*100*log(N))$$$ solution but got TLE

Problem C

#include<bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define nl '\n'

typedef long long ll;
typedef long double ld;

using namespace std;

const ll M1 = 1000000007;
const ll M9 = 998244353;
const ll INF = (ll)1e18;

void solve()
{
    ll n,r; cin>>n>>r;
    vector<ll> a(n+1); a[0]=1;
    for(ll i=1;i<=n;i++) cin>>a[i];

    ll ans=0;
    ll f=-1,l=-1;
    for(ll i=0;i<=n;i++)
    {
        if(a[i]==0)
        {
            f=i;
            break;
        }
    }
    for(ll i=n;i>=0;i--)
    {
        if(a[i]==0)
        {
            l=i;
            break;
        }
    }
    if(f==-1 && l==-1)
    {
        cout<<0<<nl;
        return;
    }
    for(ll i=f;i<=r;i++)
    {
        if(a[i]==0) ans++;
        else
        {
            if(i!=0 && i!=n)
            ans+=2;
        }
    }
    for(ll i=r+1;i<=l;i++)
    {
        if(a[i]==0) ans++;
        else
        {
            if(i!=0 && i!=n)
            ans+=2;
        }
    }

    cout<<ans<<nl;

}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll tc = 1;
    while (tc--)
    {
        solve();
    }
    return 0;
}

My code is failing only for a single testcase can anyone help me find the error in my code.

for C, go to either direction from R if there is at least one 0 in that direction, all the obstructing (locked) doors in the way need to be unlocked before you get to the farthest 0. Once you get to that 0, greedily lock all the doors.

Sadly, I have a E's solution with Mo's in last 20min, but I have no time to finish it :(

Questions E and F remain highly formulaic, with the sole merit being that Question G offers some insight.

a great contest! but maybe the problem F can be a little more difficult. (upd: I apologize for my previous awkward English expression. It was not my intention to offend anyone. In my previous statement, ABC only stands for Atcoder Beginner's Contest and has no other meanings.)

can anyone share the concept for solving E?

Nice solution for E using the contribution technique.

For a fixed value $$$v$$$, suppose an occurrence of $$$v$$$ is at position $$$k$$$ and we consider subarray $$$[L, R]$$$.
The number of subarrays $$$[L', R']$$$ with $$$L \leq L' \leq k \leq R' \leq R$$$ that include this occurrence equals

Expanding and simplifying gives

So for all occurrences $$$k$$$ of value $$$v$$$ inside $$$[L, R]$$$, the total contribution (multiplied by $$$v$$$) is

where

• $$$\sum k$$$ is the sum of indices of positions containing $$$v$$$ in $$$[L, R]$$$,
• $$$\sum k^2$$$ is the sum of squared indices, and
• $$$\text{cnt}$$$ is the count of $$$v$$$ in $$$[L, R]$$$.

Then each query $$$[L, R]$$$ uses $$$O(100)$$$ work (iterate over values).

#include<bits/stdc++.h>
using namespace std;
int main(void){
	int n,q;
	cin>>n>>q;
	int a[n];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}

	vector<vector<long long>>dp(n+1,vector<long long>(105,0));
	vector<vector<long long>>mp(n+1,vector<long long>(105,0));
	vector<vector<long long>>sq(n+1,vector<long long>(105,0));


	for(int i=0;i<n;i++){
		for(int j=1;j<=100;j++){
			dp[i+1][j]=dp[i][j];
			mp[i+1][j]=mp[i][j];
			sq[i+1][j]=sq[i][j];
		}
		dp[i+1][a[i]]+=i+1;
		++mp[i+1][a[i]];
		sq[i+1][a[i]]+=1ll*(i+1)*(i+1);
	}


	while(q--){
		long long l,r;
		cin>>l>>r;
		long long ans=0;

		for(int i=1;i<=100;i++){
			long long cur = dp[r][i]-dp[l-1][i];
			long long cnt = mp[r][i]-mp[l-1][i];
			long long cr= 1ll*(r+1)*cur
						-(1ll*sq[r][i]-sq[l-1][i])
						-1ll*cnt*(r+1)*(l-1)
						+1ll*cur*(l-1);
			if(cnt>0){
				ans+=1ll*i*(1ll*(cr));
			}
		}
		cout<<ans<<'\n';
		
	}
}

Can someone help me in question E? I know it's purely about mathematical manipulation and simplifying the expression. I did the same and the final expression I got is:

For any query (l, r): sum form l to r of : [ A_i * (i+1-l) * (r+1-i)] = -(S2) + (r+l)*S1 + (r+1)*(1-l)*S0

where S0 = sum form l to r of : A_i S1 = sum form l to r of : i*A_i S2 = sum form l to r of : i^2*A_i

Here's my code:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, q;
    cin >> n >> q;
    vector<long long> a(n+1);
    a[0] = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i+1];
    }

    vector<long long> pre_ai(n+1), pre_ai2(n+1);
    for (int i = 1; i <= n; i++)
    {
        pre_ai[i] = a[i]*i;
        // pre_ai[i] = a[i];
        // pre_ai2[i] = a[i]*(1-i*i);
        pre_ai2[i] = a[i]*(i*i);
    }


    
    for (int i = 2; i <= n; i++)
    {
        pre_ai2[i] += pre_ai2[i-1];
        a[i] += a[i-1];
        pre_ai[i] += pre_ai[i-1];
    }
    
    for (int i = 0; i < q; i++)
    {
        int l, r;
        cin >> l >> r;

        long long S0 = a[r] - a[l-1];
        long long S1 = pre_ai[r] - pre_ai[l-1];
        long long S2 = pre_ai2[r] - pre_ai2[l-1];

        long long ans = -S2 + (r+l)*S1 + (r+1)*(1-l)*S0;
        
        cout << ans << endl;
    }    
}

Your code here...
// best tempplate
#include<bits/stdc++.h>
using namespace std;
#define int long long 

void solve(){
    int n, start;
    cin>>n>>start;
    vector<int>v(n);
    int left(-1), right(-1);
    for(int i=0;i<n;i++){
        cin>>v[i];
        if(left==-1 && v[i]==0) {
            left=i;
        }
        if(v[i]==0) right=i;   
    }
    vector<int> duplicate(v);
    if(left==-1 and right==-1){
        cout<<"0\n";
        return;
    }
    // left is leftmost index where v[i]===0 and right is rightmost index where v[i]===0
    start--; 
    int cost(0);
    if(start >=left and start<=right){
        //go left 
        //now till l from start everything is opened 
        for(int i=start;i>=left;i--){
            if(v[i]==1){
                cost++;
                v[i]=0;
            }
        }

        for(int i=left;i<=right;i++){
            if(v[i]==0){
                cost++;
            }
            if(v[i]==1){
                cost+=2;
            }
        }

      cout<<cost<<"\n";
        return ;
    }

    if(start < left){
        //go right 
        for(int i=start;i<=right;i++){
            // if(v[i]==0){
            //     cost++;
            // }
            if(v[i]==1){
                cost+=2;
            }
        }
        cout<<cost<<"\n";
        return ;
    }
    if(start > right){
        for(int i=start;i>=left;i--){
             if (v[i]==1){
                cost+=2;
            }
        }

        cout<<cost<<'\n';
        return ;
    }






    
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
  solve();
    return 0;
}

please give why this solution to question c fails - i have tried my best after 15+ wrong submission please anybody clarify me what is wrong with my solution ONNLY 2 test cases getting WA