oj.uz

Submission #127807

# Submission time Handle Problem Language Result Execution time Memory
127807 2019-07-10T06:33:00 Z 조승현(#3114) Dragon 2 (JOI17_dragon2) C++14
45 / 100
 4000 ms 9568 KB 
#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];
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 b, e, ck;
};
vector<Seg>U[SZ];
vector<int>G[30100], PP[SZ];
int Query(int a, int b) {
	int i;
	for (i = 0; i < SZ; i++) {
		U[i].clear();
		PP[i].clear();
		BIT[i] = 0;
	}
	for (auto &t : G[a]) {
		U[R[t].bx].push_back({ R[t].by,R[t].ey,1 });
		U[R[t].ex+1].push_back({ R[t].by,R[t].ey,-1 });
	}
	for (auto &t : G[b]) {
		PP[P[t].x].push_back(P[t].y);
	}
	int res = 0;
	for (i = 0; i < SZ; i++) {
		for (auto &t : U[i]) {
			Add(t.b, t.ck);
			Add(t.e + 1, -t.ck);
		}
		for (auto &t : PP[i]) {
			res += Sum(t);
		}
	}
	return res;
}
int main() {
	int i, a, b;
	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);
	}
	scanf("%d", &Q);
	while (Q--) {
		scanf("%d%d", &a, &b);
		printf("%d\n", Query(a, b));
	}
}

Compilation message

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 'int main()':
dragon2.cpp:116: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:118: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:122: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:131:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
dragon2.cpp:133: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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4684 KB Output is correct
2 Correct 29 ms 4816 KB Output is correct
3 Correct 1715 ms 5072 KB Output is correct
4 Execution timed out 4009 ms 5264 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 8728 KB Output is correct
2 Correct 116 ms 9324 KB Output is correct
3 Correct 95 ms 9180 KB Output is correct
4 Correct 82 ms 9176 KB Output is correct
5 Correct 82 ms 9568 KB Output is correct
6 Correct 50 ms 9100 KB Output is correct
7 Correct 49 ms 9100 KB Output is correct
8 Correct 50 ms 9100 KB Output is correct
9 Correct 36 ms 9100 KB Output is correct
10 Correct 37 ms 9112 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4684 KB Output is correct
2 Correct 29 ms 4816 KB Output is correct
3 Correct 1715 ms 5072 KB Output is correct
4 Execution timed out 4009 ms 5264 KB Time limit exceeded
5 Halted 0 ms 0 KB -