P4087求助
  • 板块学术版
  • 楼主tonyzzzz
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/5/19 08:36
  • 上次更新2023/10/23 15:23:38
查看原帖
P4087求助
384810
tonyzzzz楼主2023/5/19 08:36

只过了三个点。。。找不到是哪里的问题 https://www.luogu.com.cn/record/110660094

#include<bits/stdc++.h>
using namespace std;

struct request{
    int time;
    int cow;
    int val;
    request(int t,int c,int v){
        time=t;
        cow=c;
        val=v;
    }
};

struct rak{
    int val;
    int cnt;
    rak(int v=0,int c=1){
        val=v;
        cnt=c;
    }
};

int N,G,in1,in2,in3;
int cnt=1;
int ans=0;
int last_val=0;
int last_cnt=0;
rak cows[4000005];
vector<request> reqs;
unordered_map<int,int> id;
unordered_map<int,int> pr;
bool is_change=false;

rak rset(long int now,long int tar,long int lb,long int rb,long int val){
    //cout<<lb<<rb<<endl;
    int mid=(lb+rb)/2;
    if(rb==lb){
        cows[now].val+=val;
        //cout<<now<<"->"<<cows[now].val<<endl;
        cows[now].cnt=1;
        return rak(cows[now].val,1);
    }
    rak r,r2;
    if(rb-lb==1){
        if(tar==lb){
            r=rset(now*2,tar,lb,lb,val);
            r2=cows[now*2+1];
        }else{
            r=rset(now*2+1,tar,rb,rb,val);
            r2=cows[now*2];
        }
    }else if(mid>tar){
        r=rset(now*2,tar,lb,mid,val);
        r2=cows[now*2+1];
    }else{
        r=rset(now*2+1,tar,mid,rb,val);
        r2=cows[now*2];
    }
    //cout<<r.val<<","<<r2.val<<endl;
    if(r.val==r2.val){
        cows[now].val=r.val;
        cows[now].cnt=r.cnt+r2.cnt;
    }else if(r.val>r2.val){
        cows[now]=r;
    }else{
        cows[now]=r2;
    }
    
    return cows[now];
}

bool cmp(request r1,request r2){
    return(r1.time<r2.time);
}

int main(){
    last_val=0;
    last_cnt=1000000;
    cin>>N>>G;
    for(int i=1;i<=N;i++){
        cin>>in1>>in2>>in3;
        reqs.push_back(request(in1,in2,in3));
    }
    sort(reqs.begin(),reqs.end(),cmp);
    for(request r:reqs){
        //cout<<r.time<<" "<<r.cow<<" "<<r.val<<endl;
        if(id.find(r.cow)==id.end()){
            id[r.cow]=cnt;
            pr[id[r.cow]]=0;
            cnt++;
        }
        rset(1,id[r.cow],1,1000000,r.val);
        if(last_val!=cows[1].val || last_cnt!=cows[1].cnt){
            ans+=1;
            last_val=cows[1].val;
            last_cnt=cows[1].cnt;
        }
    }
    cout<<ans;
}
2023/5/19 08:36
加载中...