WA on #2 求大佬看看啊

P4148 简单题

TLE自动机 @ 2019-10-04 15:51:59

我交了一页。。。

看有很多人80的都是too short on 525 啊,有没有做过的大佬看看

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define inf 1926081700
#define alpha 0.75
#define ll long long 
using namespace std;
int read(){
    int x=0,pos=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') pos=0;
    for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
    return pos?x:-x;
} 
const int N = 400001;
int n,k,ans,lnk[N],lst[N],rub[N];
struct sqr{
    int x1,x2,y1,y2;
}q;
struct point{
    int x[2],cnt;
}p[N],pn;
struct node{
    int mi[2],mx[2],sz,sum;point c;
}t[N];
int rt,D,rs[N],ls[N],top,tot;
int operator < (point a,point b){
    return a.x[D]<b.x[D];
}
void push_up(int now){
    int l=ls[now],r=rs[now];t[now].sz=t[l].sz+t[r].sz+1;t[now].sum=t[l].sum+t[r].sum+t[now].c.cnt;
    for(register int i=0;i<=1;i++){
        t[now].mi[i]=t[now].mx[i]=t[now].c.x[i];
        if(l) t[now].mi[i]=min(t[now].mi[i],t[l].mi[i]),t[now].mx[i]=max(t[now].mx[i],t[l].mx[i]);
        if(r) t[now].mi[i]=min(t[now].mi[i],t[r].mi[i]),t[now].mx[i]=max(t[now].mx[i],t[r].mx[i]);
    }
}
inline int newnode(){
    if(top) return rub[top--];
    else return ++tot;
}
inline int build(int l,int r,int d){
    if(l>r) return 0;
    int now=newnode(),mid=(l+r)>>1;
    D=d,nth_element(p+l,p+mid,p+r+1);
    t[now].c=p[mid],ls[now]=build(l,mid-1,d^1),rs[now]=build(mid+1,r,d^1);
    push_up(now); return now;
}
inline void clear(int now,int pos){
    if(ls[now]) clear(ls[now],pos);
    p[pos+t[ls[now]].sz+1]=t[now].c,rub[++top]=now;
    if(rs[now]) clear(rs[now],pos+t[ls[now]].sz+1);
}
inline void check(int &now,int d){
    if(alpha*(double)(t[now].sz)<(double)(t[ls[now]].sz)||alpha*(double)(t[now].sz)<(double)(t[rs[now]].sz)){
        clear(now,0);now=build(1,t[now].sz,d);
    }
}
inline void insert(int &now,point p,int d){
    if(!now){
        now=newnode();ls[now]=rs[now]=0;t[now].c=p;push_up(now);return;
    }
    if(p.x[d]<=t[now].c.x[d]){
        insert(ls[now],p,d^1);
    }else{
        insert(rs[now],p,d^1);
    }
    push_up(now);check(now,d);
}
int chkin(int now,sqr tp){
    return (!(t[now].mx[0]<tp.x1||t[now].mi[0]>tp.x2||t[now].mx[1]<tp.y1||t[now].mi[1]>tp.y2));
}
int totalin(int now,sqr tp){
    return (t[now].mx[0]<=tp.x2&&t[now].mi[0]>=tp.x1&&t[now].mx[1]<=tp.y2&&t[now].mi[1]>=tp.y1);
}
int ptin(point a,sqr b){
    return (b.x2>=a.x[0]&&b.x1<=a.x[0]&&b.y1<=a.x[1]&&b.y2>=a.x[1]);
}
inline int query(int now,sqr tp){
    if(!now) return 0;
    int re=0;
    if(totalin(now,tp)){
        return t[now].sum;
    }else if(!chkin(now,tp)) return 0;
    if(ptin(t[now].c,tp)) re+=t[now].c.cnt;
    int l=ls[now],r=rs[now];
    re+= query(l,tp);
    re+= query(r,tp);
    return re;
}
int main(){
    int n=read();
    while(n--){
        int opt=read();
        if(opt==1){
            pn.x[0]=(read()^ans),pn.x[1]=(read()^ans),pn.cnt=(read()^ans);
            insert(rt,pn,0);
        }else if(opt==2){
            q.x1=(read()^ans),q.y1=(read()^ans),q.x2=(read()^ans),q.y2=(read()^ans);
            ans=query(rt,q);printf("%d\n",ans);
        }else return 0;
    }
    return 0;
}

by Refined_heart @ 2019-12-03 22:40:38

我也是……


by Refined_heart @ 2019-12-03 22:46:59

@TLE自动机

因为不只n个操作,所以答案不够qwq


by Refined_heart @ 2019-12-03 22:47:45

刚刚自己试了,把

while(n--)

改成

while(1)+break

就行了


by TLE自动机 @ 2019-12-04 10:34:29

@Refined_heart 谢大佬


|