| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 594920 |
2022-07-13T07:10:28 Z |
박상훈(#8436) |
Dragon 2 (JOI17_dragon2) |
C++17 |
|
4000 ms |
40244 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];
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];
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){
for (x+=sz;x;x>>=1){
tree[x].update(y, val);
}
}
int query(int x1, int x2, int y1, int y2){
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 lx, int rx, int v, Point Z1, Point Z2, Point Z3){
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]){
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);
/*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){
///todo
ll ret = 0;
for (auto &i:T[c]){
///Case #1
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);
ret += tree.query(Rx.first, Rx.second, Ry.first, Ry.second);
///Case #2
pair<int, int> S1, S2;
S1 = get_range(a, sx+1, sx+n-1, 1, a[sx], O1, O2);
S2 = get_range(b, sy+1, sy+n-1, 1, b[sy], O2, O1);
//printf(" org: %d %d %d %d\n", sx+1, sx+n-1, sy+1, sy+n-1);
//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[]){
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 main(){
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);
init(O2, b, ny);
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++){
//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);
}
for (int i=1;i<=q;i++) printf("%lld\n", ans[i]);
return 0;
}
Compilation message
dragon2.cpp: In function 'int main()':
dragon2.cpp:249:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
249 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
dragon2.cpp:251:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
251 | scanf("%lld %lld %d", &a[i].x, &a[i].y, c+i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:257:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
257 | scanf("%lld %lld %lld %lld", &O1.x, &O1.y, &O2.x, &O2.y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:267:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
267 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
dragon2.cpp:269:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
269 | scanf("%d %d", &Q[i].c, &Q[i].d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
10324 KB |
Output is correct |
| 2 |
Correct |
49 ms |
10308 KB |
Output is correct |
| 3 |
Correct |
264 ms |
10508 KB |
Output is correct |
| 4 |
Correct |
352 ms |
13604 KB |
Output is correct |
| 5 |
Correct |
139 ms |
13732 KB |
Output is correct |
| 6 |
Correct |
19 ms |
10496 KB |
Output is correct |
| 7 |
Correct |
23 ms |
10432 KB |
Output is correct |
| 8 |
Correct |
17 ms |
10360 KB |
Output is correct |
| 9 |
Correct |
13 ms |
10300 KB |
Output is correct |
| 10 |
Correct |
14 ms |
10344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
288 ms |
39692 KB |
Output is correct |
| 2 |
Correct |
1094 ms |
39736 KB |
Output is correct |
| 3 |
Correct |
559 ms |
39884 KB |
Output is correct |
| 4 |
Correct |
171 ms |
39756 KB |
Output is correct |
| 5 |
Correct |
65 ms |
40244 KB |
Output is correct |
| 6 |
Correct |
210 ms |
39696 KB |
Output is correct |
| 7 |
Correct |
241 ms |
39696 KB |
Output is correct |
| 8 |
Correct |
224 ms |
39688 KB |
Output is correct |
| 9 |
Correct |
135 ms |
39440 KB |
Output is correct |
| 10 |
Correct |
125 ms |
39500 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
10324 KB |
Output is correct |
| 2 |
Correct |
49 ms |
10308 KB |
Output is correct |
| 3 |
Correct |
264 ms |
10508 KB |
Output is correct |
| 4 |
Correct |
352 ms |
13604 KB |
Output is correct |
| 5 |
Correct |
139 ms |
13732 KB |
Output is correct |
| 6 |
Correct |
19 ms |
10496 KB |
Output is correct |
| 7 |
Correct |
23 ms |
10432 KB |
Output is correct |
| 8 |
Correct |
17 ms |
10360 KB |
Output is correct |
| 9 |
Correct |
13 ms |
10300 KB |
Output is correct |
| 10 |
Correct |
14 ms |
10344 KB |
Output is correct |
| 11 |
Correct |
288 ms |
39692 KB |
Output is correct |
| 12 |
Correct |
1094 ms |
39736 KB |
Output is correct |
| 13 |
Correct |
559 ms |
39884 KB |
Output is correct |
| 14 |
Correct |
171 ms |
39756 KB |
Output is correct |
| 15 |
Correct |
65 ms |
40244 KB |
Output is correct |
| 16 |
Correct |
210 ms |
39696 KB |
Output is correct |
| 17 |
Correct |
241 ms |
39696 KB |
Output is correct |
| 18 |
Correct |
224 ms |
39688 KB |
Output is correct |
| 19 |
Correct |
135 ms |
39440 KB |
Output is correct |
| 20 |
Correct |
125 ms |
39500 KB |
Output is correct |
| 21 |
Correct |
310 ms |
39688 KB |
Output is correct |
| 22 |
Correct |
1043 ms |
39728 KB |
Output is correct |
| 23 |
Execution timed out |
4054 ms |
39960 KB |
Time limit exceeded |
| 24 |
Halted |
0 ms |
0 KB |
- |
