oj.uz

답안 #931848

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
931848 2024-02-22T12:27:31 Z Perl32 Bulldozer (JOI17_bulldozer) C++14
25 / 100
 2000 ms 188588 KB 
//I wrote this code 4 u <3
#  pragma GCC target ("avx2")
#  pragma GCC optimization ("O3")
#  pragma GCC optimization ("unroint-loops")
#  pragma GCC optimize("Ofast,no-stack-protector")
#  pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#  pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

struct Point {
    ll x, y, w;

    Point() {}
    Point(ll x, ll y, ll w) : x(x), y(y), w(w) {}

    bool operator<(const Point& oth) const {
        return x < oth.x || (x == oth.x && y > oth.y);
    }

    friend istream &operator>>(istream& in, Point& p) {
        in >> p.x >> p.y >> p.w;
        return in;
    }
};

struct Frac {
    ll p, q;

    Frac() {}
    Frac(ll _p, ll _q) : p(_p), q(_q) {}

    bool operator<(const Frac& oth) const {
        return 1ll * p * oth.q < 1ll * oth.p * q;
    }

    bool operator==(const Frac& oth) {
        return p * oth.q == oth.p * q;
    }
};

struct Info {
    ll pref = 0, suf = 0, all = 0, mx = 0;

    Info() {}
    Info(ll v) : pref(max(0ll, v)), suf(max(0ll, v)), all(v), mx(max(0ll, v)) {}
};

Info operator+(const Info& a, const Info& b) {
    Info ret;
    ret.all = a.all + b.all;
    ret.pref = max(a.pref, a.all + b.pref);
    ret.suf = max(b.suf, a.suf + b.all);
    ret.mx = max({ret.pref, ret.suf, a.mx, b.mx, a.suf + b.pref});
    return ret;
}

template<class Info, class Merge = plus<Info>>
struct SegTree {
    vector<Info> t;
    const Merge merge;
    int sz;

    SegTree(int n) : merge(Merge()) {
        sz = 1;
        while (sz < n) sz <<= 1;
        t.resize(sz << 1);
    }

    SegTree(vector<ll>& a) : merge(Merge()) {
        sz = 1;
        while (sz < (int) a.size()) sz <<= 1;
        t.resize(sz << 1);
        for (int i = 0; i < (int) a.size(); ++i) {
            t[i + sz] = a[i];
        }
        for (int i = sz - 1; i; --i) {
            pull(i);
        }
    }

    void pull(int x) {
        t[x] = merge(t[x << 1], t[x << 1 | 1]);
    }

    void upd(int i, Info v) {
        i += sz;
        t[i] = v;
        i >>= 1;
        while (i) {
            pull(i);
            i >>= 1;
        }
    }

    Info get() { return t[1]; }
};

signed main(int32_t argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<Point> kek(n);
    for (int i = 0; i < n; ++i) {
        cin >> kek[i];
    }
    vector<Frac> slope;
    vector<tuple<Frac, int, int>> aboba;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int dx = kek[i].x - kek[j].x, dy = kek[i].y - kek[j].y, sign = 1;
            if (dx < 0) dx *= -1, sign *= -1;
            if (dy < 0) dy *= -1, sign *= -1;
            int g = __gcd(dx, dy);
            dx /= g, dy /= g;
            if (dx) dy *= sign;
            if (kek[i] < kek[j]) aboba.push_back({{dy, dx}, i, j});
            else  aboba.push_back({{dy, dx}, j, i});
            slope.emplace_back(dy, dx);
        }
    }
    sort(slope.begin(), slope.end());
    slope.resize(unique(slope.begin(), slope.end()) - slope.begin());
    vector<vector<pair<int, int>>> flex(slope.size());
    for (auto [f, i, j] : aboba) {
        flex[lower_bound(slope.begin(), slope.end(), f) - slope.begin()].emplace_back(i, j);
    }
    for (auto& x : flex) {
        sort(x.begin(), x.end(), [&](const pair<int, int>& i, const pair<int, int>& j) {
            if (i.first == j.first) return kek[i.second] < kek[j.second];
            return kek[i.first] < kek[j.first];
        });
    }
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        return kek[i] < kek[j];
    });
    vector<int> pos(n);
    SegTree<Info> st(n);
    for (int i = 0; i < n; ++i) { pos[ord[i]] = i, st.upd(i, kek[ord[i]].w); }
    ll ans = 0;
    for (int id = 0; id < (int) slope.size(); ++id) {
        ans = max(ans, st.get().mx);
        for (auto [i, j] : flex[id]) {
            if (pos[i] < pos[j]) {
                st.upd(pos[i], kek[ord[pos[j]]].w);
                st.upd(pos[j], kek[ord[pos[i]]].w);
                swap(ord[pos[i]], ord[pos[j]]);
                swap(pos[i], pos[j]);
            }
        }
    }
    cout << max(ans, st.get().mx);
}

/*

 */

Compilation message

bulldozer.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #  pragma GCC optimization ("O3")
      | 
bulldozer.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #  pragma GCC optimization ("unroint-loops")
      | 
bulldozer.cpp: In function 'int main(int32_t, char**)':
bulldozer.cpp:135:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  135 |     for (auto [f, i, j] : aboba) {
      |               ^
bulldozer.cpp:155:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  155 |         for (auto [i, j] : flex[id]) {
      |                   ^

Subtask #1
5.0 / 5.0

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

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 828 KB Output is correct
2 Correct 3 ms 824 KB Output is correct
3 Correct 3 ms 828 KB Output is correct
4 Correct 3 ms 828 KB Output is correct
5 Correct 3 ms 824 KB Output is correct
6 Correct 3 ms 880 KB Output is correct
7 Correct 3 ms 824 KB Output is correct
8 Correct 3 ms 828 KB Output is correct
9 Correct 3 ms 828 KB Output is correct
10 Correct 3 ms 824 KB Output is correct
11 Correct 0 ms 352 KB Output is correct
12 Correct 0 ms 352 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 404 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 856 KB Output is correct
21 Correct 3 ms 824 KB Output is correct
22 Correct 3 ms 824 KB Output is correct
23 Correct 3 ms 824 KB Output is correct
24 Correct 3 ms 824 KB Output is correct
25 Correct 3 ms 824 KB Output is correct
26 Correct 3 ms 824 KB Output is correct
27 Correct 3 ms 824 KB Output is correct
28 Correct 3 ms 824 KB Output is correct
29 Correct 3 ms 824 KB Output is correct
30 Correct 3 ms 824 KB Output is correct
31 Correct 3 ms 996 KB Output is correct
32 Correct 3 ms 820 KB Output is correct

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 828 KB Output is correct
2 Correct 3 ms 824 KB Output is correct
3 Correct 3 ms 828 KB Output is correct
4 Correct 3 ms 828 KB Output is correct
5 Correct 3 ms 824 KB Output is correct
6 Correct 3 ms 880 KB Output is correct
7 Correct 3 ms 824 KB Output is correct
8 Correct 3 ms 828 KB Output is correct
9 Correct 3 ms 828 KB Output is correct
10 Correct 3 ms 824 KB Output is correct
11 Correct 0 ms 352 KB Output is correct
12 Correct 0 ms 352 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 404 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 856 KB Output is correct
21 Correct 3 ms 824 KB Output is correct
22 Correct 3 ms 824 KB Output is correct
23 Correct 3 ms 824 KB Output is correct
24 Correct 3 ms 824 KB Output is correct
25 Correct 3 ms 824 KB Output is correct
26 Correct 3 ms 824 KB Output is correct
27 Correct 3 ms 824 KB Output is correct
28 Correct 3 ms 824 KB Output is correct
29 Correct 3 ms 824 KB Output is correct
30 Correct 3 ms 824 KB Output is correct
31 Correct 3 ms 996 KB Output is correct
32 Correct 3 ms 820 KB Output is correct
33 Execution timed out 2067 ms 188588 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 828 KB Output is correct
2 Correct 3 ms 824 KB Output is correct
3 Correct 3 ms 828 KB Output is correct
4 Correct 3 ms 828 KB Output is correct
5 Correct 3 ms 824 KB Output is correct
6 Correct 3 ms 880 KB Output is correct
7 Correct 3 ms 824 KB Output is correct
8 Correct 3 ms 828 KB Output is correct
9 Correct 3 ms 828 KB Output is correct
10 Correct 3 ms 824 KB Output is correct
11 Correct 0 ms 352 KB Output is correct
12 Correct 0 ms 352 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 404 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 856 KB Output is correct
21 Correct 3 ms 824 KB Output is correct
22 Correct 3 ms 824 KB Output is correct
23 Correct 3 ms 824 KB Output is correct
24 Correct 3 ms 824 KB Output is correct
25 Correct 3 ms 824 KB Output is correct
26 Correct 3 ms 824 KB Output is correct
27 Correct 3 ms 824 KB Output is correct
28 Correct 3 ms 824 KB Output is correct
29 Correct 3 ms 824 KB Output is correct
30 Correct 3 ms 824 KB Output is correct
31 Correct 3 ms 996 KB Output is correct
32 Correct 3 ms 820 KB Output is correct
33 Execution timed out 2067 ms 188588 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 820 KB Output is correct
2 Correct 3 ms 824 KB Output is correct
3 Correct 3 ms 824 KB Output is correct
4 Correct 3 ms 824 KB Output is correct
5 Correct 3 ms 824 KB Output is correct
6 Correct 3 ms 828 KB Output is correct
7 Correct 3 ms 828 KB Output is correct
8 Correct 3 ms 828 KB Output is correct
9 Correct 3 ms 828 KB Output is correct
10 Correct 3 ms 824 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 352 KB Output is correct
16 Correct 4 ms 828 KB Output is correct
17 Correct 3 ms 824 KB Output is correct
18 Correct 3 ms 828 KB Output is correct
19 Correct 3 ms 828 KB Output is correct
20 Correct 3 ms 824 KB Output is correct
21 Correct 3 ms 880 KB Output is correct
22 Correct 3 ms 824 KB Output is correct
23 Correct 3 ms 828 KB Output is correct
24 Correct 3 ms 828 KB Output is correct
25 Correct 3 ms 824 KB Output is correct
26 Correct 0 ms 352 KB Output is correct
27 Correct 0 ms 352 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 404 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 1 ms 856 KB Output is correct
36 Correct 3 ms 824 KB Output is correct
37 Correct 3 ms 824 KB Output is correct
38 Correct 3 ms 824 KB Output is correct
39 Correct 3 ms 824 KB Output is correct
40 Correct 3 ms 824 KB Output is correct
41 Correct 3 ms 824 KB Output is correct
42 Correct 3 ms 824 KB Output is correct
43 Correct 3 ms 824 KB Output is correct
44 Correct 3 ms 824 KB Output is correct
45 Correct 3 ms 824 KB Output is correct
46 Correct 3 ms 996 KB Output is correct
47 Correct 3 ms 820 KB Output is correct
48 Execution timed out 2067 ms 188588 KB Time limit exceeded
49 Halted 0 ms 0 KB -