QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#763918#7711. Rikka with Linescrimson231WA 642ms29744kbC++235.2kb2024-11-19 22:45:222024-11-19 22:45:36

Judging History

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

  • [2024-11-19 22:45:36]
  • 评测
  • 测评结果:WA
  • 用时:642ms
  • 内存:29744kb
  • [2024-11-19 22:45:22]
  • 提交

answer

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <deque>
#include <cstring>
#include <cassert>
typedef long long ll;
typedef double ld;
typedef std::vector<int> Vint;
typedef std::vector<ll> Vll;
typedef std::vector<ld> Vld;
const int LEN = 1e5 + 5;
ll gcd(ll a, ll b) { while (b) { ll tmp = a % b; a = b; b = tmp; } return a; }
ll gcd(ll a, ll b, ll c) { a = std::abs(a); b = std::abs(b); c = std::abs(c); a = gcd(a, b); return gcd(a, c); }
void norm(ll& x, ll& y) {
	ll gcd_ = gcd(std::abs(x), std::abs(y));
	x /= gcd_; y /= gcd_;
	return;
}

int T, N, CNT[4];
struct Pos {
	ll x, y;
	Pos(ll x_ = 0, ll y_ = 0) : x(x_), y(y_) {}
	bool operator == (const Pos& q) const { return x == q.x && y == q.y; }
};
struct FracPos {
	ll x, y;
	ll dx, dy;
	int qd, i, f;
	FracPos(ll x_ = 0, ll dx_ = 0, ll y_ = 0, ll dy_ = 0, int qd_ = 0, int f_ = 0) : x(x_), y(y_), dx(dx_), dy(dy_), qd(qd_), f(f_) {}
	ll mod_x() const { return std::abs(x) % std::abs(dx); }
	ll mod_y() const { return std::abs(y) % std::abs(dy); }
	bool x_int() const { return dx != 0 && !mod_x(); }
	ll x_() const { return x / dx; }
	bool y_int() const { return dy != 0 && !mod_y(); }
	ll y_() const { return y / dy; }
	bool is_int() const { return x_int() && y_int(); }
	Pos p() const { return Pos(x / dx, y / dy); }
} P1, P2, P3, P4 ;
typedef std::vector<FracPos> Polygon;
bool x_eq(const FracPos& p, const FracPos& q) { return p.x * q.dx == q.x * p.dx; }
bool y_eq(const FracPos& p, const FracPos& q) { return p.y * q.dy == q.y * p.dy; }
bool eq(const FracPos& p, const FracPos& q) { return x_eq(p, q) && y_eq(p, q); }
bool comp(const FracPos& p, const FracPos& q) {
	if (p.qd != q.qd) return p.qd < q.qd;
	//if (eq(p, q)) return p.f < q.f;
	if (p.qd == 0) return p.x * q.dx > q.x * p.dx;
	if (p.qd == 1) return p.y * q.dy > q.y * p.dy;
	if (p.qd == 2) return p.x * q.dx < q.x * p.dx;
	if (p.qd == 3) return p.y * q.dy < q.y * p.dy;
	assert(0);
	return 0;
}
struct Line {
	ll a, b;
	Line(ll a_ = 0, ll b_ = 0) : a(a_), b(b_) {}
} L[LEN];
struct Seg {
	int l, r;
	bool operator<(const Seg& o) const { return l == o.l ? r < o.r : l < o.l; }
} SEG[LEN]; int sp;
Polygon intersections(const Line& l, const FracPos& p1, const FracPos& p2) {
	FracPos a, b, c, d;
	ll x1 = p2.y - l.b, d1 = l.a; norm(x1, d1);
	a = FracPos(x1, d1, p2.y, 1);
	if (x1 <= p1.x * d1 || p2.x * d1 < x1) a.dx = a.dy = 0;
	ll x3 = p1.y - l.b, d3 = l.a; norm(x3, d3);
	c = FracPos(x3, d3, p1.y, 1);
	if (x3 < p1.x * d3 || p2.x * d3 <= x3) c.dx = c.dy = 0;
	ll y2 = p1.x * l.a + l.b;
	b = FracPos(p1.x, 1, y2, 1);
	if (b.y_() <= p1.y || p2.y < b.y_()) b.dx = b.dy = 0;
	ll y4 = p2.x * l.a + l.b;
	d = FracPos(p2.x, 1, y4, 1);
	if (d.y_() < p1.y || p2.y <= d.y_()) d.dx = d.dy = 0;
	a.qd = 0, b.qd = 1, c.qd = 2, d.qd = 3;
	//if (a.is_int() && (b.is_int() && a.p() == b.p())) a.dx = a.dy = 0;
	//if (b.is_int() && (c.is_int() && b.p() == c.p())) b.dx = b.dy = 0;
	//if (c.is_int() && (d.is_int() && c.p() == d.p())) c.dx = c.dy = 0;
	//if (d.is_int() && (a.is_int() && d.p() == a.p())) d.dx = b.dy = 0;
	Polygon v;
	if (a.dx) v.push_back(a);
	if (b.dx) v.push_back(b);
	if (c.dx) v.push_back(c);
	if (d.dx) v.push_back(d);
	return v;
}

ll fenwick[LEN * 2];
ll sum(int idx) {
	ll s = 0;
	while (idx > 0) {
		s += fenwick[idx];
		idx -= idx & -idx;
	}
	return s;
}
void update(int idx, int diff) {
	while (idx < LEN * 2) {
		fenwick[idx] += diff;
		idx += idx & -idx;
	}
}

void query() {
	std::cin >> N >> P3.x >> P3.y >> P1.x >> P1.y;
	/*
	P2 -- P1
	|      |
	P3 -- P4
	*/
	P2.x = P3.x; P2.y = P1.y; P4.x = P1.x; P4.y = P3.y;
	memset(CNT, 0, sizeof CNT);
	memset(fenwick, 0, sizeof fenwick);
	for (int i = 0; i < N; i++) std::cin >> L[i].a >> L[i].b;
	std::priority_queue<Seg> PQ;
	Polygon P;
	for (int i = 0; i < N; i++) {
		Polygon V = intersections(L[i], P3, P1);
		if (V.empty()) continue;
		if (V.size() == 1) {
			P.push_back(V[0]);
			P.back().i = i;
			P.push_back(V[0]);
			P.back().i = i; P.back().f = 1;
		}
		if (V.size() == 2) {
			P.push_back(V[0]);
			P.back().i = i;
			P.push_back(V[1]);
			P.back().i = i; P.back().f = 1;
		}
	}
	std::sort(P.begin(), P.end(), comp);
	// for (int i = 0; i < P.size(); ++i) std::cout << "index: " << P[i].i << ' ' << P[i].f << '\n';

	//assert(P[0].f == 0);
	SEG[P[0].i].l = 1;
	for (int i = 1, idx = 1; i < P.size(); ++i) {
		if (!eq(P[i], P[i - 1])) idx++;
		// std::cout << i << ' ' << P[i].i << ' ' << P[i].f << ' ' << idx << '\n';
		(!P[i].f ? SEG[P[i].i].l : SEG[P[i].i].r) = idx;
	}
	// for (int i = 0; i < N; ++i) std::cout << SEG[i].l << ' ' << SEG[i].r << '\n';
	std::sort(SEG, SEG + N);
	
	ll ret = 0;
	for (int i = 0; i < N; ++i) {
		if (!SEG[i].l) continue;
		ret += sum(SEG[i].r) - sum(SEG[i].l - 1);
		update(SEG[i].r, 1);
	}
	std::cout << ret << '\n';
}
void solve() {
	P1.dx = 1; P1.dy = 1; P2.dx = 1; P2.dy = 1;
	P3.dx = 1; P3.dy = 1; P4.dx = 1; P4.dy = 1;
	std::cin.tie(0)->sync_with_stdio(0);
	std::cout.tie(0);
	std::cout << std::fixed;
	std::cout.precision(3);
	std::cin >> T;
	while (T--) query();
	return;
}
int main() { solve(); return 0; }

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 7772kb

input:

1
4 0 0 2 2
2 -1
1 0
-1 2
2 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: -100
Wrong Answer
time: 642ms
memory: 29744kb

input:

1000
99981 -729383395 -411431000737086146 -663099572 622842060014806018
6815159 -4872972553264521
-44664715 3425012672809037
-896158824 -386342591542384
-375531970 1040294806535662
483111943 -6742268275140254
611052273 -1055860484502308
434838119 6111752598959468
848557869 532300694586514
857250003 ...

output:

3638833
3945324559
3308732526
3987886722
90719553
75360
14916
45775
9645
84508
6068
69740
70893
17255
18821
12327
104748
73689
90658
13845
13957
75656
78158
14518
7569
7909
83182
94029
3864
14454
97646
83840
6658
94933
18842
103943
75341
90014
78593
22688
11667
83574
81363
73888
67492
39114
8098
102...

result:

wrong answer 1st numbers differ - expected: '1698824', found: '3638833'