oj.uz

Submission #594896

# Submission time Handle Problem Language Result Execution time Memory
594896 2022-07-13T06:29:30 Z 반딧불(#8437) Dragon 2 (JOI17_dragon2) C++17
15 / 100
 4000 ms 2848 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;

struct vector2{
    ll x, y;
    vector2(){}
    vector2(ll x, ll y): x(x), y(y){}

    vector2 operator-(const vector2 &r)const{
        return vector2(x-r.x, y-r.y);
    }

    ll cross(vector2 r)const{
        return x*r.y - y*r.x;
    }
};

struct Query{
    int x, y, idx;
    Query(){}
    Query(int x, int y, int idx): x(x), y(y), idx(idx){}
    bool operator<(const Query &r)const{
        return x==r.x ? y<r.y : x<r.x;
    }
};

ll ccw(vector2 a, vector2 b){
    return a.cross(b);
}

ll ccw(vector2 a, vector2 b, vector2 c){
    return (b-a).cross(c-a);
}

inline ll sign(ll x){
    return x>0?1:-1;
}

int n, k, q;
vector2 arr[30002];
int group[30002];
ll calc[30002];
vector<int> groupList[30002];
vector2 ps, pe;

int ans[100002];
Query query[100002];

int main(){
    scanf("%d %d", &n, &k);
    for(int i=1; i<=n; i++){
        scanf("%lld %lld %d", &arr[i].x, &arr[i].y, &group[i]);
        groupList[group[i]].push_back(i);
    }
    scanf("%lld %lld %lld %lld %d", &ps.x, &ps.y, &pe.x, &pe.y, &q);
    for(int i=1; i<=q; i++){
        scanf("%d %d", &query[i].x, &query[i].y);
        query[i].idx = i;
    }

    for(int i=1; i<=n; i++) calc[i] = ccw(ps, pe, arr[i]);
    sort(query+1, query+q+1);
    for(int qi=1; qi<=q; qi++){
        Query p = query[qi];
        if(p.x == query[qi-1].x && p.y == query[qi-1].y){
            ans[p.idx] = ans[query[qi-1].idx];
            continue;
        }
        for(auto X: groupList[p.x]){
            for(auto Y: groupList[p.y]){
                if(sign(ccw(arr[X], arr[Y], ps)) == sign(ccw(arr[X], arr[Y], pe)) ||
                   (sign(calc[X]) == sign(calc[Y]) && abs(calc[X]) < abs(calc[Y]))) continue;
                ans[p.idx]++;
            }
        }
    }
    for(int i=1; i<=q; i++) printf("%d\n", ans[i]);
}

Compilation message

dragon2.cpp: In function 'int main()':
dragon2.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
dragon2.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         scanf("%lld %lld %d", &arr[i].x, &arr[i].y, &group[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf("%lld %lld %lld %lld %d", &ps.x, &ps.y, &pe.x, &pe.y, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         scanf("%d %d", &query[i].x, &query[i].y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1108 KB Output is correct
2 Correct 38 ms 1108 KB Output is correct
3 Correct 51 ms 1216 KB Output is correct
4 Correct 48 ms 2788 KB Output is correct
5 Correct 41 ms 2848 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct
8 Correct 10 ms 1140 KB Output is correct
9 Correct 8 ms 1108 KB Output is correct
10 Correct 9 ms 1108 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2256 ms 2060 KB Output is correct
2 Execution timed out 4070 ms 2004 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1108 KB Output is correct
2 Correct 38 ms 1108 KB Output is correct
3 Correct 51 ms 1216 KB Output is correct
4 Correct 48 ms 2788 KB Output is correct
5 Correct 41 ms 2848 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct
8 Correct 10 ms 1140 KB Output is correct
9 Correct 8 ms 1108 KB Output is correct
10 Correct 9 ms 1108 KB Output is correct
11 Correct 2256 ms 2060 KB Output is correct
12 Execution timed out 4070 ms 2004 KB Time limit exceeded
13 Halted 0 ms 0 KB -