oj.uz

답안 #594895

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
594895 2022-07-13T06:27:42 Z 박상훈(#8436) Dragon 2 (JOI17_dragon2) C++17
60 / 100
 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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 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

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 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

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 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 -