oj.uz

Submission #127819

# Submission time Handle Problem Language Result Execution time Memory
127819 2019-07-10T06:47:11 Z 윤교준(#3110) Dragon 2 (JOI17_dragon2) C++14
15 / 100
 4000 ms 6416 KB 
#pragma GCC optimize("Ofast")
#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 unsigned int ui;
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;

static vector<ui> QV[MAXK], QRV[MAXK];
static vector<ui> AV[MAXK];
static ll DB[MAXN];
static ui QI[MAXK], QRI[MAXK];
bitset<MAXK> haveToCal;
bitset<MAXK> chk;
bitset<MAXN> isInv;

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

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

void process() {
	ll xa, ya, tab, t, tb, *db; int *xb, *yb;
	for(ui ga = K; ga; ga--) if(haveToCal[ga]) {
		chk.reset();
		memset(QI, 0, (K+1)<<2);
		memset(QRI, 0, (K+1)<<2);
		for(ui qi : QV[ga]) {
			ui gb = qi & 32767;
			QI[gb] = qi >> 15;
			chk[gb] = true;
		}
		for(ui qi : QRV[ga]) {
			ui gb = qi & 32767;
			QRI[gb] = qi >> 15;
			chk[gb] = true;
		}
		for(ui a : AV[ga]) {
			xa = X[a]; ya = Y[a]; tab = -DB[a];
			if(isInv[a]) {
				ui b = a-1, *gb = A+b;
				xb = X+b; yb = Y+b;
				db = DB+b;
				for(; b; b--, gb--, xb--, yb--, db--) if(chk[*gb]) {
					if(xa <= 0 && ya >= BY) {
						if(xa <= *xb && ya <= *yb) continue;
						if(xa >= *xb && ya >= *yb) continue;
					} else if(xa <= 0 && ya <= 0) {
						if(xa <= *xb && ya >= *yb) continue;
						if(xa >= *xb && ya <= *yb) continue;
					} else if(xa >= BX && ya >= BY) {
						if(xa <= *xb && ya >= *yb) continue;
						if(xa >= *xb && ya <= *yb) continue;
					} else if(xa >= BX && ya <= 0) {
						if(xa <= *xb && ya <= *yb) continue;
						if(xa >= *xb && ya >= *yb) continue;
					}
					t = ya**xb - xa**yb;
					tb = tab + *db + t;
					if(t > 0) {
						if(tb < 0) {
							Ans[QI[*gb]]++;
							if(!isInv[b]) Ans[QRI[*gb]]++;
						}
					} else if(tb > 0) Ans[QRI[*gb]]++;
				}
			} else {
				ui b = a-1, *gb = A+b;
				xb = X+b; yb = Y+b;
				db = DB+b;
				for(; b; b--, gb--, xb--, yb--, db--) if(chk[*gb]) {
					if(xa <= 0 && ya >= BY) {
						if(xa <= *xb && ya <= *yb) continue;
						if(xa >= *xb && ya >= *yb) continue;
					} else if(xa <= 0 && ya <= 0) {
						if(xa <= *xb && ya >= *yb) continue;
						if(xa >= *xb && ya <= *yb) continue;
					} else if(xa >= BX && ya >= BY) {
						if(xa <= *xb && ya >= *yb) continue;
						if(xa >= *xb && ya <= *yb) continue;
					} else if(xa >= BX && ya <= 0) {
						if(xa <= *xb && ya <= *yb) continue;
						if(xa >= *xb && ya >= *yb) continue;
					}
					t = ya**xb - xa**yb;
					tb = tab + *db + t;
					if(tb > 0) {
						if(t < 0) {
							Ans[QI[*gb]]++;
							if(isInv[b]) Ans[QRI[*gb]]++;
						}
					} else if(t > 0) Ans[QRI[*gb]]++;
				}
			}
		}
	}
}

void precal() {
	BX -= AX; BY -= AY;
	for(ui i = N; i; i--) {
		X[i] -= AX;
		Y[i] -= AY;
	}
	AX = AY = 0;
	if(BX < 0) {
		BX = -BX;
		for(ui i = N; i; i--) X[i] = -X[i];
	}
	if(BY < 0) {
		BY = -BY;
		for(ui i = N; i; i--) Y[i] = -Y[i];
	}

	for(ui i = N; i; i--) AV[A[i]].eb(i);
	for(ui i = N; i; i--) {
		ll x = X[i], y = Y[i];
		DB[i] = y*BX - x*BY;

		ll t = y*BX - x*BY;
		if(t > 0) isInv[i] = true;
	}
	for(ui i = Q; i; i--) {
		QV[B[i]].eb(i<<15 | C[i]);
		QRV[C[i]].eb(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:143: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 62 ms 2680 KB Output is correct
2 Correct 62 ms 2680 KB Output is correct
3 Correct 67 ms 2808 KB Output is correct
4 Correct 53 ms 5880 KB Output is correct
5 Correct 42 ms 6416 KB Output is correct
6 Correct 15 ms 2808 KB Output is correct
7 Correct 15 ms 2808 KB Output is correct
8 Correct 40 ms 2680 KB Output is correct
9 Correct 22 ms 2552 KB Output is correct
10 Correct 28 ms 2648 KB Output is correct

Subtask #2
0 / 45.0

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

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 2680 KB Output is correct
2 Correct 62 ms 2680 KB Output is correct
3 Correct 67 ms 2808 KB Output is correct
4 Correct 53 ms 5880 KB Output is correct
5 Correct 42 ms 6416 KB Output is correct
6 Correct 15 ms 2808 KB Output is correct
7 Correct 15 ms 2808 KB Output is correct
8 Correct 40 ms 2680 KB Output is correct
9 Correct 22 ms 2552 KB Output is correct
10 Correct 28 ms 2648 KB Output is correct
11 Execution timed out 4022 ms 3960 KB Time limit exceeded
12 Halted 0 ms 0 KB -