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?

Why sunday again?(qp)

good luck everyone!

RP++

I hope I can solve ABC D.

Good Luck!

Wish the E problem can get accepted.

Good luck and have fun

Hope E is easy for me and for everyone!

gl guys!

E is so easy(Yes.)

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

Some problems are too template based and not flexible enough!

exquisite beyond compare

I got 1525 points.

I think E<D

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.

Why there is no editorial in English ?

when would result come out

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.)

Hey why cant I submit my code?

There is no submit button and if you type the submit link, it will return 404

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

A solution for Problem E using SegmentTree.

It's easy for me to come up with this method so I use SegmentTree. The only thing you need to do is merging nodes on SegmentTree.Then you will get AC:)

It's not the best way, but an easy way to solve Problem E. Hope this could help you.

AC link

Why problem D needs long long ?