oj.uz

Submission #931577

# Submission time Handle Problem Language Result Execution time Memory
931577 2024-02-22T05:52:02 Z Perl32 Bulldozer (JOI17_bulldozer) C++
25 / 100
 2000 ms 213096 KB 
//I wrote this code 4 u <3
#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;
    }
};

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;
    map<Frac, vector<pair<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[{dy, dx}].emplace_back(i, j);
            else aboba[{dy, dx}].emplace_back(j, i);
            slope.emplace_back(dy, dx);
        }
    }
    sort(slope.begin(), slope.end());
    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 (auto nw : slope) {
        ans = max(ans, st.get().mx);
        sort(aboba[nw].begin(), aboba[nw].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];
        });
        for (auto [i, j] : aboba[nw]) {
            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: In function 'int main(int32_t, char**)':
bulldozer.cpp:138:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  138 |         for (auto [i, j] : aboba[nw]) {
      |                   ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 724 KB Output is correct
2 Correct 598 ms 720 KB Output is correct
3 Correct 597 ms 600 KB Output is correct
4 Correct 618 ms 720 KB Output is correct
5 Correct 601 ms 720 KB Output is correct
6 Correct 598 ms 724 KB Output is correct
7 Correct 602 ms 860 KB Output is correct
8 Correct 602 ms 724 KB Output is correct
9 Correct 603 ms 740 KB Output is correct
10 Correct 601 ms 720 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 1 ms 344 KB Output is correct
15 Correct 0 ms 800 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 860 KB Output is correct
2 Correct 4 ms 1092 KB Output is correct
3 Correct 4 ms 860 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 5 ms 860 KB Output is correct
7 Correct 4 ms 860 KB Output is correct
8 Correct 4 ms 860 KB Output is correct
9 Correct 4 ms 860 KB Output is correct
10 Correct 4 ms 856 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 4 ms 1028 KB Output is correct
22 Correct 4 ms 860 KB Output is correct
23 Correct 4 ms 1024 KB Output is correct
24 Correct 4 ms 904 KB Output is correct
25 Correct 4 ms 860 KB Output is correct
26 Correct 4 ms 860 KB Output is correct
27 Correct 4 ms 860 KB Output is correct
28 Correct 4 ms 856 KB Output is correct
29 Correct 4 ms 860 KB Output is correct
30 Correct 4 ms 1096 KB Output is correct
31 Correct 4 ms 860 KB Output is correct
32 Correct 4 ms 1036 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 860 KB Output is correct
2 Correct 4 ms 1092 KB Output is correct
3 Correct 4 ms 860 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 5 ms 860 KB Output is correct
7 Correct 4 ms 860 KB Output is correct
8 Correct 4 ms 860 KB Output is correct
9 Correct 4 ms 860 KB Output is correct
10 Correct 4 ms 856 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 4 ms 1028 KB Output is correct
22 Correct 4 ms 860 KB Output is correct
23 Correct 4 ms 1024 KB Output is correct
24 Correct 4 ms 904 KB Output is correct
25 Correct 4 ms 860 KB Output is correct
26 Correct 4 ms 860 KB Output is correct
27 Correct 4 ms 860 KB Output is correct
28 Correct 4 ms 856 KB Output is correct
29 Correct 4 ms 860 KB Output is correct
30 Correct 4 ms 1096 KB Output is correct
31 Correct 4 ms 860 KB Output is correct
32 Correct 4 ms 1036 KB Output is correct
33 Execution timed out 2054 ms 213096 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 860 KB Output is correct
2 Correct 4 ms 1092 KB Output is correct
3 Correct 4 ms 860 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 5 ms 860 KB Output is correct
7 Correct 4 ms 860 KB Output is correct
8 Correct 4 ms 860 KB Output is correct
9 Correct 4 ms 860 KB Output is correct
10 Correct 4 ms 856 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 4 ms 1028 KB Output is correct
22 Correct 4 ms 860 KB Output is correct
23 Correct 4 ms 1024 KB Output is correct
24 Correct 4 ms 904 KB Output is correct
25 Correct 4 ms 860 KB Output is correct
26 Correct 4 ms 860 KB Output is correct
27 Correct 4 ms 860 KB Output is correct
28 Correct 4 ms 856 KB Output is correct
29 Correct 4 ms 860 KB Output is correct
30 Correct 4 ms 1096 KB Output is correct
31 Correct 4 ms 860 KB Output is correct
32 Correct 4 ms 1036 KB Output is correct
33 Execution timed out 2054 ms 213096 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 724 KB Output is correct
2 Correct 598 ms 720 KB Output is correct
3 Correct 597 ms 600 KB Output is correct
4 Correct 618 ms 720 KB Output is correct
5 Correct 601 ms 720 KB Output is correct
6 Correct 598 ms 724 KB Output is correct
7 Correct 602 ms 860 KB Output is correct
8 Correct 602 ms 724 KB Output is correct
9 Correct 603 ms 740 KB Output is correct
10 Correct 601 ms 720 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 1 ms 344 KB Output is correct
15 Correct 0 ms 800 KB Output is correct
16 Correct 4 ms 860 KB Output is correct
17 Correct 4 ms 1092 KB Output is correct
18 Correct 4 ms 860 KB Output is correct
19 Correct 4 ms 860 KB Output is correct
20 Correct 4 ms 860 KB Output is correct
21 Correct 5 ms 860 KB Output is correct
22 Correct 4 ms 860 KB Output is correct
23 Correct 4 ms 860 KB Output is correct
24 Correct 4 ms 860 KB Output is correct
25 Correct 4 ms 856 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 4 ms 1028 KB Output is correct
37 Correct 4 ms 860 KB Output is correct
38 Correct 4 ms 1024 KB Output is correct
39 Correct 4 ms 904 KB Output is correct
40 Correct 4 ms 860 KB Output is correct
41 Correct 4 ms 860 KB Output is correct
42 Correct 4 ms 860 KB Output is correct
43 Correct 4 ms 856 KB Output is correct
44 Correct 4 ms 860 KB Output is correct
45 Correct 4 ms 1096 KB Output is correct
46 Correct 4 ms 860 KB Output is correct
47 Correct 4 ms 1036 KB Output is correct
48 Execution timed out 2054 ms 213096 KB Time limit exceeded
49 Halted 0 ms 0 KB -