| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 594895 |
2022-07-13T06:27:42 Z |
박상훈(#8436) |
Dragon 2 (JOI17_dragon2) |
C++17 |
|
4000 ms |
40252 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;
}
ll calc1(int c1){
ll ret = 0;
for (auto &i:T[c1]){
int sx = nx[i], sy = ny[i];
int qx1, qx2, qy1, qy2;
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(qx1, qx2, qy1, qy2);
//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
return 0;
}
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);
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;
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 (!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:183:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
183 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
dragon2.cpp:185:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
185 | scanf("%lld %lld %d", &a[i].x, &a[i].y, c+i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:191:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
191 | scanf("%lld %lld %lld %lld", &O1.x, &O1.y, &O2.x, &O2.y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:198:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
198 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
dragon2.cpp:200:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
200 | 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 |
51 ms |
10356 KB |
Output is correct |
| 3 |
Correct |
257 ms |
10504 KB |
Output is correct |
| 4 |
Correct |
392 ms |
13428 KB |
Output is correct |
| 5 |
Correct |
181 ms |
13492 KB |
Output is correct |
| 6 |
Correct |
22 ms |
10448 KB |
Output is correct |
| 7 |
Correct |
18 ms |
10452 KB |
Output is correct |
| 8 |
Correct |
16 ms |
10376 KB |
Output is correct |
| 9 |
Correct |
12 ms |
10324 KB |
Output is correct |
| 10 |
Correct |
14 ms |
10324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
252 ms |
39660 KB |
Output is correct |
| 2 |
Correct |
1057 ms |
39696 KB |
Output is correct |
| 3 |
Correct |
688 ms |
39788 KB |
Output is correct |
| 4 |
Correct |
131 ms |
39804 KB |
Output is correct |
| 5 |
Correct |
62 ms |
40252 KB |
Output is correct |
| 6 |
Correct |
262 ms |
39692 KB |
Output is correct |
| 7 |
Correct |
251 ms |
39700 KB |
Output is correct |
| 8 |
Correct |
255 ms |
39680 KB |
Output is correct |
| 9 |
Correct |
122 ms |
39516 KB |
Output is correct |
| 10 |
Correct |
114 ms |
39500 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
10324 KB |
Output is correct |
| 2 |
Correct |
51 ms |
10356 KB |
Output is correct |
| 3 |
Correct |
257 ms |
10504 KB |
Output is correct |
| 4 |
Correct |
392 ms |
13428 KB |
Output is correct |
| 5 |
Correct |
181 ms |
13492 KB |
Output is correct |
| 6 |
Correct |
22 ms |
10448 KB |
Output is correct |
| 7 |
Correct |
18 ms |
10452 KB |
Output is correct |
| 8 |
Correct |
16 ms |
10376 KB |
Output is correct |
| 9 |
Correct |
12 ms |
10324 KB |
Output is correct |
| 10 |
Correct |
14 ms |
10324 KB |
Output is correct |
| 11 |
Correct |
252 ms |
39660 KB |
Output is correct |
| 12 |
Correct |
1057 ms |
39696 KB |
Output is correct |
| 13 |
Correct |
688 ms |
39788 KB |
Output is correct |
| 14 |
Correct |
131 ms |
39804 KB |
Output is correct |
| 15 |
Correct |
62 ms |
40252 KB |
Output is correct |
| 16 |
Correct |
262 ms |
39692 KB |
Output is correct |
| 17 |
Correct |
251 ms |
39700 KB |
Output is correct |
| 18 |
Correct |
255 ms |
39680 KB |
Output is correct |
| 19 |
Correct |
122 ms |
39516 KB |
Output is correct |
| 20 |
Correct |
114 ms |
39500 KB |
Output is correct |
| 21 |
Correct |
270 ms |
39672 KB |
Output is correct |
| 22 |
Correct |
1064 ms |
39724 KB |
Output is correct |
| 23 |
Execution timed out |
4054 ms |
39868 KB |
Time limit exceeded |
| 24 |
Halted |
0 ms |
0 KB |
- |
