oj.uz

답안 #594920

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

Subtask #1
15.0 / 15.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
0 / 40.0

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