Submission #1127842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127842		PVSekhar	Dragon 2 (JOI17_dragon2)	C++20	0 / 100	17 ms	4872 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 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;
vector<ll> cnt(N, 0), lar(N, 0);
map<pair<ll, ll>, ll> mp;
vector<set<ll>> sm(N);
vector<Pt> side1, side0;

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;
}

void handle_sm_1() {
    int l = 0, r;
    Pt opp;
    vector<int> st(m + 1, 0), en(m + 1, 0);
    vector<vector<Pt>> clan(m + 1), clan1(m + 1);
    vector<Tree> seg(m + 1);
    for (auto p : side0) {
        clan[p.t].push_back(p);
        en[p.t]++;
    }
    for (int i = 1; i <= m; i++) {
        seg[i] = Tree(en[i] + 2, 1);
    }
    for (Pt p : side1) {
        clan1[p.t].push_back(p);
        o = d;
        while (l < side0.size() && cross(p, side0[l]) > 0) {
            seg[side0[l].t].update(++st[side0[l].t], 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 = lower_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 = lower_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)] += r;
        }
    }
}

void handle_sm_0() {
    int l = 0, r;
    Pt opp;
    vector<int> st(m + 1, 0), en(m + 1, 0);
    vector<vector<Pt>> clan(m + 1), clan1(m + 1);
    vector<Tree> seg(m + 1);
    for (auto p : side1) {
        clan[p.t].push_back(p);
        en[p.t]++;
    }
    for (int i = 1; i <= m; i++) {
        seg[i] = Tree(en[i] + 2, 1);
    }
    for (Pt p : side0) {
        clan1[p.t].push_back(p);
        o = e;
        while (l < side1.size() && cross(p, side1[l]) > 0) {
            seg[side1[l].t].update(++st[side1[l].t], 0);
            l++;
        }
        o = d;
        opp.x = 2 * d.x - p.x;
        opp.y = 2 * d.y - p.y;
        for (int x : sm[p.t]) {
            r = lower_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 = lower_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)] += r;
        }
    }
}

void handle_sm() {
    handle_sm_1();
    handle_sm_0();
}

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, e);
    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]++, cnt[g]++;
        queries[i] = make_pair(f, g);
    }
    for (int i = 0; i < q; i++) {
        sm[queries[i].first].insert(queries[i].second);
    }
    o = d, sort(side1.begin(),side1.end());
    o = e, sort(side0.begin(),side0.end());
    handle_sm();
    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: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40