제출 #1149875

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149875		saywoo	별자리 2 (JOI14_constellation2)	C++20	100 / 100	2017 ms	197908 KiB

constellation2

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
using ll = long long int;
using Point = pair<ll, ll>; // 2차원 점 좌표 or 벡터로 사용

struct Line {
    int i, j;
    ll dx, dy;

    Line(int i, int j, Point a, Point b) : i(i), j(j), dx(a.x - b.x), dy(a.y - b.y) {}
    bool operator<(const Line &l) const { return ((dy * l.dx) == (dx * l.dy)) ? (tie(i, j) < tie(l.i, l.j)) : ((dy * l.dx) < (dx * l.dy)); }
    bool operator==(const Line &l) const { return (dy * l.dx) == (dx * l.dy); }
};

istream& operator>>(istream &in, Point &p) { in >> p.x >> p.y; return in; }
ostream& operator<<(ostream &out, Point &p) { out << p.x << " " << p.y; return out; }

Point operator+(Point p1, Point p2) { return {p1.x + p2.x, p1.y + p2.y}; }
Point operator-(Point p1, Point p2) { return {p1.x - p2.x, p1.y - p2.y}; }
ll operator*(Point p1, Point p2) { return p1.x * p2.x + p1.y * p2.y; } // 내적
ll operator/(Point p1, Point p2) { return p1.x * p2.y - p2.x * p1.y; }
// 외적 (x1, y1, 0), (x2, y2, 0)를 외적하면 (0, 0, z3) 꼴이 나오므로, z3를 반환

int Sign(ll v) { return (v > 0) - (v < 0); } // 양수: +1, 0: 0, 음수: -1
ll Dist(Point p1, Point p2) { return (p2 - p1) * (p2 - p1); } // 두 점 거리의 제곱

// -1 : 시계 방향, 0 : 직선, 1 : 반시계 방향
ll CCW(Point p1, Point p2, Point p3) { return Sign((p2 - p1) / (p3 - p1)); }

// 삼각형의 넓이 * 2를 반환
ll TriangleArea(Point p1, Point p2, Point p3) { return labs((p2 - p1) / (p3 - p1)); }

// 다각형의 넓이 * 2를 반환
ll PolygonArea(const vector<Point> &v) {
    int n = v.size();
    ll area = 0;
    for (int i = 1; i < n - 1; i++) area += TriangleArea(v[0], v[i], v[i+1]);
    return labs(area);
}

int st[3][10101];
int tmp;

ll xc[3], yc[3];

ll Query(int i, int l, int r, int s, int e, int p)
{
    if (e < l || r < s) return 0;
    else if (s <= l && r <= e) return st[i][p];
    else return Query(i, l, (l + r) / 2, s, e, p << 1) + Query(i, (l + r) / 2 + 1, r, s, e, p << 1 | 1);
}

int Query2(int l, int r) {
    l += tmp; r += tmp;
    int ans = 0;
    for (int i = 0; i < 3; i++) xc[i] = 0;
    for (; l < r; l >>= 1, r >>= 1) {
        for (int i = 0; i < 3; i++) {
            if (l & 1) xc[i] += st[i][l];
            if (r & 1) xc[i] += st[i][r-1];
        }
        if (r & 1) --r;
        if (l & 1) l++;
    }
    return ans;
}

void Update(int i, int p, int v)
{
    p = tmp + p;
    st[i][p] = v;
    while (p > 1) {
        p >>= 1;
        st[i][p] = st[i][p<<1] + st[i][p<<1|1];
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    vector<Point> P;
    vector<Line> L;
    int ind[3030], col[3030];
    map<Point, int> m;

    int n; cin >> n;
    for (tmp = 1; tmp < n; tmp *= 2) {}

    P.resize(n);
    for (int i = 0; i < n; i++) {
        int c;
        cin >> P[i] >> c; ind[i] = i;
        m[P[i]] = c;
    }
    sort(P.begin(), P.end());

    for (int i = 0; i < n; i++) {
        col[i] = m[P[i]];
        Update(col[i], i, 1);
        for (int j = i + 1; j < n; j++) {
            L.emplace_back(i, j, P[i], P[j]);
        }
    }
    sort(L.begin(), L.end());

    ll ans = 0;
    for (int i = 0; i < L.size(); i++) {
        int x = L[i].i; int y = L[i].j;
        Update(col[ind[x]], ind[x], 0); Update(col[ind[y]], ind[y], 0);
        Update(col[ind[x]], ind[y], 1); Update(col[ind[y]], ind[x], 1);
        swap(P[ind[x]], P[ind[y]]); swap(col[ind[x]], col[ind[y]]); swap(ind[x], ind[y]);
        if (ind[x] > ind[y]) swap(x, y);
        x = ind[x]; y = ind[y];
        ll xs = 0, ys = 0;

        Query2(0, x);
        if (col[ind[L[i].i]] == 0) xs = xc[1] * xc[2];
        if (col[ind[L[i].i]] == 1) xs = xc[0] * xc[2];
        if (col[ind[L[i].i]] == 2) xs = xc[0] * xc[1];
        Query2(y + 1, tmp + 1);
        if (col[ind[L[i].j]] == 0) ys = xc[1] * xc[2];
        if (col[ind[L[i].j]] == 1) ys = xc[0] * xc[2];
        if (col[ind[L[i].j]] == 2) ys = xc[0] * xc[1];
        
        ans += xs * ys;
    }
    
    cout << ans << '\n';

    return 0;
}

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