为啥这么慢啊
  • 板块CF19D Points
  • 楼主lzyqwq
  • 当前回复6
  • 已保存回复6
  • 发布时间2023/3/26 17:29
  • 上次更新2023/10/23 20:23:46
查看原帖
为啥这么慢啊
539211
lzyqwq楼主2023/3/26 17:29
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include<bits/stdc++.h>
#define N 200005
#define ls t<<1
#define rs t<<1|1
using namespace std;
string s;
int n,cx,cy,rex[N],rey[N],mx[N<<2];    
set<int>sx,sy,seg[N];
unordered_map<int,int>mpx,mpy;
struct request{
    int op,x,y;
}r[N];
void modify(int t,int l,int r,int x,int y){
    if(l^r){
        int m=(l+r)>>1;
        if(x<=m){
            modify(ls,l,m,x,y);
        }else{
            modify(rs,m+1,r,x,y);
        }
        mx[t]=max(mx[ls],mx[rs]);
    }else{
        mx[t]=y;
    }
}
bool find(int t,int l,int r,int ql,int qr,int y){
    if(ql<=l&&r<=qr){
        return mx[t]>y;
    }
    int m=(l+r)>>1;
    bool ret=0;
    if(ql<=m){
        if((ret|=find(ls,l,m,ql,qr,y))){
            return 1;
        }
    }
    if(qr>m){
        ret=find(rs,m+1,r,ql,qr,y);
    }
    return ret;
}
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>s>>r[i].x>>r[i].y;
        r[i].op=(s[0]=='a'?1:s[0]^'f'?2:3);
        sx.insert(r[i].x);
        sy.insert(r[i].y);
    }
    for(int i:sx){
        rex[mpx[i]=++cx]=i;
    }
    for(int i:sy){
        rey[mpy[i]=++cy]=i;
    }
    for(int i=1;i<=n;++i){
        int x=mpx[r[i].x],y=mpy[r[i].y];
        if(r[i].op==1){
            seg[x].insert(y);
            if(y==*seg[x].rbegin()){
                modify(1,1,cx,x,y);
            }
        }else if(r[i].op^3){
            if(y==*seg[x].rbegin()){
                seg[x].erase(y);
                modify(1,1,cx,x,seg[x].empty()?0:*seg[x].rbegin());
            }
        }else{
            int l=x+1,r=cx,px=0;
            while(l<=r){
                int m=(l+r)>>1;
                if(find(1,1,cx,x+1,m,y)){
                    r=(px=m)-1;
                }else{
                    l=m+1;
                }
            }
            px?cout<<rex[px]<<' '<<rey[*seg[px].upper_bound(y)]<<'\n':cout<<"-1\n";
        }
    }
}

蒟蒻努力卡常才 AC。今天连着 3 发最劣解了

2023/3/26 17:29
加载中...