oj.uz

답안 #1072375

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1072375 2024-08-23T17:38:39 Z wapas 별자리 2 (JOI14_constellation2) C++17
55 / 100
 1499 ms 262144 KB 
// code by wapas
# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

/*
  segtree code by : https://github.com/atcoder/ac-library/blob/master/atcoder/segtree.hpp
  how to use : https://github.com/atcoder/ac-library/blob/master/document_en/segtree.md
*/
#if __cplusplus < 202002L
unsigned int bit_ceil(unsigned int n) {
    unsigned int x = 1;
    while (x < (unsigned int)(n)) x *= 2;
    return x;
}
#endif

int countr_zero(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

template <class S, auto op, auto e> struct segtree {
    static_assert(is_convertible_v<decltype(op), function<S(S, S)>>,
                  "op must work as S(S, S)");
    static_assert(is_convertible_v<decltype(e), function<S()>>,
                  "e must work as S()");
  
  public:
    segtree() : segtree(0) {}
    explicit segtree(int n) : segtree(vector<S>(n, e())) {}
    explicit segtree(const vector<S>& v) : _n(int(v.size())) {
        size = (int) bit_ceil((unsigned int)(_n));
        log = countr_zero((unsigned int)size);
        d = vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) const {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() const { return d[1]; }

    template <bool (*f)(S)> int max_right(int l) const {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) const {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r) const {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) const {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

ll op(ll a, ll b) {
    return a + b;
}

ll e() {
    return 0;
}

// Bulldozer code by justiceHui : https://justicehui.github.io/hard-algorithm/2022/03/30/rotate-sweep-line/
struct point {
    ll x, y, z;
    bool operator < (const point &p) const {
        return tie(x, y) < tie(p.x, p.y);
    }
    bool operator == (const point &p) const {
        return tie(x, y) == tie(p.x, p.y);
    }
};

struct line {
    ll i, j, dx, dy;
    line(int i, int j, const point &pi, const point &pj) : i(i), j(j), dx(pj.x - pi.x), dy(pj.y - pi.y) {}
    bool operator < (const line &l) const {
        ll le = dy * l.dx, ri = l.dy * dx;
        return tie(le, i, j) < tie(ri, l.i, l.j);
    }
    bool operator == (const line &l) const {
        return dy * l.dx == l.dy * dx;
    }
};

point vec(point a, point b) {
    return { b.x - a.x, b.y - a.y };
}

ll ccw(point a, point b, point c) {
    point u = vec(a, b);
    point v = vec(b, c);
    return u.x * v.y - u.y * v.x;
}

void solution(int t) {
    int N; cin >> N;
    vector<point> prr(N);
    for (int i = 0; i < N; i++) cin >> prr[i].x >> prr[i].y >> prr[i].z;
    sort(prr.begin(), prr.end());
    vector<segtree<ll, op, e>> st(3, segtree<ll, op, e>(N));
    for (int i = 0; i < N; i++) st[prr[i].z].set(i, 1);
    vector<int> pos(N);
    for (int i = 0; i < N; i++) pos[i] = i;
    vector<line> lrr;
    for (int i = 0; i < N - 1; i++) for (int j = i + 1; j < N; j++) lrr.emplace_back(i, j, prr[i], prr[j]);
    sort(lrr.begin(), lrr.end());
    ll ans = 0;
    for (int i = 0, j = 0; i < lrr.size(); i = j) {
        while (j < lrr.size() && lrr[i] == lrr[j]) j++;
        for (int k = i; k < j; k++) {
            int u = lrr[k].i, v = lrr[k].j;
            st[prr[pos[u]].z].set(pos[u], 0);
            st[prr[pos[v]].z].set(pos[v], 0);
            swap(pos[u], pos[v]);
            swap(prr[pos[u]], prr[pos[v]]);
            st[prr[pos[u]].z].set(pos[u], 1);
            st[prr[pos[v]].z].set(pos[v], 1);
            if (pos[u] > pos[v]) swap(u, v);
            ll L = 1;
            for (int i = 0; i < 3; i++) if (i != prr[pos[u]].z) L *= st[i].prod(0, pos[u]);
            ll R = 1;
            for (int i = 0; i < 3; i++) if (i != prr[pos[v]].z) R *= st[i].prod(pos[v], N);;
            ans += L * R;
        }
    }
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // int T; cin >> T;
    int T = 1;
    for (int t = 0; t < T; t++) {
        solution(t);
    }
}

Compilation message

constellation2.cpp: In function 'void solution(int)':
constellation2.cpp:197:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |     for (int i = 0, j = 0; i < lrr.size(); i = j) {
      |                            ~~^~~~~~~~~~~~
constellation2.cpp:198:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |         while (j < lrr.size() && lrr[i] == lrr[j]) j++;
      |                ~~^~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 4 ms 992 KB Output is correct
5 Correct 6 ms 1500 KB Output is correct
6 Correct 18 ms 2520 KB Output is correct
7 Correct 15 ms 2524 KB Output is correct
8 Correct 14 ms 2524 KB Output is correct
9 Correct 15 ms 2524 KB Output is correct
10 Correct 10 ms 1500 KB Output is correct
11 Correct 15 ms 2524 KB Output is correct
12 Correct 15 ms 2524 KB Output is correct

Subtask #3
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 17000 KB Output is correct
2 Correct 173 ms 17092 KB Output is correct
3 Correct 206 ms 17092 KB Output is correct
4 Correct 202 ms 17088 KB Output is correct
5 Correct 542 ms 66416 KB Output is correct
6 Correct 895 ms 66456 KB Output is correct
7 Correct 1499 ms 132144 KB Output is correct
8 Runtime error 148 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -