Codeforces Round 805 (Div. 3)

基本情况

A、B、C题秒了。

D题一开始读错题了，以为是DP，后面发现是简单贪心，拖了点时间才AC。

不过无所谓，~~因为E题没思路了~~。

但是总感觉 C 做的太不优雅。

C. Train and Queries

我的做法

就纯用STL无脑模拟。跑了\(701ms\)

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<map>
#include<queue>

const int N = 2e5 + 10;

int a[N];
int n, k;

std::map<int, std::priority_queue <int,std::vector<int>,std::greater<int> > > tag1;
std::map<int, std::priority_queue <int> > tag2;

void solve(int l, int r)
{
	if (tag1[l].empty() || tag2[r].empty()) std::cout << "NO\n";
	else
	{
		if (tag1[l].top() < tag2[r].top()) std::cout << "YES\n";
		else std::cout << "NO\n";
	}
}

int main()
{
 	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	int _;std::cin >> _;
	while(_--)
	{
		std::cin >> n >> k;
		tag1.clear();tag2.clear();
		for (int i = 1; i <= n; i++) std::cin >> a[i], tag1[a[i]].push(i), tag2[a[i]].push(i);
		int a, b;
		while(k--)
		{
			std::cin >> a >> b;
			solve(a, b);
		}
	}
	return 0;
}

更优雅的

其实思想一样，只是本质上只要维护最先出现和最后出现的下标即可，我开两个优先队列显然是浪费，用两个数组维护就行了。

#include <bits/stdc++.h>
using namespace std;
int n,m,i,x,y;
void solve(){
	cin>>n>>m;
	map <int,int> a,b;
	for (i=1;i<=n;i++){
		cin>>x;
		if (a[x]==0) a[x]=i;
		b[x]=i;
	}
	for (i=1;i<=m;i++){
		cin>>x>>y;
		if (a[x]!=0 && b[y]!=0 && a[x]<=b[y]) cout<<"YES\n";
		else cout<<"NO\n";
	}
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int tests=1;
	cin>>tests;
	while (tests--)
		solve();
	return 0;
}