提出 #61828225

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int  N=1e6+10, S=1e6;

struct Segtree{
    int d[4*N];
    int FL[N*4],FR[N*4];

    void pushup(int p){
        FL[p]=FL[p*2];
        FR[p]=FR[p*2+1];
    }

    void pushdown(int p) {
        if (d[p]) {
            FL[p*2]+=d[p],FL[p*2+1]+=d[p];
            FR[p*2]+=d[p],FR[p*2+1]+=d[p];
            d[p*2]+=d[p],d[p*2+1]+=d[p];
        }
        d[p]=0;
    }

    void build(int p,int l, int r) {
        if(l==r) {
            FR[p]=FL[p]=l;
            return;
        }
        int mid=(l+r)/2;
        build(p*2,l,mid),build(p*2+1,mid+1,r);
        pushup(p);
    }

    void update(int p, int l, int r, int L, int R, int x) {
        if (L<=l && r<=R) {
            d[p]+=x; FL[p]+=x; FR[p]+=x;
            return;
        }
        int mid=(l+r)/2;
        pushdown(p);
        if (L <= mid) update(p*2,l,mid,L,R,x);
        if (R > mid) update(p*2+1,mid+1,r,L,R,x);
        pushup(p);
    }
    
    int query(int p, int l, int r, int pos) {
        if(l==r)return FL[p];
        pushdown(p);
        int mid=(l+r)/2;
        if(pos<=mid)return query(p*2,l,mid,pos);
        else return query(p*2+1,mid+1,r,pos);
    }
    // 找第一个>=val的
    int get_l(int p, int l, int r, int val) {
        if (l==r) return l;
        
        pushdown(p);
        int mid=(l+r)/2;
        //左边有
        if (FR[p*2]>=val) return get_l(p*2, l, mid, val);
        else return get_l(p*2+1, mid+1, r, val);
    }
    
    // 找最后一个<=val的
    int get_r(int p, int l, int r, int val) {
        
        if (l==r) return l;
        
        pushdown(p);
        // cerr<<"GR"<<p<<' '<<l<<' '<<r<<' '<<FL[p*2+1]<<' '<<val<<'\n';
        int mid=(l+r)/2;

        // 右边第一个就不行了
        if (FL[p*2+1]>val) return get_r(p*2, l, mid, val);
        else return get_r(p*2+1, mid+1, r, val);
    }
};

Segtree T;


int n, a[N];

int main() {
    cin>>n;
    
    T.build(1,1,S);

    for(int i=1;i<=n;i++){
        int l,r;cin>>l>>r;
        int L=T.get_l(1,1,S,l);
        int R=T.get_r(1,1,S,r);
        // cout << "opt"<<L << ' ' << R << '\n';
        T.update(1,1,S,L,R,1);
    }
    int q;cin>>q;
    for(int i=1;i<=q;i++) {
        int x;
        cin>>x;
        cout<<T.query(1,1,S,x) << '\n';
    }



    
    return 0;
}

提出情報

ジャッジ結果