This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
~~~~~^~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |