NC20182. [JSOI2010]下棋问题
描述
输入描述
第一行输入只有一个整数 n，代表此盘棋共下了n (1 ≤ n ≤ 5,000)个棋子。
接下來的n 行，每一行有兩个整数，依序代表这n 个棋子所放置的位置。
请注意，由于测试资料中有可能包含n=1000 的输入，你的程序必须非常的有效率才会通过所有的测试资料。
输出描述
请输出兩个整数，分别代表该盘棋兩位下棋者的累计得分數。
先下棋者(A)的分数在前，后下棋者(B)的分数在后，中间用一个空格隔开。
示例1
输入:
4 2 3 3 4 1 2 4 1
输出:
2 6
C++14(g++5.4) 解法, 执行用时: 300ms, 内存消耗: 760K, 提交时间: 2019-07-23 17:24:38
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=5005;
int N;
int p[maxn];
int q1[maxn],q2[maxn],q3[maxn],q4[maxn],top[5];
LL ans1,ans2,k;
struct Node
{
int x,y;
}a[maxn];
bool cmp(int x,int y)
{
return a[x].x<a[y].x;
}
int solve(int x)
{
memset(top,0,sizeof(top));
for(int i=1;i<=N;i++)
{
if(p[i]<x)
{
int op=1;
int t=p[i];
if(a[t].x<a[x].x&&a[t].y>a[x].y)op=2;
if(a[t].x<a[x].x&&a[t].y<a[x].y)op=3;
if(a[t].x>a[x].x&&a[t].y<a[x].y)op=4;
if(op==1)if(!top[1]||a[t].y<a[q1[top[1]]].y)q1[++top[1]]=t;
if(op==2)
{
while(top[2]&&a[t].y<a[q2[top[2]]].y)top[2]--;
q2[++top[2]]=t;
}
if(op==3)
{
while(top[3]&&a[t].y>a[q3[top[3]]].y)top[3]--;
q3[++top[3]]=t;
}
if(op==4)
if(!top[4]||a[t].y>a[q4[top[4]]].y)
q4[++top[4]]=t;
}
}
int ans=top[1]+top[2]+top[3]+top[4];
int p1=top[2],p2=0,p3=top[3]+1,p4=top[3];
for(int i=1;i<=top[1];i++)
{
while(p1>=1&&a[q2[p1]].y>a[q1[i]].y)p1--;
while(p2+1<=top[4]&&a[q4[p2+1]].x<a[q1[i]].x)p2++;
while(p3-1>=1&&(!p1||a[q3[p3-1]].x>a[q2[p1]].x))p3--;
while(p4>=1&&(p2!=0&&a[q4[p2]].y>a[q3[p4]].y))p4--;
if(p4>=p3)ans-=p4-p3+1;
}
p1=top[1]+1,p2=0,p3=top[4]+1,p4=top[4];
for(int i=1;i<=top[2];i++)
{
while(p1-1>=1&&a[q1[p1-1]].y<a[q2[i]].y)p1--;
while(p2<=top[3]&&a[q3[p2]].x<a[q2[i]].x)p2++;
while(p3-1>=1&&(p2==top[3]+1||a[q4[p3-1]].y>a[q3[p2]].y))p3--;
while(p4>=1&&(p1!=top[1]+1&&a[q4[p4]].x>a[q1[p1]].x))p4--;
if(p4>=p3)ans-=p4-p3+1;
}
return ans;
}
int main()
{
cin>>N;
for(int i=1;i<=N;i++)
{
cin>>a[i].x>>a[i].y;
p[i]=i;
}
sort(p+1,p+N+1,cmp);
for(int i=1;i<=N;i++)
{
k+=solve(i);
if(i&1)
ans1+=k;
else
ans2+=k;
}
cout<<ans1<<' '<<ans2<<endl;
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 295ms, 内存消耗: 504K, 提交时间: 2020-02-14 15:41:52
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=5000+5;
int N;
int p[maxn];
int q1[maxn],q2[maxn],q3[maxn],q4[maxn],top[5];
LL ans1,ans2,now;
struct Node
{
int x,y;
}a[maxn];
bool cmp(int x,int y)
{
return a[x].x<a[y].x;//??
}
int solve(int x)
{
memset(top,0,sizeof(top));
for(int i=1;i<=N;i++)
{
if(p[i]<x)
{
int op=1;
int t=p[i];
if(a[t].x<a[x].x&&a[t].y>a[x].y) op=2;
if(a[t].x<a[x].x&&a[t].y<a[x].y) op=3;
if(a[t].x>a[x].x&&a[t].y<a[x].y) op=4;
if(op==1) if(!top[1]||a[t].y<a[q1[top[1]]].y) q1[++top[1]]=t;
if(op==2)
{
while(top[2]&&a[t].y<a[q2[top[2]]].y) top[2]--;
q2[++top[2]]=t;
}
if(op==3)
{
while(top[3]&&a[t].y>a[q3[top[3]]].y) top[3]--;
q3[++top[3]]=t;
}
if(op==4) if(!top[4]||a[t].y>a[q4[top[4]]].y) q4[++top[4]]=t;
}
}
int ans=top[1]+top[2]+top[3]+top[4];
int p1=top[2],p2=0,p3=top[3]+1,p4=top[3];
for(int i=1;i<=top[1];i++)
{
while(p1>=1&&a[q2[p1]].y>a[q1[i]].y) p1--;
while(p2+1<=top[4]&&a[q4[p2+1]].x<a[q1[i]].x) p2++;
while(p3-1>=1&&(!p1||a[q3[p3-1]].x>a[q2[p1]].x)) p3--;
while(p4>=1&&(p2!=0&&a[q4[p2]].y>a[q3[p4]].y)) p4--;
if(p4>=p3) ans-=p4-p3+1;
}
p1=top[1]+1,p2=0,p3=top[4]+1,p4=top[4];
for(int i=1;i<=top[2];i++)
{
while(p1-1>=1&&a[q1[p1-1]].y<a[q2[i]].y) p1--;
while(p2<=top[3]&&a[q3[p2]].x<a[q2[i]].x) p2++;
while(p3-1>=1&&(p2==top[3]+1||a[q4[p3-1]].y>a[q3[p2]].y)) p3--;
while(p4>=1&&(p1!=top[1]+1&&a[q4[p4]].x>a[q1[p1]].x)) p4--;
if(p4>=p3) ans-=p4-p3+1;
}
return ans;
}
int main()
{
cin>>N;
for(int i=1;i<=N;i++) cin>>a[i].x>>a[i].y;
for(int i=1;i<=N;i++) p[i]=i;//??
sort(p+1,p+N+1,cmp);
for(int i=1;i<=N;i++)
{
now+=solve(i);
if(i&1) ans1+=now;
else ans2+=now;
}
cout<<ans1<<" "<<ans2<<endl;
return 0;
}