oj.uz

Submission #127751

# Submission time Handle Problem Language Result Execution time Memory
127751 2019-07-10T05:12:21 Z 윤교준(#3110) Dragon 2 (JOI17_dragon2) C++14
15 / 100
 4000 ms 4188 KB 
#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef long long ll;

const int MAXN = 30005;
const int MAXK = 30005;
const int MAXQ = 100005;

vector<int> QV[MAXK];
vector<int> AV[MAXK];
ll DA[MAXN], DB[MAXN];
int QI[MAXK];
bitset<MAXK> haveToCal;
bitset<MAXN> chk, isInv;

int X[MAXN], Y[MAXN], A[MAXN];
int B[MAXQ], C[MAXQ];

int Ans[MAXQ];
int AX, AY, BX, BY;
int N, K, Q;

void process() {
	for(int ga = 1; ga <= K; ga++) if(haveToCal[ga]) {
		chk.reset();
		for(int qi : QV[ga]) {
			int gb = C[qi];
			QI[gb] = qi;
			for(int b : AV[gb]) chk[b] = true;
		}
		for(int a : AV[ga]) {
			ll xa = X[a], ya = Y[a], taa = -DA[a], tab = -DB[a];
			bool flag = isInv[a];
			for(int b = 1; b <= N; b++) if(chk[b]) {
				ll t = xa*Y[b] - ya*X[b];
				ll ta = taa + DA[b] - t;
				ll tb = tab + DB[b] - t;
				if((!flag && ta < 0 && tb > 0) || (flag && ta > 0 && tb < 0)) {
					Ans[QI[A[b]]]++;
				}
			}
		}
	}
}

void precal() {
	for(int i = 1; i <= N; i++) AV[A[i]].eb(i);
	for(int i = 1; i <= N; i++) {
		ll x = X[i], y = Y[i];
		DA[i] = y*AX - x*AY;
		DB[i] = y*BX - x*BY;

		ll t = (ll(AX)*BY - ll(AY)*BX) + (y*BX - x*BY) + (x*AY - y*AX);
		if(t > 0) isInv[i] = true;
	}
	for(int i = 1; i <= Q; i++) {
		QV[B[i]].eb(i);
		haveToCal[B[i]] = haveToCal[C[i]] = true;
	}
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> K;
	for(int i = 1; i <= N; i++)
		cin >> X[i] >> Y[i] >> A[i];
	cin >> AX >> AY >> BX >> BY;
	cin >> Q;
	for(int i = 1; i <= Q; i++)
		cin >> B[i] >> C[i];
	
	precal();
	process();

	for(int i = 1; i <= Q; i++)
		printf("%d\n", Ans[i]);
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 2040 KB Output is correct
2 Correct 70 ms 2040 KB Output is correct
3 Correct 101 ms 2168 KB Output is correct
4 Correct 72 ms 3960 KB Output is correct
5 Correct 61 ms 4188 KB Output is correct
6 Correct 18 ms 2168 KB Output is correct
7 Correct 18 ms 2168 KB Output is correct
8 Correct 35 ms 2040 KB Output is correct
9 Correct 24 ms 1912 KB Output is correct
10 Correct 27 ms 1912 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4003 ms 3036 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 2040 KB Output is correct
2 Correct 70 ms 2040 KB Output is correct
3 Correct 101 ms 2168 KB Output is correct
4 Correct 72 ms 3960 KB Output is correct
5 Correct 61 ms 4188 KB Output is correct
6 Correct 18 ms 2168 KB Output is correct
7 Correct 18 ms 2168 KB Output is correct
8 Correct 35 ms 2040 KB Output is correct
9 Correct 24 ms 1912 KB Output is correct
10 Correct 27 ms 1912 KB Output is correct
11 Execution timed out 4003 ms 3036 KB Time limit exceeded
12 Halted 0 ms 0 KB -