社区讨论
关于map常数
P6687 论如何玩转 Excel 表格参与者 2已保存回复 7
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 7 条
- 当前快照
- 1 份
- 快照标识符
- @lodhxk09
- 此快照首次捕获于
- 2023/10/31 06:53 2 年前
- 此快照最后确认于
- 2023/11/06 22:08 2 年前
这题用map咋超时了呢。。。
CPP#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n;
long long ans;
int a[maxn],b[maxn],x[maxn],y[maxn],c[maxn],t[maxn];
map<pair<int,int>,int>mp;
void add(int x){for (;x<=n;x+=x&-x)t[x]++;}
int sum(int x){int sum=0;for (;x;x-=x&-x)sum+=t[x];return sum;}
int query(int l,int r){return sum(r)-sum(l-1);}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)scanf("%d",&a[i]);
for (int i=1;i<=n;i++)scanf("%d",&b[i]);
for (int i=1;i<=n;i++)scanf("%d",&x[i]);
for (int i=1;i<=n;i++)scanf("%d",&y[i]);
for (int i=1;i<=n;i++)mp[make_pair(x[i],y[i])]=i;
bool flag=1;
for (int i=1;i<=n;i++){
if (flag==0)break;
bool e=0;
if (mp[make_pair(a[i],b[i])]){
if ((mp[make_pair(a[i],b[i])]-i)%2)flag=0;
c[i]=mp[make_pair(a[i],b[i])];
e=1;
}
if (mp[make_pair(b[i],a[i])]){
if ((mp[make_pair(b[i],a[i])]-i)%2==0)flag=0;
c[i]=mp[make_pair(b[i],a[i])];
e=1;
}
if (e==0)flag=0;
}
if (!flag)return puts("dldsgay!!1"),0;
for (int i=1;i<=n;i++){
add(c[i]);
ans+=query(c[i]+1,n);
}
printf("%lld",ans);
return 0;
}
回复
共 7 条回复,欢迎继续交流。
正在加载回复...