QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#672823#2386. FishermenYarema#WA 1ms3724kbC++141.5kb2024-10-24 19:20:572024-10-24 19:20:58

Judging History

你现在查看的是最新测评结果

  • [2024-10-24 19:20:58]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3724kb
  • [2024-10-24 19:20:57]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef double db;


struct fish
{
	LL x, y, i;
	
	bool operator<(const fish& f) const
	{
		return MP(x - y, i) < MP(f.x - f.y, f.i);
	}
};

int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	
	int n, m, l;
	cin >> n >> m >> l;
	vector<PLL> f(n);
	FOR (i, 0, n)
		cin >> f[i].F >> f[i].S;
	sort(ALL(f), [](PLL a, PLL b)
	{
		return a.F + a.S < b.F + b.S;
	});
	set<fish> s;
	VL a(m);
	FOR (i, 0, m)
		cin >> a[i];
	VI idx(m);
	iota(ALL(idx), 0);
	sort(ALL(idx), [&a](int i, int j)
	{
		return a[i] < a[j];
	});
	VI ans(m);
	int j = 0;
	for (auto i : idx)
	{
		//cerr << i << ' ' << j << ' ' << f[j].F + f[j].S << ' ' << a[i] + l << '\n';
		while (j < n && f[j].F + f[j].S <= a[i] + l)
		{
			s.insert({f[j].F, f[j].S, j});
			j++;
		}
		//cerr << i << ' ' << SZ(s) << ' ';
		while (!s.empty())
		{
			fish p = *s.begin();
			//cerr << p.x << ' ' << p.y << ' ';
			if (p.x - p.y < a[i] - l)
				s.erase(s.begin());
			else
				break;
		}
		//cerr << SZ(s) << '\n';
		ans[i] = SZ(s);
	}
	FOR (i, 0, m)
	{
		cout << ans[i] << ' ';
	}
	cout << '\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3724kb

input:

8 4 4
7 2
3 3
4 5
5 1
2 2
1 4
8 4
9 4
6 1 4 9

output:

2 2 3 2 

result:

wrong answer 1st lines differ - expected: '2', found: '2 2 3 2 '