社区讨论

为什么我这里用stable_sort会AC,而用了sort会0pts

P2163[SHOI2007] 园丁的烦恼参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lr7oqxed
此快照首次捕获于
2024/01/10 19:16
2 年前
此快照最后确认于
2024/01/10 19:52
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
//#define int long long
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
const int N=4e6+5;

struct node{
    int x,y,id;
}a[N];
int lsh[N],len,n,m,len1,tot[N];
int ans[N][5];
struct Binarytree{
    int t[N<<1];
    void ud(int x){
        while(x<=n){
            t[x]++;
            x+=x&-x;
        }
    }
    int ask(int x){
        int ret=0;
        while(x){
            ret+=t[x];
            x-=x&-x;
        }
        return ret;
    }
}bit;

int lsh_(int x){
    return lower_bound(lsh+1,lsh+len+1,x)-lsh;
}

int32_t main(){
    std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    rep(i,1,n){
        int x,y;
        cin>>x>>y;
        a[i]={x,y,0};
        lsh[++len1]=y;
    }
    rep(i,1,m){
        int x1_,y1_,x2_,y2_;
        cin>>x1_>>y1_>>x2_>>y2_;
        a[++n]={x1_-1,y1_-1,i};
        a[++n]={x2_,y2_,i};
        a[++n]={x1_-1,y2_,i};
        a[++n]={x2_,y1_-1,i};
        lsh[++len1]=y1_-1;lsh[++len1]=y2_;
    }
    sort(lsh+1,lsh+len1+1);
    len=unique(lsh+1,lsh+len1+1)-lsh-1;
    ///////////////////////////////////////////////////
    stable_sort(a+1,a+n+1,[](const node& x_,const node& y_){
        return x_.x<y_.x;
    });//here turn into sort will get 0pts!!!
    ///////////////////////////////////////////////////
    rep(i,1,n){
        if(a[i].id){
            ans[a[i].id][++tot[a[i].id]]=bit.ask(lsh_(a[i].y));
        }else{
            bit.ud(lsh_(a[i].y));
        }
    }
    rep(i,1,m){
        sort(ans[i]+1,ans[i]+5);
        cout<<ans[i][4]-ans[i][3]-ans[i][2]+ans[i][1]<<'\n';
    }
}

回复

2 条回复,欢迎继续交流。

正在加载回复...