链的情况 求助

P1600 [NOIP2016 提高组] 天天爱跑步

__ZXYAKIOI__ @ 2022-04-04 21:17:51

#include <bits/stdc++.h>
#define For(val) for(int i=1;i<=val;++i)
#define DEBUG printf("Passing [%s] in LINE %d.\n", __FUNCTION__, __LINE__)
using namespace std;

const int SIZE = 300000;
int n,m;
struct eDGe{int v,next;}edge[(SIZE << 1) + 9];
int box[SIZE + 9],ecnt;
inline void add_edge(int x,int y) {edge[++ecnt] = (eDGe) {y,box[x]}; box[x] = ecnt;}

int w[SIZE + 9];
int ans[SIZE + 9];

namespace subtask3{
    const int MAX_N = 100000;
    struct peo{
        int s,t;
        bool operator < (const peo &x) const {
            if(s == x.s) return t<x.t;
            return s<x.s;
        }
    }a[MAX_N + 9];

    inline void input(){
        int u,v;
        For(n-1) scanf("%d%d",&u,&v);
        For(n) scanf("%d",&w[i]);
        For(m) scanf("%d%d",&a[i].s,&a[i].t);
    }

    inline bool cmp(const int &x,const peo &y){
        return y.s>=x;
    }

    inline bool cmp_(const int &x,const peo &y){
        return y.t<=x;
    }

    inline bool Cmp(const int &x,const peo &y){
        return y.s<x;
    }

    inline bool Cmp_(const int &x,const peo &y){
        return y.t>x;
    }

    inline void solve(){
        input();
        sort(a+1,a+m+1);
        For(n){
            peo* ed = upper_bound(a+1,a+n+1,i,cmp);
            peo* edd = upper_bound(a+1,ed,i,cmp_);
            ans[i] += ed - (a+1);
            peo* eddd = upper_bound(a+1,a+n+1,i,Cmp);
            peo* edddd = upper_bound(a+1,ed,i,Cmp_);
            ans[i] += edddd - (a+1);
            printf("%d ",ans[i]);
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    subtask3::solve();
    return 0;
}

|