Sort by

recency

|

17 Discussions

|

  • + 0 comments
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <cassert>
    
    using namespace std;
    
    // Aliases for common operations
    #define pb push_back
    #define pbk pop_back
    #define mp make_pair
    #define fs first
    #define sc second
    #define all(x) (x).begin(), (x).end()
    #define foreach(i, a) for (auto i = (a).begin(); i != (a).end(); ++i)
    #define len(a) ((int) (a).size())
    
    #ifdef CUTEBMAING
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
    #else
    #define eprintf(...) 42
    #endif
    
    // Type definitions
    typedef long long int64;
    typedef long double ld;
    typedef unsigned long long lint;
    
    const int inf = (1 << 30) - 1;
    const int64 linf = (1ll << 62) - 1;
    const int N = 1e6 + 100;
    const int K = 20;
    
    int n;
    vector<int> g[N];
    int bin[N][K], valMin[N][K], valMax[N][K];
    int in[N], out[N], curTime = 0;
    
    // Depth-First Search (DFS) function
    void dfs(int v, int p = -1) {
        in[v] = curTime++;
        bin[v][0] = p;
        valMin[v][0] = min(v, p == -1 ? inf : p);
        valMax[v][0] = max(v, p);
    
        for (int i = 1; i < K; i++) {
            if (bin[v][i - 1] == -1) {
                bin[v][i] = -1;
                valMin[v][i] = valMin[v][i - 1];
                valMax[v][i] = valMax[v][i - 1];
            } else {
                bin[v][i] = bin[bin[v][i - 1]][i - 1];
                valMin[v][i] = min(valMin[v][i - 1], valMin[bin[v][i - 1]][i - 1]);
                valMax[v][i] = max(valMax[v][i - 1], valMax[bin[v][i - 1]][i - 1]);
            }
        }
    
        for (int to : g[v]) {
            if (to != p) {
                dfs(to, v);
            }
        }
        out[v] = curTime++;
    }
    
    // Check if u is an ancestor of v
    inline bool anc(int u, int v) {
        return in[u] <= in[v] && out[v] <= out[u];
    }
    
    // Get the minimum value in the path from u to v
    inline int smallMin(int u, int v) {
        if (anc(u, v)) return inf;
        int ans = inf;
    
        for (int i = K - 1; i >= 0; i--) {
            if (bin[u][i] != -1 && !anc(bin[u][i], v)) {
                ans = min(ans, valMin[u][i]);
                u = bin[u][i];
            }
        }
    
        ans = min(ans, valMin[u][0]);
        assert(bin[u][0] != -1);
        return ans;
    }
    
    inline int getMin(int u, int v) {
        return min(smallMin(u, v), smallMin(v, u));
    }
    
    // Get the maximum value in the path from u to v
    inline int smallMax(int u, int v) {
        if (anc(u, v)) return -inf;
        int ans = -inf;
    
        for (int i = K - 1; i >= 0; i--) {
            if (bin[u][i] != -1 && !anc(bin[u][i], v)) {
                ans = max(ans, valMax[u][i]);
                u = bin[u][i];
            }
        }
    
        ans = max(ans, valMax[u][0]);
        assert(bin[u][0] != -1);
        return ans;
    }
    
    inline int getMax(int u, int v) {
        return max(smallMax(u, v), smallMax(v, u));
    }
    
    int nextL[N], nextR[N];
    vector<int> rmq[N * 4];
    
    // Build the Range Minimum Query (RMQ) structure
    void make_rmq(int i, int l, int r) {
        if (l == r) {
            rmq[i].pb(nextL[l]);
            return;
        }
    
        make_rmq(i * 2, l, (l + r) / 2);
        make_rmq(i * 2 + 1, (l + r) / 2 + 1, r);
        rmq[i].resize(len(rmq[i * 2]) + len(rmq[i * 2 + 1]));
        merge(all(rmq[i * 2]), all(rmq[i * 2 + 1]), rmq[i].begin());
    }
    
    // Get the number of values in the range [l, r] less than v
    int getValue(int i, int ll, int rr, int l, int r, int v) {
        if (ll > r || rr < l) return 0;
        if (l <= ll && rr <= r) {
            return upper_bound(all(rmq[i]), v) - rmq[i].begin();
        }
        return getValue(i * 2, ll, (ll + rr) / 2, l, r, v) + getValue(i * 2 + 1, (ll + rr) / 2 + 1, rr, l, r, v);
    }
    
    int main() {
        cin >> n;
        for (int i = 0; i < n - 1; i++) {
            int a, b;
            scanf("%d%d", &a, &b);
            a--, b--;
            g[a].pb(b);
            g[b].pb(a);
        }
    
        dfs(0);
    
        vector<int> stack;
        stack.pb(0);
        for (int i = 0; i < n; i++) {
            nextR[i] = inf;
            nextL[i] = -inf;
        }
    
        int64 ans = 0;
        for (int i = 1; i < n; i++) {
            while (!stack.empty() && getMin(stack.back(), i) != stack.back()) {
                nextR[stack.back()] = i;
                stack.pbk();
            }
            stack.pb(i);
        }
    
        stack.clear();
        stack.pb(n - 1);
        for (int i = n - 2; i >= 0; i--) {
            while (!stack.empty() && getMax(stack.back(), i) != stack.back()) {
                nextL[stack.back()] = i;
                stack.pbk();
            }
            stack.pb(i);
        }
    
        make_rmq(1, 0, n - 1);
        for (int i = 0; i < n; i++) {
            ans += getValue(1, 0, n - 1, i, nextR[i] - 1, i - 1);
        }
    
        cout << ans << endl;
        return 0;
    }
    
  • + 0 comments

    ONLY 15 TEST CASES ARE PASSED WHY?

    from heapq import *
    n=int(input())
    neighbors = {}
    
    for x in range(n):
        neighbors[x] = []
    for i in range(n-1):
        a, b = map(int,input().split())
        neighbors[a-1].append(b-1)
        neighbors[b-1].append(a-1)
    def search(source):
        ans = 0
        cur_max = 0
        cur_len = 0
        heap = [source]
        vis = [False for i in range(n)]
        while len(heap) > 0:
            x = heappop(heap)
            cur_max = max(cur_max, x)
            cur_len += 1
            vis[x] = True
            if cur_max - source + 1 == cur_len:
                ans += 1
            for y in neighbors[x]:
                if y >= source and vis[y] == False:
                    heappush(heap, y)
        return ans
    ans = 0
    prev = 0
    for x in range(n-1, -1, -1):
        neigh = 0
        plus = 0
        for y in neighbors[x]:
            if y > x:
                neigh += 1
            if y == x + 1:
                plus = 1
        if plus == neigh and plus == 1:
            prev += 1
        else:
            prev = search(x)
        ans += prev
    print(ans)
    
  • + 1 comment

    www.germanic.ae – Dubai’s leading auto repair destination. Provide your vehicle with the exceptional care and attention it deserves.

  • + 0 comments

    any hints on the problem please

  • + 0 comments

    Self-driving buses are revolutionizing transportation with safer and more efficient rides. However, they face challenges like navigating city streets and ensuring passenger safety. Need a professional mascot logo? Check out my services on Fiverr!