oj.uz

Submission #161722

# Submission time Handle Problem Language Result Execution time Memory
161722 2019-11-04T09:08:10 Z darkkcyan Bulldozer (JOI17_bulldozer) C++14
25 / 100
 2000 ms 116312 KB 
#include <bits/stdc++.h>
using namespace std;
using namespace std::placeholders;

#define llong long long 
#define xx first
#define yy second
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define all(x) x.begin(), x.end()
#define sgn(x) ((x) < 0 ? -1 : (x) > 0)
#define clog if (0) cerr
// #define rand __rand
// mt19937 rng(chrono::system_clock::now().time_since_epoch().count());  // or mt19937_64
// template<class T = int> T rand(T range = numeric_limits<T>::max()) {
    // return (T)(rng() % range);
// }

struct itnode {
    llong max_sum_subarr, max_left_sum, max_right_sum, sum;
    itnode *lchild, *rchild;
    int l, r;  // [l; r)

    itnode(int l_, int r_, function<llong(int)> getitem)
        : lchild(0), rchild(0), l(l_), r(r_)
    {
        if (l + 1 == r) {
            assign(getitem(l));
        }
        if (l + 1 >= r) return ;
        int mid = (l + r) / 2;
        lchild = new itnode(l, mid, getitem);
        rchild = new itnode(mid, r, getitem);
        merge();
    }

    ~itnode() {
        if (!lchild) return ;
        delete lchild; delete rchild;
    }

    void assign(llong val) {
        sum = val;
        max_sum_subarr = sum;
        max_right_sum = max_left_sum = max(sum, 0ll);
    }

    void merge() {
        if (!lchild || !rchild) return ;
        sum = lchild->sum + rchild->sum;
        max_sum_subarr = max({lchild->max_sum_subarr, rchild->max_sum_subarr, lchild->max_right_sum + rchild->max_left_sum});
        max_left_sum = max(lchild->max_left_sum, lchild->sum + rchild->max_left_sum);
        max_right_sum = max(rchild->max_right_sum, rchild->sum + lchild->max_right_sum);
    }

    void inc(int pos, llong val) {
        if (pos < l or pos >= r) return ;
        if (l + 1 == r) {
            assign(sum + val);
            return ;
        }

        lchild->inc(pos, val);
        rchild->inc(pos, val);
        merge();
    }

    void dolog() {
        if (!lchild) {
            clog << setw(4) << sum << ' ';
        } else {
            lchild->dolog();
            rchild->dolog();
        }
    }
};

struct line {
    llong a, b, c;   // ax + by + c = 0
    line(llong a_ = 0, llong b_ = 0, llong c_ = 0) : a(a_), b(b_), c(c_) {}

    line& norm() {
        llong g = __gcd(a, b);
        g = __gcd(g, c);
        a /= g;
        b /= g;
        c /= g;

        // the normal will point almost the same way as Oy
        // also the line a == b == 0 does not "really" exist, no need to handle it.
        if (b < 0 || (b == 0 and a < 0)) {
            a = -a; b = -b; c = -c;
        }
        return *this;
    }

    template<class Point>
    static line through_points(Point const& u, Point const& v) {
        return line(
            u.y - v.y,
            - u.x + v.x,
            u.x * v.y - u.y * v.x
        ).norm();
    }
};

bool operator == (const line& lhs, const line& rhs) {
    return lhs.a == rhs.a and lhs.b == rhs.b and lhs.c == rhs.c;
}

#define maxn 2020
struct spot {
    llong x, y, cost;
    int pos;
    spot(llong x_ = 0, llong y_ = 0, llong v = 0) : x(x_), y(y_), cost(v), pos(0) {}
};

struct cmp_line {
    bool operator()(const line& lhs, const line& rhs) const {
        int cross = sgn(lhs.a * rhs.b - lhs.b * rhs.a);
        if (cross == 0) return lhs.c < rhs.c;
        return cross > 0;
    }
};

int n;
spot a[maxn];

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    rep(i, n) cin >> a[i].x >> a[i].y >> a[i].cost;
    sort(a, a + n, [](const spot& u, const spot& v) {
        return (u.x == v.x) ? u.y > v.y : u.x < v.x;
    });
    
    rep(i, n) a[i].pos = i;

    rep(i, n) {
        clog << i << ":" << a[i].x << ' ' << a[i].y << ' ' << a[i].cost << endl;
    }

    map<line, vector<spot*>, cmp_line> group;
    rep(i, n) {
        for (int f = i + 1; f < n; ++f) {
            line ln = line::through_points(a[i], a[f]);
            group[ln].push_back(a + i);
            group[ln].push_back(a + f);
        }
    }

    itnode tree(0, n, [](int u) { return a[u].cost; });
    llong ans = 0;

    auto upd_ans = [&]() {
        clog << setw(3) << ans << ' ' << setw(3) <<  tree.max_sum_subarr << ": ";
        tree.dolog(); clog << endl;
        ans = max(ans, tree.max_sum_subarr);
    };
    upd_ans();

    vector<vector<spot*>> to_be_processed;
    auto process = [&]() {
        for (auto& i: to_be_processed) {
            sort(i.begin(), i.end(), [](spot* u, spot* v) { return u->pos < v->pos; });
            i.resize(unique(i.begin(), i.end()) - i.begin());
            rep1(f, len(i) - 1) {
                tree.inc(i[f]->pos, -i[f]->cost);
                tree.inc(i[0]->pos, i[f]->cost);
            }
        }
        upd_ans();
        for (auto& i: to_be_processed) {
            int first_pos = i[0]->pos;
            rep(f, len(i) - 1) {
                tree.inc(first_pos, -i[f]->cost);
                if (f < len(i) - f - 1) swap(i[f]->pos, i[len(i) - f - 1]->pos);
                tree.inc(i[f]->pos, i[f]->cost);
            }
        }
        upd_ans();
    };

    line cur_line(1, 0, 0);
    for (auto& [ln, points]: group) {
        if (cur_line.a != ln.a or cur_line.b != ln.b) {
            clog << "=== process" << endl;
            process();
            to_be_processed.clear();
            cur_line = ln;
        }
        to_be_processed.push_back(move(points));
        clog << "line : " << -ln.b << ' ' << ln.a << endl;
    }
    process();
    cout << ans;
    return 0;
}

Compilation message

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:186:16: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     for (auto& [ln, points]: group) {
                ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 676 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1016 KB Output is correct
2 Correct 13 ms 1016 KB Output is correct
3 Correct 11 ms 1020 KB Output is correct
4 Correct 12 ms 1016 KB Output is correct
5 Correct 11 ms 1024 KB Output is correct
6 Correct 11 ms 1016 KB Output is correct
7 Correct 11 ms 1016 KB Output is correct
8 Correct 12 ms 1016 KB Output is correct
9 Correct 12 ms 1016 KB Output is correct
10 Correct 11 ms 1116 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 380 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 14 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 10 ms 1016 KB Output is correct
22 Correct 10 ms 1016 KB Output is correct
23 Correct 10 ms 1016 KB Output is correct
24 Correct 11 ms 1016 KB Output is correct
25 Correct 11 ms 1016 KB Output is correct
26 Correct 10 ms 988 KB Output is correct
27 Correct 12 ms 1016 KB Output is correct
28 Correct 11 ms 1016 KB Output is correct
29 Correct 10 ms 1016 KB Output is correct
30 Correct 10 ms 1016 KB Output is correct
31 Correct 11 ms 1016 KB Output is correct
32 Correct 11 ms 1016 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1016 KB Output is correct
2 Correct 13 ms 1016 KB Output is correct
3 Correct 11 ms 1020 KB Output is correct
4 Correct 12 ms 1016 KB Output is correct
5 Correct 11 ms 1024 KB Output is correct
6 Correct 11 ms 1016 KB Output is correct
7 Correct 11 ms 1016 KB Output is correct
8 Correct 12 ms 1016 KB Output is correct
9 Correct 12 ms 1016 KB Output is correct
10 Correct 11 ms 1116 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 380 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 14 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 10 ms 1016 KB Output is correct
22 Correct 10 ms 1016 KB Output is correct
23 Correct 10 ms 1016 KB Output is correct
24 Correct 11 ms 1016 KB Output is correct
25 Correct 11 ms 1016 KB Output is correct
26 Correct 10 ms 988 KB Output is correct
27 Correct 12 ms 1016 KB Output is correct
28 Correct 11 ms 1016 KB Output is correct
29 Correct 10 ms 1016 KB Output is correct
30 Correct 10 ms 1016 KB Output is correct
31 Correct 11 ms 1016 KB Output is correct
32 Correct 11 ms 1016 KB Output is correct
33 Execution timed out 2047 ms 116312 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1016 KB Output is correct
2 Correct 13 ms 1016 KB Output is correct
3 Correct 11 ms 1020 KB Output is correct
4 Correct 12 ms 1016 KB Output is correct
5 Correct 11 ms 1024 KB Output is correct
6 Correct 11 ms 1016 KB Output is correct
7 Correct 11 ms 1016 KB Output is correct
8 Correct 12 ms 1016 KB Output is correct
9 Correct 12 ms 1016 KB Output is correct
10 Correct 11 ms 1116 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 380 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 14 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 10 ms 1016 KB Output is correct
22 Correct 10 ms 1016 KB Output is correct
23 Correct 10 ms 1016 KB Output is correct
24 Correct 11 ms 1016 KB Output is correct
25 Correct 11 ms 1016 KB Output is correct
26 Correct 10 ms 988 KB Output is correct
27 Correct 12 ms 1016 KB Output is correct
28 Correct 11 ms 1016 KB Output is correct
29 Correct 10 ms 1016 KB Output is correct
30 Correct 10 ms 1016 KB Output is correct
31 Correct 11 ms 1016 KB Output is correct
32 Correct 11 ms 1016 KB Output is correct
33 Execution timed out 2047 ms 116312 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 676 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 11 ms 1016 KB Output is correct
17 Correct 13 ms 1016 KB Output is correct
18 Correct 11 ms 1020 KB Output is correct
19 Correct 12 ms 1016 KB Output is correct
20 Correct 11 ms 1024 KB Output is correct
21 Correct 11 ms 1016 KB Output is correct
22 Correct 11 ms 1016 KB Output is correct
23 Correct 12 ms 1016 KB Output is correct
24 Correct 12 ms 1016 KB Output is correct
25 Correct 11 ms 1116 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 2 ms 376 KB Output is correct
29 Correct 2 ms 380 KB Output is correct
30 Correct 2 ms 376 KB Output is correct
31 Correct 14 ms 376 KB Output is correct
32 Correct 2 ms 376 KB Output is correct
33 Correct 2 ms 376 KB Output is correct
34 Correct 2 ms 376 KB Output is correct
35 Correct 2 ms 376 KB Output is correct
36 Correct 10 ms 1016 KB Output is correct
37 Correct 10 ms 1016 KB Output is correct
38 Correct 10 ms 1016 KB Output is correct
39 Correct 11 ms 1016 KB Output is correct
40 Correct 11 ms 1016 KB Output is correct
41 Correct 10 ms 988 KB Output is correct
42 Correct 12 ms 1016 KB Output is correct
43 Correct 11 ms 1016 KB Output is correct
44 Correct 10 ms 1016 KB Output is correct
45 Correct 10 ms 1016 KB Output is correct
46 Correct 11 ms 1016 KB Output is correct
47 Correct 11 ms 1016 KB Output is correct
48 Execution timed out 2047 ms 116312 KB Time limit exceeded
49 Halted 0 ms 0 KB -