Submission #1128263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128263		PVSekhar	Dragon 2 (JOI17_dragon2)	C++20	100 / 100	1295 ms	24896 KiB

dragon2

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std; 
using namespace std; 
using namespace __gnu_pbds;
#define ll long long
// const ll MOD = 998244353;
const ll MOD = 1e9 + 7;
const ll N = 3e4 + 2;
const ll Q = 1e5 + 2;

struct Pt {
    ll x, y, t;
};

struct Tree {
    typedef int T;
    static constexpr T unit = 0;
    T f(T a, T b) { return a + b; } // (any associative fn)
    vector<T> s; int n;
    Tree(int n = 0, T def = unit) : s(2*n, def), n(n) {}
    void init(int _n = 0, T def = unit) {
        n = _n;
        s.resize(2 * n);
        s.assign(2 * n, def);
    }
    void update(int pos, T val) {
        for (s[pos += n] = val; pos /= 2;)
            s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
    }
    T query(int b, int e) { // query [ b , e)
        T ra = unit, rb = unit;
        for (b += n, e += n; b < e; b /= 2, e /= 2) {
            if (b % 2) ra = f(ra, s[b++]);
            if (e % 2) rb = f(s[--e], rb);
        }
        return f(ra, rb);
    }
};

Pt d, e, o;
ll n, m, q;
map<pair<ll, ll>, ll> mp;
vector<set<ll>> sm(N), la(N);
vector<Pt> side1, side0;
vector<int> cnt(N, 0);

ll cross(const Pt &p, const Pt &q) {
    return (q.y - o.y) * (p.x - o.x) - (p.y - o.y) * (q.x - o.x);
}

bool side(const Pt &p) {
    if (p.y == o.y) return p.x > o.x;
    return p.y > o.y;
}

bool operator<(const Pt &p, const Pt &q) {
    bool s1 = side(p), s2 = side(q);
    if (s1 != s2) return s1 < s2;
    return cross(p, q) > 0;
}

bool operator==(const Pt &p, const Pt &q) {
    return p.x == q.x && p.y == q.y && p.t == q.t;
}

void handle_sm() {
    int l = 0, r;
    Pt opp;
    vector<vector<Pt>> clan(m + 1), clan1(m + 1);
    vector<Tree> seg(m + 1), seg1(m + 1);
    map<pair<ll, ll>, int> ind;
    o = e;
    sort(side1.begin(),side1.end(),[&](const Pt &p, const Pt &q) { return cross(p, q) < 0;});
    sort(side0.begin(),side0.end(),[&](const Pt &p, const Pt &q) { return cross(p, q) > 0;});
    for (auto p : side0) clan[p.t].push_back(p);
    for (int i = 1; i <= m; i++) {
        seg[i].init(clan[i].size() + 5, 0);
        for (int j = 1; j <= clan[i].size(); j++) {
            seg[i].update(j, 1);
            ind[make_pair(clan[i][j - 1].x, clan[i][j - 1].y)] = j;
        }
    }
    for (auto p : side1) clan1[p.t].push_back(p);
    for (int i = 1; i <= m; i++) {
        seg1[i].init(clan1[i].size() + 5, 0);
        for (int j = 1; j <= clan1[i].size(); j++) {
            ind[make_pair(clan1[i][j - 1].x, clan1[i][j - 1].y)] = j;
        }
    }
    o = d;
    sort(side1.begin(),side1.end(),[&](const Pt &p, const Pt &q) { return cross(p, q) > 0;});
    sort(side0.begin(),side0.end(),[&](const Pt &p, const Pt &q) { return cross(p, q) > 0;});
    for (Pt p : side1) {
        seg1[p.t].update(ind[make_pair(p.x, p.y)], 1);
        o = d;
        while (l < side0.size() && cross(p, side0[l]) > 0) {
            seg[side0[l].t].update(ind[make_pair(side0[l].x, side0[l].y)], 0);
            l++;
        }
        o = e;
        opp.x = 2 * e.x - p.x, opp.y = 2 * e.y - p.y;
        for (int x : sm[p.t]) {
            r = upper_bound(clan[x].begin(), clan[x].end(), opp, [&](const Pt &p, const Pt &q){ return cross(p, q) > 0;}) - clan[x].begin();
            mp[make_pair(p.t, x)] += seg[x].query(1, r + 1);
            r = upper_bound(clan1[x].begin(), clan1[x].end(), p, [&](const Pt &p, const Pt &q){ return cross(p, q) < 0;}) - clan1[x].begin();
            mp[make_pair(p.t, x)] += seg1[x].query(1, r + 1);
        }
    }
}

void handle_la() {
    int l = 0, r;
    Pt opp;
    vector<vector<Pt>> clan(m + 1), clan1(m + 1);
    vector<Tree> seg(m + 1), seg1(m + 1);
    map<pair<ll, ll>, int> ind;
    o = e;
    sort(side1.begin(),side1.end(),[&](const Pt &p, const Pt &q) { return cross(p, q) > 0;});
    sort(side0.begin(),side0.end(),[&](const Pt &p, const Pt &q) { return cross(p, q) > 0;});
    for (auto p : side0) clan[p.t].push_back(p);
    for (int i = 1; i <= m; i++) {
        seg[i].init(clan[i].size() + 5, 0);
        for (int j = 1; j <= clan[i].size(); j++) {
            seg[i].update(j, 1);
            ind[make_pair(clan[i][j - 1].x, clan[i][j - 1].y)] = j;
        }
    }
    for (auto p : side1) clan1[p.t].push_back(p);
    for (int i = 1; i <= m; i++) {
        seg1[i].init(clan1[i].size() + 5, 0);
        for (int j = 1; j <= clan1[i].size(); j++) {
            seg1[i].update(j, 1);
            ind[make_pair(clan1[i][j - 1].x, clan1[i][j - 1].y)] = j;
        }
    }
    o = d;
    sort(side1.begin(),side1.end(),[&](const Pt &p, const Pt &q) { return cross(p, q) > 0;});
    sort(side0.begin(),side0.end(),[&](const Pt &p, const Pt &q) { return cross(p, q) > 0;});
    for (Pt p : side1) {
        seg1[p.t].update(ind[make_pair(p.x, p.y)], 0);
        o = d;
        while (l < side0.size() && cross(p, side0[l]) > 0) {
            seg[side0[l].t].update(ind[make_pair(side0[l].x, side0[l].y)], 0);
            l++;
        }
        o = e;
        opp.x = 2 * e.x - p.x, opp.y = 2 * e.y - p.y;
        for (int x : la[p.t]) {
            r = upper_bound(clan[x].begin(), clan[x].end(), opp, [&](const Pt &p, const Pt &q){ return cross(p, q) > 0;}) - clan[x].begin();
            mp[make_pair(x, p.t)] += seg[x].query(1, r + 1);
            r = upper_bound(clan1[x].begin(), clan1[x].end(), p, [&](const Pt &p, const Pt &q){ return cross(p, q) > 0;}) - clan1[x].begin();
            mp[make_pair(x, p.t)] += seg1[x].query(1, r + 1);
        }
    }
}

void solve() {
    cin >> n >> m;
    vector<Pt> pts(n);
    for (int i = 0; i < n; i++) {
        cin >> pts[i].x >> pts[i].y >> pts[i].t;
    }
    cin >> d.x >> d.y >> e.x >> e.y;
    if (d.x == e.x) {
        swap(d.x, d.y);
        swap(e.x, e.y);
        for (int i = 0; i < n; i++) swap(pts[i].x, pts[i].y);
    }
    if (d.x > e.x) swap(d.x, e.x), swap(d.y, e.y);
    ll c;
    o = d;
    for (int i = 0; i < n; i++) {
        c = cross(e, pts[i]);
        if (c > 0 || (c == 0 && pts[i].x > d.x)) side1.push_back(pts[i]);
        else side0.push_back(pts[i]);
    }
    cin >> q;
    ll f, g;
    vector<pair<ll, ll>> queries(q);
    for (int i = 0; i < q; i++) {
        cin >> f >> g;
        cnt[f]++;
        queries[i] = make_pair(f, g);
    }
    for (int i = 0; i < q; i++) {
        if (cnt[queries[i].first] * cnt[queries[i].first] < q) sm[queries[i].first].insert(queries[i].second);
        else la[queries[i].second].insert(queries[i].first);
    }
    ll max_sm = 0, max_la = 0;
    for (int i = 1; i <= m; i++) {
        max_sm = max(max_sm, (ll)sm[i].size());
    }
    handle_sm();
    handle_la();
    swap(d, e);
    swap(side0, side1);
    handle_sm();
    handle_la();
    for (auto it : queries) {
        cout << mp[it] << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    solve();
    return 0;
}

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