QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#116647#6326. Make Convex SequenceSingleZombieWA 135ms7456kbC++141.8kb2023-06-29 18:08:042023-06-29 18:08:06

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-29 18:08:06]
  • 评测
  • 测评结果:WA
  • 用时:135ms
  • 内存:7456kb
  • [2023-06-29 18:08:04]
  • 提交

answer

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <queue>
#include <stack>
#include <functional>
#include <map>
#include <set>
#include <bitset>
#include <ctime>
#include <cassert>
#include <complex>

const int INF = 0x3f3f3f3f;
const long long INFLL = 0x3f3f3f3f3f3f3f3fll;
#define memset0(x) memset(x, 0, sizeof(x))
#define memsetM1(x) memset(x, -1, sizeof(x))
#define memsetINF(x) memset(x, INF, sizeof(x))

using namespace std;

using ll = long long;
ll cross(ll x1, ll y1, ll x2, ll y2)
{
	return x1 * y2 - x2 * y1;
}

bool judge(const pair<int, int>& p1, const pair<int, int>& p2, const pair<int, int>& p3)
{
	auto p12x = p2.first - p1.first;
	auto p12y = p2.second - p1.second;
	auto p23x = p3.first - p2.first;
	auto p23y = p3.second - p2.second;
	return cross(p12x, p12y, p23x, p23y) <= 0;
}

double getY(int x, const pair<int, int>& a, const pair<int, int> b)
{
	double k = (b.second - a.second) / (b.first - a.first);
	return k * (x - a.first) + a.second;
}

int main()
{
	int n;
	cin >> n;
	vector<int> l(n), r(n);
	for (auto& i : l)
	{
		cin >> i;
	}
	for (auto& i : r)
	{
		cin >> i;
	}
	vector<pair<int, int>> points(n);
	int pIndex = 0;
	for (int i = 0; i < n; i++)
	{
		while (pIndex >= 2 && judge(points[pIndex - 2], points[pIndex - 1], { i, r[i] }))
		{
			pIndex--;
		}
		points[pIndex++] = { i, r[i] };
	}
	int sIndex = 0;
	bool hasAns = true;
	for (int i = 0; i < n; i++)
	{
		if (points[sIndex + 1].first < i)
		{
			sIndex++;
		}
		double y = getY(i, points[sIndex], points[sIndex + 1]);
		if (y < l[i])
		{
			hasAns = false;
			break;
		}
	}
	if (hasAns)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3416kb

input:

4
2 1 2 5
4 6 5 8

output:

Yes

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 1ms
memory: 3372kb

input:

3
1 4 2
3 7 4

output:

No

result:

ok answer is NO

Test #3:

score: -100
Wrong Answer
time: 135ms
memory: 7456kb

input:

271757
150678576 28436211 82026915 150751377 329329758 207446456 449759844 245730845 425844298 93416110 220240900 414108016 268705922 158510126 362264528 715921 468258085 104286815 63874786 73971103 476243636 89261247 440888454 422989962 422041006 436065809 498263669 368104872 458751340 280953952 40...

output:

Yes

result:

wrong answer expected NO, found YES