社区讨论
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 条回复,欢迎继续交流。
正在加载回复...