Submission #1162531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162531		jerzyk	Dragon 2 (JOI17_dragon2)	C++20	100 / 100	3474 ms	9832 KiB

dragon2

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 30'007;
vector<int> sp[N];
pair<ll, ll> tab[N], ta[N], tb[N], A, B;
ll d[N];
map<pair<int, int>, int> answer;

bool C(int i, int j)
{
    if(!((d[i] < 0) ^ (d[j] < 0)))
        if(abs(d[i]) < abs(d[j]))
            return 0;
    ll x = tab[j].st - tab[i].st, y = tab[j].nd - tab[i].nd;
    ll a = x * ta[i].nd - y * (ta[i].st);
    ll b = x * tb[i].nd - y * (tb[i].st);
    return ((a > 0) ^ (b > 0));
}

inline int Cnt(int a, int b)
{
    int ans = 0;
    for(int i = 0; i < (int)sp[a].size(); ++i)
        for(int j = 0; j < (int)sp[b].size(); ++j)
            ans += (int)C(sp[a][i], sp[b][j]);
    return ans;
}

void Solve()
{
    int n, m, x, q;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
    {
        cin >> tab[i].st >> tab[i].nd >> x;
        sp[x].pb(i);
    }
    cin >> A.st >> A.nd >> B.st >> B.nd;
    for(int i = 1; i <= n; ++i)
    {
        ta[i] = make_pair(A.st - tab[i].st, A.nd - tab[i].nd);
        tb[i] = make_pair(B.st - tab[i].st, B.nd - tab[i].nd);
        d[i] = ta[i].st * tb[i].nd - ta[i].nd * tb[i].st;
    }
    cin >> q;
    int a, b;
    for(int i = 1; i <= q; ++i)
    {
        cin >> a >> b;
        if(answer.find(make_pair(a, b)) == answer.end())
            answer[make_pair(a, b)] = Cnt(a, b);
        cout << answer[make_pair(a, b)] << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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