WA&MLE0分求调
查看原帖
WA&MLE0分求调
1772213
Ahler楼主2025/8/1 09:10
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define int long long
#define cen cout << endl
#define c1 cout << 1 << " "
#define cs cout << " ";
using namespace std;
using namespace __gnu_pbds;
int root,now_wd;
struct point{
    int x[2],val;
}p[50009];
bool operator<(point a,point b){return a.x[now_wd]<b.x[now_wd];}
struct node{
    int sz,sum,ls,rs,mi[2],mx[2];
    point tp;
}tr[500009];
void push_up(int x){
    int l=tr[x].ls,r=tr[x].rs;
    for(int i=0;i<2;i++){
        tr[x].mi[i]=tr[x].mx[i]=tr[x].tp.x[i];
        if(l){
            tr[x].mi[i]=min(tr[x].mi[i],tr[l].mi[i]);
            tr[x].mx[i]=max(tr[x].mx[i],tr[l].mx[i]);
        }
        if(r){
            tr[x].mi[i]=min(tr[x].mi[i],tr[r].mi[i]);
            tr[x].mx[i]=max(tr[x].mx[i],tr[r].mx[i]);
        }
    }
    tr[x].sum=tr[l].sum+tr[r].sum+tr[x].tp.val;
    tr[x].sz=tr[l].sz+tr[r].sz+1;
}
int build(int l,int r,int wd){
    if(l>r){
        return 0;
    }
    now_wd=wd;
    int mid=(l+r)/2;
    nth_element(p+l,p+mid,p+r+1);
    tr[mid].tp=p[mid];
    tr[mid].ls=build(l,mid-1,wd^1);
    tr[mid].rs=build(mid+1,r,wd^1);
    push_up(mid);
    return mid;
}
bool check(int x,int y,int a,int b,int c){
    return (x*a+y*b<c);
}
int query(int k,int a,int b,int c){
    int sum=0;
    sum+=check(tr[k].mi[0],tr[k].mi[1],a,b,c);
    sum+=check(tr[k].mi[0],tr[k].mx[1],a,b,c);
    sum+=check(tr[k].mx[0],tr[k].mi[1],a,b,c);
    sum+=check(tr[k].mx[0],tr[k].mx[1],a,b,c);
    if(sum==4){
        return tr[k].sum;
    }
    if(sum==0){
        return 0;
    }
    sum=0;
    if(check(tr[k].tp.x[0],tr[k].tp.x[1],a,b,c)){
        sum+=tr[k].tp.val;
    }
    sum+=query(tr[k].ls,a,b,c);
    sum+=query(tr[k].rs,a,b,c);
    return sum;
}
signed main(){
    int n,m;
    cin >> n >> m;
    for(int i=0;i<n;i++){
        cin >> p[i].x[0] >> p[i].x[1] >> p[i].val;
    }
    root=build(0,n-1,0);
    while(m--){
        int a,b,c;
        cin >> a >> b >> c;
        cout << query(root,a,b,c);
        cen;
    }
	return 0;
}
2025/8/1 09:10
加载中...