Submission #1249333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249333		1ncogn1to	Dragon 2 (JOI17_dragon2)	C++20	100 / 100	544 ms	11844 KiB

dragon2

#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <deque>
#include <string>
#include <string.h>
#include <vector>
#include <set>
#include <map>
#include <stdlib.h>
#include <complex>
using namespace std;

// maksymalna liczba smoków, zapytań, bitów do fenwick (BS -> 2^15=32768)
const int MN = 30000, MQ = 100000, BS = 15, RQ = 300;

typedef complex<long long> point;  // punkt jako liczba zespolona (x + yi)

// Funkcja obliczająca orientację (2D cross product) P1 x P2
long long op(point P1, point P2) {
    // conj(P1)*P2 daje (x1 - y1 i)*(x2 + y2 i) = ..., wyciągamy część uroj.
    return imag(conj(P1) * P2);
}

namespace std {
    // Nadpisujemy operator < dla punktów, tak aby sortować je według kąta
    bool operator<(point P1, point P2) {
        // P1 < P2 jeśli P1 leży bardziej "w lewo" niż P2, czyli op(P1,P2)>0
        return op(P1, P2) > 0;
    }
}

// Fenwick Tree (Binary Indexed Tree) na sumy typu T
template<class T>
class sumBIT {
private:
    T *bit;
    int S;
public:
    sumBIT(int S0) {
        S = S0;
        // alokacja tablicy size = 2^S
        bit = (T *)calloc(sizeof(T), 1 << S);
    }
    
    // dodaj k do pozycji i
    void add(int i, T k) {
        int p = i + 1;
        while (p < (1 << S)) {
            bit[p] += k;
            p += p & -p;
        }
    }
    
    // sum prefix sum od 1 do p
    T sum(int p) {
        T ret = 0;
        while (p > 0) {
            ret += bit[p];
            p -= p & -p;
        }
        return ret;
    }
    
    // suma w przedziale [a, b)
    T rag(int a, int b) {
        return sum(b) - sum(a);
    }
};

int main() {
    int n, m;
    // n = liczba smoków, m = liczba plemion
    scanf("%d%d", &n, &m);
    
    static point P[MN];   // pozycje smoków
    static int C[MN];     // przynależność plemienna (0-index)
    for (int i = 0; i < n; i++) {
        long long x, y;
        scanf("%lld%lld%d", &x, &y, C + i);
        P[i] = point(x, y);
        C[i]--;  // odjęcie 1 dla 0-based
    }
    
    // Wczytanie wiosek
    long long d1, e1, d2, e2;
    scanf("%lld%lld%lld%lld", &d1, &e1, &d2, &e2);
    point X = point(d1, e1), Y = point(d2, e2);

    // F[i] = true jeśli P[i] leży po lewej stronie wektora X->Y
    static bool F[MN];
    for (int i = 0; i < n; i++) {
        F[i] = (op(Y - X, P[i] - X) > 0);
    }

    // A[i] = wektor od Y do P[i] (jeśli F[i]) lub od P[i] do Y
    static point A[MN];
    // AA = pary (plemię, wektor) do sortowania globalnego
    static pair<int, point> AA[MN];
    for (int i = 0; i < n; i++) {
        A[i] = (F[i] ? P[i] - Y : Y - P[i]);
        AA[i] = make_pair(C[i], A[i]);
    }
    // Sortujemy wszystkie pary po plemieniu, a w ramach plemienia po kącie
    sort(AA, AA + n);

    // D[i] = indeks pary (C[i], A[i]) w posortowanym AA
    static int D[MN];
    for (int i = 0; i < n; i++) {
        D[i] = lower_bound(AA, AA + n, make_pair(C[i], A[i])) - AA;
    }

    // T[k] = początek przedziału dla plemienia k (w AA)
    static int T[MN + 1];
    for (int i = 0; i <= m; i++) {
        // szukamy pierwszego elementu >= (i, dowolny wektor jak Y-X)
        T[i] = lower_bound(AA, AA + n, make_pair(i, Y - X)) - AA;
    }

    // Pr = wektory od X do P[i] (lub odwrotnie), wraz z indeksem i, posortowane rosnąco
    static pair<point, int> Pr[MN];
    for (int i = 0; i < n; i++) {
        Pr[i] = make_pair(F[i] ? P[i] - X : X - P[i], i);
    }
    sort(Pr, Pr + n);

    int Q;
    scanf("%d", &Q);
    static int as[MQ], bs[MQ];   // zapytania: as[j] atakuje bs[j]
    for (int i = 0; i < Q; i++) {
        scanf("%d%d", as + i, bs + i);
        as[i]--;
        bs[i]--;
    }

    // V[a] = lista plemion b, które a atakuje (dla "małych" plemion)
    static vector<int> V[MN], VN[MN];
    for (int i = 0; i < Q; i++) {
        V[as[i]].push_back(bs[i]);
        VN[as[i]].push_back(i);  // numer zapytania
    }
    // V2[b] = lista plemion a ("dużych"), które atakują b (odwrócenie fazy II)
    static vector<int> V2[MN], VN2[MN];
    for (int i = 0; i < Q; i++) {
        if (V[as[i]].size() >= RQ) {
            // jeśli a jest duże, przerzucamy do V2 b
            V2[bs[i]].push_back(as[i]);
            VN2[bs[i]].push_back(i);
        }
    }

    static long long ans[MQ] = {0};  // odpowiedzi

    // --- Faza I: małe plemiona ---
    sumBIT<int> seg0(BS), seg1(BS);
    // Na początku wstawiamy do seg1 wszystkie smoki po prawej
    for (int i = 0; i < n; i++) {
        if (!F[i]) seg1.add(D[i], 1);
    }
    // Sweep po kątowej kolejności względem X
    for (int t = 0; t < n; t++) {
        int i = Pr[t].second;
        int a = C[i];
        if (F[i]) {
            // gdy smok jest po lewej, obsługujemy małe zapytania z V[a]
            if (V[a].size() < RQ) {
                for (int k = 0; k < (int)V[a].size(); k++) {
                    int b = V[a][k], l = VN[a][k];
                    int L = lower_bound(AA, AA + n, make_pair(b, A[i])) - AA;
                    // dodajemy liczbę smoków plemienia b, które były już po lewej (seg0) lub po prawej (seg1)
                    ans[l] += seg0.rag(L, T[b+1]) + seg1.rag(T[b], L);
                }
            }
            seg0.add(D[i], 1);  // przenosimy tego smoka do seg0
        } else {
            // analogicznie, gdy smok po prawej
            if (V[a].size() < RQ) {
                for (int k = 0; k < (int)V[a].size(); k++) {
                    int b = V[a][k], l = VN[a][k];
                    int L = lower_bound(AA, AA + n, make_pair(b, A[i])) - AA;
                    ans[l] += seg0.rag(L, T[b+1]) + seg1.rag(T[b], L);
                }
            }
            seg1.add(D[i], -1);  // usuwamy smoka z prawej
        }
    }

    // --- Faza II: duże plemiona ---
    sumBIT<int> seg2(BS), seg3(BS);
    // seg2 trzyma wszystkie smoki jeszcze nieprzetworzone
    for (int i = 0; i < n; i++) {
        seg2.add(D[i], 1);
    }
    for (int t = 0; t < n; t++) {
        int i = Pr[t].second;
        int b = C[i];
        if (F[i]) {
            // dla każdego dużego a atakującego b
            for (int k = 0; k < (int)V2[b].size(); k++) {
                int a = V2[b][k], l = VN2[b][k];
                int L = lower_bound(AA, AA + n, make_pair(a, A[i])) - AA;
                ans[l] += seg2.rag(T[a], L);
            }
            seg2.add(D[i], -1);
            seg3.add(D[i], 1);
        } else {
            for (int k = 0; k < (int)V2[b].size(); k++) {
                int a = V2[b][k], l = VN2[b][k];
                int L = lower_bound(AA, AA + n, make_pair(a, A[i])) - AA;
                ans[l] += seg3.rag(L, T[a+1]);
            }
            seg2.add(D[i], -1);
            seg3.add(D[i], 1);
        }
    }

    // Wypisanie wyników
    for (int t = 0; t < Q; t++) {
        printf("%lld\n", ans[t]);
    }
    return 0;
}

Compilation message (stderr)

dragon2.cpp: In function 'int main()':
dragon2.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
dragon2.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         scanf("%lld%lld%d", &x, &y, C + i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     scanf("%lld%lld%lld%lld", &d1, &e1, &d2, &e2);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:129:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |     scanf("%d", &Q);
      |     ~~~~~^~~~~~~~~~
dragon2.cpp:132:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         scanf("%d%d", as + i, bs + i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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