Submission #1307152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307152		Double_Slash	Dragon 2 (JOI17_dragon2)	C++20	100 / 100	2247 ms	8404 KiB

dragon2

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pint = pair<int, int>;
using Vec = array<ll, 2>;

Vec operator-(const Vec &a, const Vec &b) { return {a[0] - b[0], a[1] - b[1]}; }

ll operator^(const Vec &a, const Vec &b) { return a[0] * b[1] - b[0] * a[1]; }

int main() {
    int n, m;
    cin >> n >> m;
    vector<Vec> V[m + 1];
    while (n--) {
        Vec u;
        int c;
        cin >> u[0] >> u[1] >> c;
        V[c].push_back(u);
    }
    Vec d, e;
    cin >> d[0] >> d[1] >> e[0] >> e[1];
    int q;
    cin >> q;
    map<pint, int> cache;
    while (q--) {
        int i, j;
        cin >> i >> j;
        if (not cache.count({i, j})) {
            int &ans = cache[{i, j}];
            for (auto &u: V[i]) {
                auto ud = d - u, ue = e - u;
                bool ltr = (ud ^ ue) < 0;
                for (auto &v: V[j]) {
                    auto uv = v - u;
                    ans += ltr ? (ud ^ uv) < 0 and (uv ^ ue) < 0 : (ue ^ uv) < 0 and (uv ^ ud) < 0;
                }
            }
        }
        cout << cache[{i, j}] << endl;
    }
}

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40