Problems were really good.

i use the same approach as mention in tutorial A but scores only 12 points, will someone help me to find out the bug?

/*
  In the name of ALLAH
  Author : Raashid Anwar
*/

#include <bits/stdc++.h>
using namespace std;
 
#define int int64_t
const int M1 =  998244353;
const int M2 =  1000000007;
mt19937 rng((uint64_t)chrono::steady_clock::now().time_since_epoch().count());

int lo[100001];
int hi[100001];


int get(int x, int y) {
  x *= (x + 1);
  x /= 2;
  x %= M2;
  y *= (y + 1);
  y /= 2;
  y %= M2;
  x = (x * y) % M2;
  return x;
}


void solve() {
  int n;
  cin >> n;
  vector <pair<int, int>> a;
  for(int i = 0; i < n; i++) {
    int h;
    cin >> h;
    a.push_back({h, i});
  }
  for(int i = 0; i < n; i++) {
    int w;
    cin >> w;
    lo[i] = (i? hi[i - 1]: 0);
    hi[i] = lo[i] + w;
  }
  sort(a.rbegin(), a.rend());
  int ans = 0;
  set <pair<int, int>> s;
  s.insert({-1, -1});
  s.insert({M2 * M2, M2 * M2});
  for(auto [height, i] : a) {
    int from = lo[i];
    int to = hi[i];
    auto ri = s.lower_bound({from, 0});
    auto li = ri;
    li--;
    if((*ri).first == hi[i]) {
      to = (*ri).second;
      s.erase(ri);
    }
    if((*li).second == lo[i]) {
      from = (*li).first;
      s.erase(li);
    }
    s.insert({from, to});
    ans = (ans + get(to - from, height)) % M2;
    ans = (ans + (M2 - get(to - hi[i], height)) % M2) % M2;
    ans = (ans + (M2 - get(lo[i] - from, height)) % M2) % M2;
  }
  cout << ans << "\n";
}

 
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  solve();
}

C can also be solved with all-directions DP + matrix fast pow: For the last layer ($$$i = D$$$), we compute for every edge $$$u \to v$$$ whether the state we get after moving from $$$u$$$ to $$$v$$$ is winning. This allows us to compute for every vertex whether starting at this vertex is a winning state in $$$O(n)$$$ time in total. Let's call those vertices winning vertices.

Let an $$$i$$$-configuration be a way of placing the tunnels between layers $$$i, i+1, ..., D$$$. (In particular, the total number of $$$i$$$-configurations is $$$n^{2(D-i)}$$$.) When considering tunnels from $$$i$$$ to $$$i+1$$$, we only care about whether this tunnel leads to a winning vertex or not. We compute for every edge $$$u \to v$$$ the number of $$$i$$$-configurations for which the state we get after moving from $$$u$$$ to $$$v$$$ is winning/losing and for which the tunnel is reachable from $$$v$$$. This in turn allows us to compute for every vertex in layer $$$i$$$ the number of $$$i$$$-configurations for which this vertex is winning in $$$O(N)$$$ time in total. Doing this for all $$$i$$$ gives an $$$O(D N)$$$ time algorithm.

To get $$$O(N + \log D)$$$ time, note that total number of winning/losing vertices in layer $$$i$$$ among all $$$i$$$-configurations depends linearly on the total number of winning and the total number of losing vertices in layer $$$i+1$$$ among all $$$(i+1)$$$-configurations. Hence we only have to run the dp three times: Twice to get the matrix of this linear map and once for the first layer (as the starting vertex is fixed). (It is also possible to avoid the third call.)

In problem C, subtask 5, I don't really get the ''we can reroot the tree easily'' part and I've complicated myself with if's and all that.. Could someone please help me?

Guys could you tell me why do i get tl on subtask 6? Code

Can someone help me find bug in my code, it is for subtask 4 of Problem A. 91100908

Can someone explain the Problem B sweep line more in detail, I don't really understand what the author means by Rmost(u), how is it calculated, and how it helps us in building the tree.

In Problem A, I am not able to understand why my solution is not working. It has only passed Subtask 2. I dont know why it does not work on all subtasks. A little help would be really appreciated.

#include <bits/stdc++.h>
using namespace std;
#define loop(i,a,n) for (ll i=a;i<n;i++)
#define loopm(i,a,n) for (ll i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define tr(container,it)\
for(auto it=container.begin();it!=container.end();it++)
#define SZ(x) ((int)(x).size())
#define WGraph(n) vector < vector < pair < ll , ll > > >(n)
typedef vector<long long> VI;
typedef long long ll;
typedef vector < vector < ll > > VII;
typedef pair<ll,ll> PII;
typedef double db;
const ll mod=1e9+7;
ll inv=0;
ll binpow(ll a ,ll b)
{
    b=b%(mod-1);//remove if m is not a prime
    a=a%mod;
    ll res=1;
    while(b>0)
    {
        if(b&1)
            res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}

ll combine2(ll h,ll val){
    return (((((((((((h+1)*(h))%mod)*(val+1))%mod)*val)%mod)*inv)%mod)*inv)%mod);//(n+1)C2*(m+1)C2
}
ll combine(ll val1,ll val2,ll h){
    ll ans=combine2(val1+val2,h)-combine2(val1,h)-combine2(val2,h);//Assuming merging then removing the 
    //rectangles that occur on the same side.
    if(ans<0)
        ans=mod-(-1*ans)%mod;
    ans%=mod;
    return ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    inv=binpow(2,mod-2);
    VI h(n,0);//heights
    VI w(n,0);//widths
    loop(i,0,n)
        cin>>h[i];
    loop(i,0,n)
        cin>>w[i];
    VI pref(n+1,0);
    loop(i,0,n){
        pref[i+1]=pref[i]+w[i];//this is prefix array that will be required during merging part
    }
    VI forw(n,0);//storing closest forward index with element smaller than index
    stack<ll> s;
    ll i=0;
    while(i<n){
        while(!s.empty()&&h[s.top()]>h[i]){
            forw[s.top()]=i;
            s.pop();
        }
        s.push(i);
        i++;
    }
    while(!s.empty()){
            forw[s.top()]=i;
            s.pop();
    }
    i=n-1;
    VI backw(n,0);//storing closest backward index with element smaller than or equal to(to prevent 
//multicounting)
    while(i>=0){
        while(!s.empty()&&h[s.top()]>=h[i]){
            backw[s.top()]=i;
            s.pop();
        }
        s.push(i);
        i--;
    }
    while(!s.empty()){
            backw[s.top()]=i;
            s.pop();
    }
    ll ans=0;
    loop(i,0,n){
        ll prev=backw[i];
        ll nxt=forw[i];
        ans+=combine(pref[nxt]-pref[i+1],pref[i]-pref[prev+1],h[i]);//the lengths and height of forward
//and backward part which are then merged.
        ans%=mod;
        ll c=w[i];
        c%=mod;
        ans+=combine(c,pref[nxt]-pref[i+1],h[i]);ans%=mod;//extra cases when current element is joing 
//with forward part
        ans+=combine(c,pref[i]-pref[prev+1],h[i]);ans%=mod;//with backward part
        ans+=combine2(h[i],c);//and with itself
        ans%=mod;
    }
    cout<<ans<<"\n";
}

I read the editorial of problem B. It's a good approach. But I didn't understand how can we find for every point q such points v, u that q is located between v and u. Could anybody please help me with that?

After 3 days of trying to get the last subtask of problem A. I finally solved it with segment tree lol.

I solved A in Linear time complexity using Stack(By precalculating the next smallest element in left and right). But not able to understand how DSU or sorting can be used to solve this problem.

Can somebody explain how DSU more clearly? How we are able to get sum of widths from x to yth node using dsu?

REDACTED

Problem $$$A$$$ was cool, cannot speak about the others since I didn't solve yet :P

I have a different solution.

Observation 1: The number of fancy rectangles in an $$$H \times W$$$ rectangle is $$$\binom{H + 1}{2} \cdot \binom{W + 1}{2}$$$.

This is true if we imagine fixing the two vertical axes of the rectangle (there are $$$(W + 1) \cdot W/2$$$ ways to do so) and then fixing the two horizontal axes of the rectangle (there are $$$(H + 1) \cdot H/2$$$ ways to do so). We divide because one of the axes will be lower than the other.

Observation 2: We can fix indices $$$(i, j)$$$ and find the number of rectangles that partially contain i and j but not i — 1 and j + 1.

Assume $$$i \ne j$$$. If $$$i = j$$$, resort to observation 1. Suppose that the minimum height from $$$i \to j$$$ is $$$H$$$. Then, we have $$$\binom{H}{2} \cdot w[i] \cdot w[j]$$$ ways to fix the rectangle. This is because we can fix the widths in $$$w[i] \cdot w[j]$$$ ways and the height in $$$\binom{H}{2}$$$ ways. This gives 30 points: 146963809, if implemented naively in $$$\mathcal{O}(N^2)$$$.

Observation 3: We can fix the minimum height $$$H$$$ on the interval and do black magic from here :P

We fix our minimum height $$$H$$$ and fix the leftmost index $$$ind$$$ which has that height. This can be done via a map in $$$\mathcal{O} (N \log N)$$$. Now, we want to find $$$\sum w[i] \cdot w[j]$$$ where $$$(i \dots j)$$$ contains $$$ind$$$ as the leftmost index with minimal height. This is a very standard problem, I've seen at least 3 variations.

We first want to find the leftmost index $$$L$$$ for which $$$\min_{L \to i} \ge H.$$$ This can be done via sparse table or segment tree and binary search. Analogously, we can find rightmost index $$$R$$$ for which $$$\min_{i \to R} > H$$$. Now what? Okay, so given $$$L, R$$$, we actually want to evaluate the sum

This can be done via prefix sums easily.

The end.

It's pretty easy I think, once you make observation 2. Code is not too bad 146970245

Can anyone help me with my pA's solution? I could only get 15 points https://ideone.com/pagI2z