oj.uz

Submission #1066188

# Submission time Handle Problem Language Result Execution time Memory
1066188 2024-08-19T16:10:54 Z Unforgettablepl Dragon 2 (JOI17_dragon2) C++17
100 / 100
 1501 ms 11732 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

typedef complex<int> point;

int cross_product(point a,const point &b) {
    a.imag(-a.imag());
    return (a*b).imag();
}

int cross_product_int(point a,const point &b) {
    if(cross_product(a,b)<0)return -1;
    return +1;
}


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,M;
    cin >> N >> M;
    vector<pair<point,int>> dragons(N);
    for(auto&[a,b]:dragons) {
        int u,v;cin>>u>>v>>b;
        a = {u,v};
    }
    point d1,d2;
    {
        int a,b;cin>>a>>b;
        d1 = {a,b};
        cin>>a>>b;
        d2 = {a,b};
    }
    vector<vector<point>> left(M+1),right(M+1);
    for(auto&[a,b]:dragons) {
        if(cross_product(d2-d1,a-d1)<0)left[b].emplace_back(a);
        else right[b].emplace_back(a);
    }
    map<pair<int,int>,int> lookup;
    int Q;
    cin >> Q;
    for(int i=1;i<=Q;i++) {
        int u,v;cin>>u>>v;
        if(lookup.count({u,v})) {
            cout << lookup[{u,v}] << '\n';
            continue;
        }
        int ans = 0;
        for(point&x:left[u]) {
            for(point&y:left[v]) {
                if(cross_product(y-x,d1-x)>0 and cross_product(y-x,d2-x)<0)ans++;
            }
            for(point&y:right[v]) {
                if(cross_product(y-x,d1-x)>0 and cross_product(y-x,d2-x)<0)ans++;
            }
        }
        for(point&x:right[u]) {
            for(point&y:left[v]) {
                if(cross_product(y-x,d1-x)<0 and cross_product(y-x,d2-x)>0)ans++;
            }
            for(point&y:right[v]) {
                if(cross_product(y-x,d1-x)<0 and cross_product(y-x,d2-x)>0)ans++;
            }
        }
        cout << ans << '\n';
        lookup[{u,v}]=ans;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 604 KB Output is correct
2 Correct 11 ms 672 KB Output is correct
3 Correct 17 ms 860 KB Output is correct
4 Correct 67 ms 7860 KB Output is correct
5 Correct 64 ms 8052 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 5 ms 680 KB Output is correct
9 Correct 5 ms 604 KB Output is correct
10 Correct 5 ms 604 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 625 ms 2644 KB Output is correct
2 Correct 948 ms 2568 KB Output is correct
3 Correct 24 ms 2396 KB Output is correct
4 Correct 8 ms 2652 KB Output is correct
5 Correct 10 ms 3972 KB Output is correct
6 Correct 754 ms 2528 KB Output is correct
7 Correct 778 ms 2520 KB Output is correct
8 Correct 446 ms 2520 KB Output is correct
9 Correct 439 ms 2140 KB Output is correct
10 Correct 449 ms 2264 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 604 KB Output is correct
2 Correct 11 ms 672 KB Output is correct
3 Correct 17 ms 860 KB Output is correct
4 Correct 67 ms 7860 KB Output is correct
5 Correct 64 ms 8052 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 5 ms 680 KB Output is correct
9 Correct 5 ms 604 KB Output is correct
10 Correct 5 ms 604 KB Output is correct
11 Correct 625 ms 2644 KB Output is correct
12 Correct 948 ms 2568 KB Output is correct
13 Correct 24 ms 2396 KB Output is correct
14 Correct 8 ms 2652 KB Output is correct
15 Correct 10 ms 3972 KB Output is correct
16 Correct 754 ms 2528 KB Output is correct
17 Correct 778 ms 2520 KB Output is correct
18 Correct 446 ms 2520 KB Output is correct
19 Correct 439 ms 2140 KB Output is correct
20 Correct 449 ms 2264 KB Output is correct
21 Correct 646 ms 2396 KB Output is correct
22 Correct 946 ms 2396 KB Output is correct
23 Correct 920 ms 2616 KB Output is correct
24 Correct 396 ms 10068 KB Output is correct
25 Correct 79 ms 10600 KB Output is correct
26 Correct 69 ms 11624 KB Output is correct
27 Correct 15 ms 5212 KB Output is correct
28 Correct 14 ms 5376 KB Output is correct
29 Correct 1501 ms 11328 KB Output is correct
30 Correct 80 ms 11244 KB Output is correct
31 Correct 68 ms 11440 KB Output is correct
32 Correct 82 ms 11256 KB Output is correct
33 Correct 365 ms 11732 KB Output is correct
34 Correct 68 ms 11604 KB Output is correct
35 Correct 69 ms 11560 KB Output is correct
36 Correct 75 ms 11348 KB Output is correct
37 Correct 70 ms 11600 KB Output is correct
38 Correct 529 ms 11460 KB Output is correct
39 Correct 453 ms 11344 KB Output is correct
40 Correct 368 ms 11524 KB Output is correct
41 Correct 1453 ms 11348 KB Output is correct
42 Correct 970 ms 11272 KB Output is correct
43 Correct 693 ms 11348 KB Output is correct
44 Correct 1016 ms 4192 KB Output is correct
45 Correct 516 ms 4172 KB Output is correct
46 Correct 353 ms 4184 KB Output is correct
47 Correct 759 ms 4152 KB Output is correct
48 Correct 421 ms 4352 KB Output is correct
49 Correct 251 ms 4272 KB Output is correct