| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 594976 |
2022-07-13T08:18:50 Z |
박상훈(#8436) |
Dragon 2 (JOI17_dragon2) |
C++17 |
|
4000 ms |
40452 KB |
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct Query{
int c, d, i;
bool inv;
bool operator<(const Query &Q) const{
if (d==Q.d) return c<Q.c;
return d<Q.d;
}
}Q[100100];
ll ans[100100], it = 0;
struct Point;
ll xo, yo;
int ccw(Point a, Point b, Point c);
struct Point{
ll x, y, i;
Point(){}
Point(ll _x, ll _y, ll _i): x(_x), y(_y), i(_i) {}
bool operator<(const Point &P) const{
bool left1 = (x-xo<0 || (x-xo==0 && y-yo>0));
bool left2 = (P.x-xo<0 || (P.x-xo==0 && P.y-yo>0));
if (left1!=left2) return left1 > left2;
return ccw(Point(xo, yo, 0), *this, P) > 0;
}
}a[60060], b[60060], O1, O2;
int n, ccol, c[30030], nx[30030], ny[30030], opa[30030], opb[30030];
vector<int> T[30030];
int ccw(Point a, Point b, Point c){
ll ret = (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
if (ret>0) return 1;
if (ret<0) return -1;
return 0;
}
struct Seg{
vector<int> a, tree;
int sz;
void init(){
sz = a.size();
tree.resize(sz*2, 0);
}
int getidx(int y){
return lower_bound(a.begin(), a.end(), y) - a.begin();
}
void update(int y, int val){
y = getidx(y) + sz;
for (tree[y]+=val;y>1;y>>=1) tree[y>>1] = tree[y] + tree[y^1];
}
int query(int l, int r){
int ret = 0;
l = getidx(l), r = getidx(r+1);
for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
if (l&1) ret += tree[l++];
if (r&1) ret += tree[--r];
}
return ret;
}
};
struct Seg2D{
Seg tree[120120];
int sz;
void init(int N){
sz = N;
for (int i=sz+1;i<sz*2;i++){
if (i-sz<=n){
tree[i].a.push_back(ny[a[i-sz].i]);
tree[i].a.push_back(ny[a[i-sz].i]+n);
}
else{
tree[i].a.push_back(ny[a[i-sz-n].i]);
tree[i].a.push_back(ny[a[i-sz-n].i]+n);
}
}
for (int i=sz-1;i;i--){
tree[i].a.resize(tree[i<<1].a.size() + tree[i<<1|1].a.size());
merge(tree[i<<1].a.begin(), tree[i<<1].a.end(), tree[i<<1|1].a.begin(), tree[i<<1|1].a.end(), tree[i].a.begin());
}
for (int i=1;i<sz*2;i++) tree[i].init();
}
void update(int x, int y, int val){
//return;
for (x+=sz;x;x>>=1){
tree[x].update(y, val);
}
}
int query(int x1, int x2, int y1, int y2){
//return 0;
x2++;
int ret = 0;
for (x1+=sz, x2+=sz;x1<x2;x1>>=1, x2>>=1){
if (x1&1) ret += tree[x1++].query(y1, y2);
if (x2&1) ret += tree[--x2].query(y1, y2);
}
return ret;
}
}tree;
void update(int x, int y, int val){
//printf(" %d %d %d\n", x, y, val);
tree.update(x, y, val);
tree.update(x, y+n, val);
tree.update(x+n, y, val);
tree.update(x+n, y+n, val);
}
ll query(int x1, int x2, int y1, int y2){
int c1 = ccol;
ll ret = 0;
for (int i=x1;i<=x2;i++){
if (y1 <= ny[a[i].i] && ny[a[i].i] <= y2 && c[a[i].i]==c1) ret++;
if (y1 <= ny[a[i].i]+n && ny[a[i].i]+n <= y2 && c[a[i].i]==c1) ret++;
}
return ret;
}
pair<int, int> get_range(Point a[], int op[], int sx, bool v, Point Z2, Point Z3){
if (op[sx]==sx+n){
if ((ccw(Z2, a[sx], Z3)==1) != v) return {sx+1, sx+n-1};
return {sx+1, sx};
}
if ((ccw(Z2, a[sx], Z3)==ccw(Z2, a[sx], a[op[sx]])) == v) return {sx+1, op[sx]-1};
return {op[sx], sx+n-1};
/*
int qx1, qx2;
int sx = lx-1, px = rx+1;
bool flagL = (ccw(Z1, Z2, Z3)*ccw(Z1, Z2, a[lx])==v);
while(lx<=rx){
int mx = (lx+rx)>>1;
bool flagm = (ccw(Z1, Z2, Z3)*ccw(Z1, Z2, a[mx])==v);
if (flagm==flagL) lx = mx+1;
else rx = mx-1, px = mx;
}
if (flagL) qx1 = sx+1, qx2 = px-1;
else qx1 = px, qx2 = sx+n-1;
return {qx1, qx2};*/
}
ll calc1(int c1){
ll ret = 0;
for (auto &i:T[c1]){
it++;
int sx = nx[i], sy = ny[i];
//auto Rx = get_range(a, sx+1, sx+n-1, 1, a[sx], O1, O2);
//auto Ry = get_range(b, sy+1, sy+n-1, 1, b[sy], O2, O1);
auto Rx = get_range(a, opa, sx, 0, O1, O2);
auto Ry = get_range(b, opb, sy, 0, O2, O1);
//printf("%lld %lld -> %d, %d / %d, %d\n", a[sx].x, a[sx].y, Rx.first, Rx.second, Ry.first, Ry.second);
/*int lx = sx+1, rx = sx+n-1, px = sx+n;
bool flagL = (ccw(a[sx], O1, O2)==ccw(a[sx], O1, a[lx]));
while(lx<=rx){
int mx = (lx+rx)>>1;
bool flagm = (ccw(a[sx], O1, O2)==ccw(a[sx], O1, a[mx]));
if (flagm==flagL) lx = mx+1;
else rx = mx-1, px = mx;
}
if (flagL) qx1 = sx+1, qx2 = px-1;
else qx1 = px, qx2 = sx+n-1;
int ly = sy+1, ry = sy+n-1, py = sy+n;
flagL = (ccw(b[sy], O2, O1)==ccw(b[sy], O2, b[ly]));
while(ly<=ry){
int my = (ly+ry)>>1;
bool flagm = (ccw(b[sy], O2, O1)==ccw(b[sy], O2, b[my]));
if (flagm==flagL) ly = my+1;
else ry = my-1, py = my;
}
if (flagL) qy1 = sy+1, qy2 = py-1;
else qy1 = py, qy2 = sy+n-1;*/
//printf("ok\n");
ret += tree.query(Rx.first, Rx.second, Ry.first, Ry.second);
//printf("%d %d %d %d: %d / %lld\n", qx1, qx2, qy1, qy2, tree.query(qx1, qx2, qy1, qy2), query(qx1, qx2, qy1, qy2));
/*for (int j=sx+1;j<sx+n;j++){
if (ccw(a[sx], O1, O2)!=ccw(a[sx], O1, a[j])) continue;
if (ccw(b[sy], O2, O1)!=ccw(b[sy], O2, a[j])) continue;
if (c[a[j].i]!=c2) continue;
//printf("ok: %lld %lld %lld %lld (j = %d / %lld %lld)\n", a[sx].x, a[sx].y, a[j].x, a[j].y, j, b[sy].x, b[sy].y);
ret++;
}*/
}
return ret;
}
ll calc2(int c){
ll ret = 0;
for (auto &i:T[c]){
it++;
///Case #1
int sx = nx[i], sy = ny[i];
auto Rx = get_range(a, opa, sx, 1, O1, O2);
auto Ry = get_range(b, opb, sy, 1, O2, O1);
ret += tree.query(Rx.first, Rx.second, Ry.first, Ry.second);
///Case #2
pair<int, int> S1, S2;
S1 = get_range(a, opa, sx, 0, O1, O2);
S2 = get_range(b, opb, sy, 0, O2, O1);
//printf(" org: %d %d %d %d\n", sx+1, sx+n-1, sy+1, sy+n-1);
//printf(" R: %d %d %d %d\n", Rx.first, Rx.second, Ry.first, Ry.second);
//printf(" S: %d %d %d %d\n", S1.first, S1.second, S2.first, S2.second);
if (ccw(O1, O2, a[sx])==1){ /// 0 -> 1
int tmp = nx[n];
if (!(sx<tmp && tmp<sx+n)) tmp += n;
assert(sx<tmp && tmp<sx+n);
S1.second = tmp-1;
}
else{ /// 1 -> 0
int tmp = nx[n];
if (!(sx<tmp && tmp<sx+n)) tmp += n;
assert(sx<tmp && tmp<sx+n);
S1.first = tmp+1;
}
if (ccw(O2, O1, a[sx])==1){ ///0 -> 1
int tmp = ny[n];
if (!(sy<tmp && tmp<sy+n)) tmp += n;
assert(sy<tmp && tmp<sy+n);
S2.second = tmp-1;
}
else{ /// 1 -> 0
int tmp = ny[n];
if (!(sy<tmp && tmp<sy+n)) tmp += n;
assert(sy<tmp && tmp<sy+n);
S2.first = tmp+1;
}
ret += tree.query(S1.first, S1.second, S2.first, S2.second);
//printf(" %lld %lld -> %d + %d\n", a[sx].x, a[sx].y, tree.query(Rx.first, Rx.second, Ry.first, Ry.second), tree.query(S1.first, S1.second, S2.first, S2.second));
//printf(" S: %d %d %d %d\n\n", S1.first, S1.second, S2.first, S2.second);
}
return ret;
}
void init(Point O, Point a[], int nx[], int op[]){
xo = O.x, yo = O.y;
sort(a+1, a+n+1);
for (int i=n+1;i<=n*2;i++) a[i] = a[i-n];
for (int i=1;i<=n;i++) nx[a[i].i] = i;
int pt = 2;
for (int i=1;i<=n;i++){
while(pt<i+n && ccw(O, a[i], a[pt]) >= 0) pt++;
op[i] = pt;
//printf("%lld %lld -> %lld %lld (%d)\n", a[i].x, a[i].y, a[op[i]].x, a[op[i]].y, ccw(O, a[i], a[pt]));
}
//printf("\n");
}
int main(){
//freopen("Big.txt", "r", stdin);
int m;
scanf("%d %d", &n, &m);
for (int i=1;i<=n;i++){
scanf("%lld %lld %d", &a[i].x, &a[i].y, c+i);
a[i].i = i;
b[i] = a[i];
T[c[i]].push_back(i);
}
scanf("%lld %lld %lld %lld", &O1.x, &O1.y, &O2.x, &O2.y);
a[n+1] = O2, b[n+1] = O1;
a[n+1].i = n+1, b[n+1].i = n+1;
++n;
init(O1, a, nx, opa);
init(O2, b, ny, opb);
tree.init(n*2+1);
int q;
scanf("%d", &q);
for (int i=1;i<=q;i++){
scanf("%d %d", &Q[i].c, &Q[i].d);
Q[i].i = i;
if (T[Q[i].c].size() > T[Q[i].d].size()){
Q[i].inv = 1;
swap(Q[i].c, Q[i].d);
}
else if (T[Q[i].c].size()==T[Q[i].d].size() && Q[i].c > Q[i].d){
Q[i].inv = 1;
swap(Q[i].c, Q[i].d);
}
else Q[i].inv = 0;
}
sort(Q+1, Q+q+1);
ccol = 0;
for (int i=1;i<=q;i++){
//if (i%10000==0) printf("ok %d queries\n", i);
//printf("YES %d\n", i);
if (ccol!=Q[i].d){
for (auto &j:T[ccol]) update(nx[j], ny[j], -1);
for (auto &j:T[Q[i].d]) update(nx[j], ny[j], 1);
ccol = Q[i].d;
}
//printf("update ok\n");
if (i>1 && Q[i].c==Q[i-1].c && Q[i].d==Q[i-1].d && Q[i].inv==Q[i-1].inv){
ans[Q[i].i] = ans[Q[i-1].i];
continue;
}
if (!Q[i].inv) ans[Q[i].i] = calc1(Q[i].c);
else ans[Q[i].i] = calc2(Q[i].c);
}
//printf("Total iterations: %lld\n", it);
for (int i=1;i<=q;i++) printf("%lld\n", ans[i]);
return 0;
}
Compilation message
dragon2.cpp: In function 'int main()':
dragon2.cpp:274:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
274 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
dragon2.cpp:276:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
276 | scanf("%lld %lld %d", &a[i].x, &a[i].y, c+i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:282:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
282 | scanf("%lld %lld %lld %lld", &O1.x, &O1.y, &O2.x, &O2.y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:292:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
292 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
dragon2.cpp:294:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
294 | scanf("%d %d", &Q[i].c, &Q[i].d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
10324 KB |
Output is correct |
| 2 |
Correct |
42 ms |
10324 KB |
Output is correct |
| 3 |
Correct |
265 ms |
10544 KB |
Output is correct |
| 4 |
Correct |
263 ms |
13644 KB |
Output is correct |
| 5 |
Correct |
125 ms |
13804 KB |
Output is correct |
| 6 |
Correct |
19 ms |
10428 KB |
Output is correct |
| 7 |
Correct |
21 ms |
10524 KB |
Output is correct |
| 8 |
Correct |
18 ms |
10400 KB |
Output is correct |
| 9 |
Correct |
15 ms |
10376 KB |
Output is correct |
| 10 |
Correct |
13 ms |
10380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
292 ms |
39916 KB |
Output is correct |
| 2 |
Correct |
1106 ms |
39952 KB |
Output is correct |
| 3 |
Correct |
592 ms |
40024 KB |
Output is correct |
| 4 |
Correct |
132 ms |
39940 KB |
Output is correct |
| 5 |
Correct |
60 ms |
40452 KB |
Output is correct |
| 6 |
Correct |
265 ms |
40016 KB |
Output is correct |
| 7 |
Correct |
207 ms |
39924 KB |
Output is correct |
| 8 |
Correct |
242 ms |
39912 KB |
Output is correct |
| 9 |
Correct |
131 ms |
39872 KB |
Output is correct |
| 10 |
Correct |
151 ms |
39740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
10324 KB |
Output is correct |
| 2 |
Correct |
42 ms |
10324 KB |
Output is correct |
| 3 |
Correct |
265 ms |
10544 KB |
Output is correct |
| 4 |
Correct |
263 ms |
13644 KB |
Output is correct |
| 5 |
Correct |
125 ms |
13804 KB |
Output is correct |
| 6 |
Correct |
19 ms |
10428 KB |
Output is correct |
| 7 |
Correct |
21 ms |
10524 KB |
Output is correct |
| 8 |
Correct |
18 ms |
10400 KB |
Output is correct |
| 9 |
Correct |
15 ms |
10376 KB |
Output is correct |
| 10 |
Correct |
13 ms |
10380 KB |
Output is correct |
| 11 |
Correct |
292 ms |
39916 KB |
Output is correct |
| 12 |
Correct |
1106 ms |
39952 KB |
Output is correct |
| 13 |
Correct |
592 ms |
40024 KB |
Output is correct |
| 14 |
Correct |
132 ms |
39940 KB |
Output is correct |
| 15 |
Correct |
60 ms |
40452 KB |
Output is correct |
| 16 |
Correct |
265 ms |
40016 KB |
Output is correct |
| 17 |
Correct |
207 ms |
39924 KB |
Output is correct |
| 18 |
Correct |
242 ms |
39912 KB |
Output is correct |
| 19 |
Correct |
131 ms |
39872 KB |
Output is correct |
| 20 |
Correct |
151 ms |
39740 KB |
Output is correct |
| 21 |
Correct |
268 ms |
39884 KB |
Output is correct |
| 22 |
Correct |
995 ms |
39968 KB |
Output is correct |
| 23 |
Execution timed out |
4035 ms |
40172 KB |
Time limit exceeded |
| 24 |
Halted |
0 ms |
0 KB |
- |
