oj.uz

Submission #127759

# Submission time Handle Problem Language Result Execution time Memory
127759 2019-07-10T05:40:10 Z 윤교준(#3110) Dragon 2 (JOI17_dragon2) C++14
15 / 100
 4000 ms 4472 KB 
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)im='-'==*p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);if(im)(x)=-(x);
#define eb emplace_back
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
using namespace std;
typedef long long ll;
static unsigned char str[5500055], *p=str;
static bool im=false;

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

unsigned int __Q[MAXQ*2+MAXK], *__Qp = __Q;
unsigned int *QV[MAXK], *QRV[MAXK], QVn[MAXK], QRVn[MAXK];

vector<int> AV[MAXK];
ll DA[MAXN], DB[MAXN];
unsigned int QI[MAXK], QRI[MAXK];
bitset<MAXK> haveToCal;
bitset<MAXK> chkQ, chkQR;
bitset<MAXN> isInv;

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

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

void process() {
	ll xa, ya, taa, tab, t, ta, tb;
	for(int ga = 1; ga <= K; ga++) if(haveToCal[ga]) {
		chkQ.reset(); chkQR.reset();
		for(int i = QVn[ga]; i--;) {
			unsigned int qi = QV[ga][i], gb = qi & 32767;
			QI[gb] = qi >> 15;
			chkQ[gb] = true;
		}
		for(int i = QRVn[ga]; i--;) {
			unsigned int qi = QRV[ga][i], gb = qi & 32767;
			QRI[gb] = qi >> 15;
			chkQR[gb] = true;
		}
		for(int a : AV[ga]) {
			xa = X[a]; ya = Y[a]; taa = -DA[a]; tab = -DB[a];
			bool flag = isInv[a];
			for(int b = 1, gb; b < a; b++) {
				gb = A[b];
				if(!chkQ[gb] && !chkQR[gb]) continue;
				t = xa*Y[b] - ya*X[b];
				ta = taa + DA[b] - t;
				tb = tab + DB[b] - t;
				if(chkQ[gb]) {
					if((!flag && ta < 0 && tb > 0) || (flag && ta > 0 && tb < 0)) {
						Ans[QI[gb]]++;
					}
				}
				if(chkQR[gb]) {
					if(isInv[b]) {
						if(ta < 0 && tb > 0) {
							Ans[QRI[gb]]++;
						}
					} else {
						if(ta > 0 && tb < 0) {
							Ans[QRI[gb]]++;
						}
					}
				}
			}
		}
	}
}

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++) {
		QVn[B[i]]++;
		QRVn[C[i]]++;
	}
	for(int i = 1; i <= K; i++) {
		QV[i] = __Qp; __Qp += QVn[i];
		QRV[i] = __Qp; __Qp += QRVn[i];
	}
	memset(QVn, 0, (K+1)<<2);
	memset(QRVn, 0, (K+1)<<2);
	for(int i = 1; i <= Q; i++) {
		QV[B[i]][QVn[B[i]]++] = i<<15 | C[i];
		QRV[C[i]][QRVn[C[i]]++] = i<<15 | B[i];
		haveToCal[B[i]] = haveToCal[C[i]] = true;
	}
}

int main() {
	fread(str, 1, 5500055, stdin);

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

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

Compilation message

dragon2.cpp: In function 'int main()':
dragon2.cpp:105:7: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  fread(str, 1, 5500055, stdin);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 1400 KB Output is correct
2 Correct 68 ms 1272 KB Output is correct
3 Correct 88 ms 1400 KB Output is correct
4 Correct 49 ms 4216 KB Output is correct
5 Correct 35 ms 4472 KB Output is correct
6 Correct 12 ms 1528 KB Output is correct
7 Correct 12 ms 1528 KB Output is correct
8 Correct 23 ms 1272 KB Output is correct
9 Correct 18 ms 1272 KB Output is correct
10 Correct 20 ms 1400 KB Output is correct

Subtask #2
0 / 45.0

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

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 1400 KB Output is correct
2 Correct 68 ms 1272 KB Output is correct
3 Correct 88 ms 1400 KB Output is correct
4 Correct 49 ms 4216 KB Output is correct
5 Correct 35 ms 4472 KB Output is correct
6 Correct 12 ms 1528 KB Output is correct
7 Correct 12 ms 1528 KB Output is correct
8 Correct 23 ms 1272 KB Output is correct
9 Correct 18 ms 1272 KB Output is correct
10 Correct 20 ms 1400 KB Output is correct
11 Execution timed out 4021 ms 2848 KB Time limit exceeded
12 Halted 0 ms 0 KB -