68求调
查看原帖
68求调
181715
gjh303987897楼主2022/11/3 13:49
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>

using std:: endl;
using std:: cin;
using std:: cout;

typedef long long ll;

const int maxn = 1e5+11;

ll read(){
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

struct data{
    int time;
    int id;
    int cha;
    int n_id;
}in[maxn];

struct tre{
    int maxx;
    int id;
    int num;
}tree[maxn*4];

int n,g;

inline int cmp1(data a,data b){
    return a.id<b.id;
}
inline int cmp2(data a,data b){
    return a.time<b.time;
}

void update(int now){
    if(tree[now<<1].maxx>tree[now<<1|1].maxx){
        tree[now].maxx=tree[now<<1].maxx;
        tree[now].id=tree[now<<1].id;
        tree[now].num=tree[now<<1].num;
    }else if(tree[now<<1|1].maxx>tree[now<<1].maxx){
        tree[now].maxx=tree[now<<1|1].maxx;
        tree[now].id=tree[now<<1|1].id;
        tree[now].num=tree[now<<1|1].num;
    }else{
        tree[now].maxx=tree[now<<1].maxx;
        tree[now].id=tree[now<<1].id;
        tree[now].num+=tree[now<<1].num+tree[now<<1|1].num;
    }
}
void build(int now,int l,int r){
    if(l==r){
        tree[now].id=l;
        tree[now].maxx=g;
        tree[now].num=1;
        return;
    }
    int mid=(l+r)>>1;
    build(now<<1,l,mid);
    build(now<<1|1,mid+1,r);
    update(now);
}
void point_change(int now,int l,int r,int q_l,int q_r,int cha){
    if(l==r){
        tree[now].maxx+=cha;
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=q_l) point_change(now<<1,l,mid,q_l,q_r,cha);
    if(mid<q_l) point_change(now<<1|1,mid+1,r,q_l,q_r,cha);
    update(now);
}

int main(){
    n=read(),g=read();
//    cout<<"ok0"<<endl;
    for(int i=1;i<=n;i++){
        in[i].time=read();
        in[i].id=read();
        in[i].cha=read();
    }
    std:: sort(in+1,in+1+n,cmp1);
    int num_cow=0;
//    cout<<"ok1"<<endl;
    for(int i=1;i<=n;i++){
        if(in[i].id!=in[i-1].id){
            num_cow++;
        }
        in[i].n_id=num_cow;
    }
    in[0].n_id=++num_cow;
    in[0].cha=0;
    in[0].time=0;
//    cout<<"ok2 "<<num_cow<<endl;
    build(1,0,num_cow);
//    cout<<"ok3"<<endl;
    int ans=0;
    std:: sort(in+1,in+1+n,cmp2);
    for(int i=1;i<=n;i++){
        int now_num=tree[1].num;
       // cout<<num_cow<<endl;
        int now_id=tree[1].id;
        point_change(1,1,num_cow,in[i].n_id,in[i].n_id,in[i].cha);
        if(now_num!=tree[1].num){
            ans++; 
        }else if(now_id!=tree[1].id) ans++;
    }
    cout<<ans;
    return 0;
}
2022/11/3 13:49
加载中...