Submission

Score: 100

User: admin

Problemset: Nostalgia v2

Language: cpp

Time: 0.110 second

Submitted On: 2025-01-11 23:40:20

#include <bits/stdc++.h>

using namespace std;

int n, x[100010], a[100010], ans, val;

struct segtree {
    vector<int> seg;

    void init() {
        seg.assign(600010, 0);
    }
    
    void upd(int l, int r, int idx, int val, int node) {
        if(l == r) {
            seg[node] = val;
            return;
        }
        int mid = (l+r)/2;
        if(idx <= mid) upd(l, mid, idx, val, node*2);
        else upd(mid+1, r, idx, val, node*2+1);
        seg[node] = min(seg[node*2], seg[node*2+1]);
    }

    int qry(int l, int r, int ql, int qr, int node) {
        if(l > qr || r < ql) return 1e9;
        if(l >= ql && r <= qr) return seg[node];
        int mid = (l+r)/2;
        return min(qry(l, mid, ql, qr, node*2), qry(mid+1, r, ql, qr, node*2+1));
    }

    void update(int idx, int val) {
        upd(1, 2*n, idx, val, 1);
    }

    int query(int ql, int qr) {
        return qry(1, 2*n, ql, qr, 1);
    }
};


int main() {
    segtree seg;
    seg.init();
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> x[i];
    }
    for(int i=1; i<=n; i++) {
        cin >> a[i];
    }
    for(int i=1; i<=n; i++) {
        seg.update(i, val);
        val += a[i];
        val -= x[i];
    }
    for(int i=1; i<=n; i++) {
        seg.update(i+n, val);
        val += a[i];
        val -= x[i];
    }
    for(int i=1; i<=n; i++) {
        if(seg.query(i, i) == seg.query(i, i+n)) ans++;
    }
    cout << ans;
    return 0;
}