社区讨论

关于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 条回复,欢迎继续交流。

正在加载回复...