oj.uz

Submission #594880

# Submission time Handle Problem Language Result Execution time Memory
594880 2022-07-13T06:01:17 Z 박상훈(#8436) Dragon 2 (JOI17_dragon2) C++17
15 / 100
 4000 ms 4308 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

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, 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;
}

ll query(int x1, int x2, int y1, int y2, int c1){
    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 calc(int c1, int c2){
    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;

        ret += query(qx1, qx2, qy1, qy2, c2);

        /*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;
}

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);

    int q;
    scanf("%d", &q);
    while(q--){
        int c1, c2;
        scanf("%d %d", &c1, &c2);
        printf("%lld\n", calc(c1, c2));
    }
    return 0;
}

Compilation message

dragon2.cpp: In function 'int main()':
dragon2.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
dragon2.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         scanf("%lld %lld %d", &a[i].x, &a[i].y, c+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |     scanf("%lld %lld %lld %lld", &O1.x, &O1.y, &O2.x, &O2.y);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
dragon2.cpp:111:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         scanf("%d %d", &c1, &c2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1364 KB Output is correct
2 Correct 91 ms 1364 KB Output is correct
3 Correct 890 ms 1504 KB Output is correct
4 Correct 1068 ms 1536 KB Output is correct
5 Correct 515 ms 1612 KB Output is correct
6 Correct 6 ms 1364 KB Output is correct
7 Correct 6 ms 1432 KB Output is correct
8 Correct 11 ms 1368 KB Output is correct
9 Correct 8 ms 1364 KB Output is correct
10 Correct 7 ms 1364 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2480 ms 4308 KB Output is correct
2 Execution timed out 4003 ms 4268 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1364 KB Output is correct
2 Correct 91 ms 1364 KB Output is correct
3 Correct 890 ms 1504 KB Output is correct
4 Correct 1068 ms 1536 KB Output is correct
5 Correct 515 ms 1612 KB Output is correct
6 Correct 6 ms 1364 KB Output is correct
7 Correct 6 ms 1432 KB Output is correct
8 Correct 11 ms 1368 KB Output is correct
9 Correct 8 ms 1364 KB Output is correct
10 Correct 7 ms 1364 KB Output is correct
11 Correct 2480 ms 4308 KB Output is correct
12 Execution timed out 4003 ms 4268 KB Time limit exceeded
13 Halted 0 ms 0 KB -