社区讨论

n^nlog(n)水过QwQ

P3415祭坛参与者 3已保存回复 9

讨论操作

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

当前回复
9 条
当前快照
1 份
快照标识符
@mi6ylu7g
此快照首次捕获于
2025/11/20 12:56
4 个月前
此快照最后确认于
2025/11/20 12:56
4 个月前
查看原帖
CPP
// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define inf 0x7fffffff
using namespace std;
typedef long long ll;
int Getint(){char c=getchar();int ret=0,f=1;while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}while(isdigit(c))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();return ret*f;}

const int Maxn = 100005;
int n,Maxx,cnt;
bool visx[Maxn],visy[Maxn];
vector<int>tx,ty;
vector<int>vex[Maxn],vey[Maxn];

struct Point {int x,y;}P[Maxn];

int main() {
    
//	freopen("sern.in","r",stdin);
//	freopen("sern.out","w",stdout);

    n=Getint();
    for(int i=1;i<=n;++i) {
        P[i].x=Getint(),P[i].y=Getint();
        vex[P[i].x].push_back(P[i].y);
        vey[P[i].y].push_back(P[i].x);
        if(!visx[P[i].x]) tx.push_back(P[i].x),visx[P[i].x]=true;
        if(!visy[P[i].y]) ty.push_back(P[i].y),visy[P[i].y]=true;
    }
    for(int i=0,sx=tx.size();i<sx;++i) sort(vex[tx[i]].begin(),vex[tx[i]].end()),unique(vex[tx[i]].begin(),vex[tx[i]].end());
    for(int i=0,sy=ty.size();i<sy;++i) sort(vey[ty[i]].begin(),vey[ty[i]].end()),unique(vey[ty[i]].begin(),vey[ty[i]].end());
    for(int i=0,sx=tx.size();i<sx;++i) {
        if(vex[tx[i]].size()<Maxx*2) continue;
 		for(int j=0,sy=ty.size();j<sy;++j) {
            if(vey[ty[j]].size()<Maxx*2) continue;
            auto iterx=upper_bound(vey[ty[j]].begin(),vey[ty[j]].end(),tx[i]);
            auto itery=upper_bound(vex[tx[i]].begin(),vex[tx[i]].end(),ty[j]);
            if(iterx==vey[ty[j]].end()||itery==vex[tx[i]].end()) continue;
            if(iterx==vey[ty[j]].begin()||itery==vex[tx[i]].begin()) continue;
            auto lx=iterx,rx=iterx;--lx;if(*lx==tx[i]) continue;
            auto ly=itery,ry=itery;--ly;if(*ly==ty[j]) continue;
            int t=min(min(lx-vey[ty[j]].begin()+1,vey[ty[j]].end()-rx),min(ly-vex[tx[i]].begin()+1,vex[tx[i]].end()-ry));
            if(t==Maxx) cnt++;
            else if(t>Maxx) Maxx=t,cnt=1;
        } 
    }
    cout<<Maxx<<"\n"<<cnt;
    return 0;
}
/*
4
0 1
2 0
2 2
3 1
*/

回复

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

正在加载回复...