Submission #127981

#	Time	Username	Problem	Language	Result	Execution time	Memory
127981		ainta	Dragon 2 (JOI17_dragon2)	C++17	100 / 100	1165 ms	18896 KiB

dragon2

#include<cstdio>
#include<algorithm>
#include<vector>
#define pii pair<int,int>
using namespace std;
struct point {
	long long x, y;
	int num;
	point operator +(const point &p)const {
		return { x + p.x,y + p.y };
	}
	point operator -(const point &p)const {
		return { x - p.x,y - p.y };
	}
	int dir() const {
		if (x > 0 || (x >= 0 && y > 0))return 0;
		return 1;
	}
	bool operator <(const point &p)const {
		if (dir() != p.dir())return dir() < p.dir();
		return y * p.x < p.y*x;
	}
}w[30100], ori[30100], A, B;
long long ccw(point a, point b, point c) {
	return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
}
int Col[30100];
int n, K;
struct AA {
	int x, y;
}P[30100];
struct Rect {
	int bx, by, ex, ey;
}R[30100];
void Make(point O, int ck) {
	int i;
	vector<point>T;
	for (i = 1; i <= n + 1; i++) {
		point t1 = w[i] - O; t1.num = i;
		point t2 = O - w[i]; t2.num = -i;
		T.push_back(t1);
		T.push_back(t2);
	}
	sort(T.begin(), T.end());
	int sz = T.size(), pv = 0, pv2 = 0;
	for (i = 0; i < sz; i++) {
		if (T[i].num == -(n + 1)) {
			pv = i;
		}
		if (T[i].num == n + 1)pv2 = i;
	}
	for (i = 0; i < sz; i++) {
		int t = T[(pv + i) % sz].num;
		if (abs(t) > n)continue;
		if (t > 0) {
			if (!ck)P[t].x = R[t].bx = i + 1;
			else P[t].y = R[t].by = i + 1;
		}
		else {
			t = -t;
			if (!ck)R[t].ex = i + 1;
			else R[t].ey = i + 1;
		}
	}
}
int Q;
const int SZ = 65536;
int BIT[SZ];
const int TH = 150;
void Add(int a, int b) {
	while (a < SZ) {
		BIT[a] += b;
		a += (a&-a);
	}
}
int Sum(int a) {
	int r = 0;
	while (a) {
		r += BIT[a];
		a -= (a&-a);
	}
	return r;
}
struct Seg {
	int x, b, e, ck;
	bool operator<(const Seg &p)const {
		return x < p.x;
	}
}U[SZ];
pii PP[SZ];
vector<int>G[30100];
int Query(int a, int b) {
	int i, c1 = 0, c2 = 0;
	for (auto &t : G[a]) {
		U[c1++] = { R[t].bx,R[t].by,R[t].ey,1 };
		U[c1++] = { R[t].ex + 1,R[t].by,R[t].ey,-1 };
	}
	for (auto &t : G[b]) {
		PP[c2++] = { P[t].x, P[t].y };
	}
	sort(U, U + c1);
	sort(PP, PP + c2);
	int res = 0, pv = 0;
	for (i = 0; i < c2; i++) {
		while (pv < c1 && U[pv].x <= PP[i].first) {
			Add(U[pv].b, U[pv].ck);
			Add(U[pv].e + 1, -U[pv].ck);
			pv++;
		}
		res += Sum(PP[i].second);
	}
	while (pv > 0) {
		pv--;
		Add(U[pv].b, -U[pv].ck);
		Add(U[pv].e + 1, U[pv].ck);
	}
	return res;
}
int D1[210][30100], D2[210][30100], D[30100], Num[30100];
struct BBB {
	int x, y, col;
	bool operator<(const BBB &p)const {
		return x < p.x;
	}
}PPP[SZ];
void PreCalc1(int col) {
	int i;
	for (i = 1; i <= K; i++)D[i] = 0;
	int c1 = 0, c2 = 0;
	for (auto &t : G[col]) {
		U[c1++] = { R[t].bx,R[t].by,R[t].ey,1 };
		U[c1++] = { R[t].ex + 1,R[t].by,R[t].ey,-1 };
	}
	for (i = 1; i <= n; i++) PPP[c2++] = { P[i].x,P[i].y,Col[i] };

	sort(U, U + c1);
	sort(PPP, PPP + c2);
	int res = 0, pv = 0;
	for (i = 0; i < c2; i++) {
		while (pv < c1 && U[pv].x <= PPP[i].x) {
			Add(U[pv].b, U[pv].ck);
			Add(U[pv].e + 1, -U[pv].ck);
			pv++;
		}
		D[PPP[i].col] += Sum(PPP[i].y);
	}
	while (pv > 0) {
		pv--;
		Add(U[pv].b, -U[pv].ck);
		Add(U[pv].e + 1, U[pv].ck);
	}
}
void PreCalc2(int col) {
	int i;
	for (i = 1; i <= K; i++)D[i] = 0;
	int c1 = 0, c2 = 0;
	for (i = 1; i <= n; i++) {
		U[c1++] = { R[i].bx - 1, R[i].by, R[i].ey, -Col[i] };
		U[c1++] = { R[i].ex, R[i].by, R[i].ey, Col[i] };
	}
	for (auto &t : G[col]) {
		PP[c2++] = { P[t].x, P[t].y };
	}
	sort(U, U + c1);
	sort(PP, PP + c2);

	int pv = 0;
	for (i = 0; i < c1; i++) {
		while (pv < c2 && PP[pv].first <= U[i].x) {
			Add(PP[pv].second, 1);
			pv++;
		}
		int t = Sum(U[i].e) - Sum(U[i].b - 1);
		if (U[i].ck > 0) {
			D[U[i].ck] += t;
		}
		else {
			D[-U[i].ck] -= t;
		}
	}

	for (i = 0; i < SZ; i++)BIT[i] = 0;

}
int main() {
	int i, a, b, j;
	scanf("%d%d", &n, &K);
	for (i = 1; i <= n; i++) {
		scanf("%lld%lld%d", &w[i].x, &w[i].y, &Col[i]);
		G[Col[i]].push_back(i);
		w[i].num = i;
	}
	scanf("%lld%lld%lld%lld", &A.x, &A.y, &B.x, &B.y);
	w[n + 1] = B;
	Make(A, 0);
	w[n + 1] = A;
	Make(B, 1);
	for (i = 1; i <= n; i++) {
		if (R[i].ex < R[i].bx)swap(R[i].bx, R[i].ex);
		if (R[i].ey < R[i].by)swap(R[i].by, R[i].ey);
	}
	int cc = 0;
	for (i = 1; i <= K; i++) {
		if (G[i].size() > TH) {
			Num[i] = ++cc;
			PreCalc1(i);
			for (j = 1; j <= K; j++)D1[cc][j] = D[j];
			PreCalc2(i);
			for (j = 1; j <= K; j++)D2[cc][j] = D[j];
		}
	}
	scanf("%d", &Q);
	while (Q--) {
		scanf("%d%d", &a, &b);
		if (G[b].size() > TH) {
			printf("%d\n", D2[Num[b]][a]);
		}
		else if (G[a].size() > TH) {
			printf("%d\n", D1[Num[a]][b]);
		}
		else {
			printf("%d\n", Query(a, b));
		}
	}
}

Compilation message (stderr)

dragon2.cpp: In function 'void Make(point, int)':
dragon2.cpp:45:29: warning: variable 'pv2' set but not used [-Wunused-but-set-variable]
  int sz = T.size(), pv = 0, pv2 = 0;
                             ^~~
dragon2.cpp: In function 'void PreCalc1(int)':
dragon2.cpp:138:6: warning: unused variable 'res' [-Wunused-variable]
  int res = 0, pv = 0;
      ^~~
dragon2.cpp: In function 'int main()':
dragon2.cpp:187:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &K);
  ~~~~~^~~~~~~~~~~~~~~~
dragon2.cpp:189:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%d", &w[i].x, &w[i].y, &Col[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:193:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld%lld", &A.x, &A.y, &B.x, &B.y);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:212:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
dragon2.cpp:214:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40