选择客栈

输入共n+1行。
第一行三个整数n，k，p，，，每两个整数之间用一个空格隔开，分别表示客栈的个数，色调的数目和能接受的最低消费的最高值；
接下来的n行，第i+1行两个整数，之间用一个空格隔开，分别表示i号客栈的装饰色调和i号客栈的咖啡店的最低消费。

C++14(g++5.4) 解法, 执行用时: 348ms, 内存消耗: 600K, 提交时间: 2019-10-12 14:39:11

#include <bits/stdc++.h>

#define rep(i, a, b) for (int i = a; i <= b; i++)

using namespace std;

typedef long long ll;

const int N = 2e6 + 10;
int n, k, p, co, mo, las, now;
int last[N], cnt[N], sum[N];

int main() {
	scanf("%d%d%d", &n, &k, &p);
	ll ans = 0;
	rep(i, 1, n) {
		scanf("%d%d", &co, &mo);
		if (mo <= p) {
			now = i;
		}
		if (now >= last[co]) sum[co] = cnt[co];
		ans += sum[co];
		last[co] = i, cnt[co]++;
	}
	cout << ans;
	return 0;
}

C++(clang++11) 解法, 执行用时: 702ms, 内存消耗: 464K, 提交时间: 2021-05-15 10:56:06

#include <iostream>
#include <iomanip>
using namespace std;
int a[200001],b[200001],c[200001];
int main()
{
	int n,m,p;
	 double ans=0;
	cin>>n>>m>>p;
	int i,x,y,pos;
	for(i=1;i<=n;i++)
	  {
	  	cin>>x>>y;
	  	if (y<=p) pos=i;
	  	if (pos>=a[x]) c[x]=b[x];
	    a[x]=i;
	    ans+=c[x];
	    b[x]++;
	  }
	cout<<setprecision(30)<<ans;
	return 0;
}

详情