Submission #1128134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128134		PVSekhar	Dragon 2 (JOI17_dragon2)	C++20	60 / 100	4088 ms	31492 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 __int128_t
// const ll MOD = 998244353;
const ll MOD = 1e9 + 7;
const ll N = 3e4 + 2;
const ll Q = 1e5 + 2;

__int128 read() {
    __int128 x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
void print(__int128 x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
bool cmp(__int128 x, __int128 y) { return x > y; }

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

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

void handle_sm_1() {
    int l = 0, r;
    Pt opp;
    // vector<int> sz(m + 1, 0);
    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++) {
        // sz[i] = clan1[i].size();
        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 solve() {
    n = read();
    m = read();
    vector<Pt> pts(n);
    for (int i = 0; i < n; i++) {
        pts[i].x = read(), pts[i].y = read(), pts[i].t = read();
    }
    d.x = read(), d.y = read(), e.x = read(), e.y = read();
    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]);
    }
    q = read();
    ll f, g;
    vector<pair<ll, ll>> queries(q);
    for (int i = 0; i < q; i++) {
        f = read(), g = read();
        queries[i] = make_pair(f, g);
    }
    for (int i = 0; i < q; i++) {
        sm[queries[i].first].insert(queries[i].second);
    }
    handle_sm_1();
    swap(d, e);
    swap(side0, side1);
    handle_sm_1();
    for (auto it : queries) {
        print(mp[it]), putchar('\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: 0 / 40