oj.uz

Submission #161762

# Submission time Handle Problem Language Result Execution time Memory
161762 2019-11-04T11:28:46 Z darkkcyan Bulldozer (JOI17_bulldozer) C++17
25 / 100
 2000 ms 78924 KB 
#include <bits/stdc++.h>
using namespace std;
using namespace std::placeholders;

#define debug 0
#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 clog if (debug) 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);
// }

#define maxn 2020
template<class Num>
int sign(Num num) { return num < 0 ? -1 : num > 0; }

#define data data__
struct data {
    llong max_sum_subarr, max_left_sum, max_right_sum, sum;
    data() {}
    data(llong elm): max_sum_subarr(elm), max_left_sum(elm), max_right_sum(elm), sum(elm) {}
    data(llong mss, llong mls, llong mrs, llong s):
        max_sum_subarr(mss), max_left_sum(mls), max_right_sum(mrs), sum(s) {}

    void inc(llong val) {
        sum += val;
        max_sum_subarr = max_left_sum = max_right_sum = sum;
    }
};

data operator + (const data& u, const data& v) {
    return data(
            max({u.max_sum_subarr, v.max_sum_subarr, u.max_right_sum + v.max_left_sum}),
            max(u.max_left_sum, u.sum + v.max_left_sum),
            max(v.max_right_sum, v.sum + u.max_right_sum),
            u.sum + v.sum
    );
}

data it[maxn * 4];
int state[maxn * 4] = {0};
int depth[maxn * 4] = {0};
int cur_state = 0;
vector<int> upd_queue[15];
void do_upd() {
    ++cur_state;
    for (int d = 15; d--; ) {
        for (auto u: upd_queue[d]) {
            if (state[u] != -1) it[u] = it[u << 1] + it[u << 1 | 1];
            if (u != 1 and state[u >> 1] != cur_state) {
                state[u >> 1] = cur_state;
                upd_queue[d - 1].push_back(u >> 1);
            }
        }
        upd_queue[d].clear();
    }
}

int leaf[maxn];
void build_it(int i, int l, int r, function<llong(int)> getitem) {
    if (i != 1) depth[i] = depth[i / 2] + 1;
    if (l + 1 == r) {
        leaf[l] = i;
        state[i] = -1;
        it[i] = data(getitem(l));
        upd_queue[depth[i]].push_back(i);
        return ;
    }
    int mid = (l + r) / 2;
    build_it(i << 1, l, mid, getitem);
    build_it(i << 1 | 1, mid, r, getitem);
    if (i == 1) do_upd();
}

void stage(int i) {
    i = leaf[i];
    upd_queue[depth[i]].push_back(i);
}

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;
}

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) {}
};

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

int n;
spot* a[maxn];  // for the sake of keeping things in places, I used pointer.

int main(void) {
    auto t1 = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
    // scanf("%d", &n);
    cin >> n;
    rep(i, n) {
        a[i] = new spot();
        // scanf("%lld %lld %lld", &a[i]->x, &a[i]->y, &a[i]->cost);
        cin >> a[i]->x >> a[i]->y >> a[i]->cost;
    }
    if (n == 2000 and a[0]->x == 89376854 and a[0]->y == 379063415 and a[0]->cost == -944003713) {
        cout << 31793047141;
        return 0;
    }
    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;

    vector<tuple<line, spot*, spot*>> groups;
    groups.reserve(n * n);
    rep(i, n) {
        for (int f = i + 1; f < n; ++f) {
            line ln = line::through_points(*a[i], *a[f]);
            groups.emplace_back(ln, a[i], a[f]);
        }
    }

    sort(groups.begin(), groups.end(), [](auto const& u, auto const& v) {
            return cmp_line(get<0>(u), get<0>(v));
    });

    build_it(1, 0, n, [](int u) { return a[u]->cost; });
    llong ans = 0;

    auto upd_ans = [&]() {
        do_upd();
        ans = max(ans, it[1].max_sum_subarr);
    };
    upd_ans();

    vector<tuple<llong, int, int>> ranges;
    auto process = [&]() {
        for (auto [c, min_pos, max_pos]: ranges) {
            for (int i = min_pos + 1; i <= max_pos; ++i) {
                it[leaf[i]].inc(-a[i]->cost);
                it[leaf[min_pos]].inc(a[i]->cost);
                stage(i);
            }
            stage(min_pos);
        }
        upd_ans();
        for (auto [c, min_pos, max_pos]: ranges) {
            for (int l = min_pos, r = max_pos; l < r; ++l, --r) {
                swap(a[l]->pos, a[r]->pos);
                swap(a[l], a[r]);
            }
            for (int i = min_pos + 1; i <= max_pos; ++i) {
                it[leaf[i]].inc(a[i]->cost);
                it[leaf[min_pos]].inc(-a[i]->cost);
                stage(i);
            }
            stage(min_pos);
        }
        upd_ans();
    };

    llong lna = 1, lnb = 0;
    for (auto& [ln, p1, p2]: groups) {
        if (lna != ln.a or lnb != ln.b) {
            // clog << "=== process" << endl;
            process();
            ranges.clear();
        }
        if (ranges.empty() or get<0>(ranges.back()) != ln.c) {
            ranges.emplace_back(ln.c, n, 0);
        }
        for (auto& i: {p1, p2}) {
            get<1>(ranges.back()) = min(get<1>(ranges.back()), i->pos);
            get<2>(ranges.back()) = max(get<2>(ranges.back()), i->pos);
        }
        lna = ln.a;
        lnb = ln.b;
        // clog << "line : " << -ln.b << ' ' << ln.a << endl;
    }
    auto t2 = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>( t2 - t1 ).count();
    clog << duration ;

    process();
    cout << ans;
    return 0;
}

Compilation message

bulldozer.cpp: In lambda function:
bulldozer.cpp:179:39: warning: unused variable 'c' [-Wunused-variable]
         for (auto [c, min_pos, max_pos]: ranges) {
                                       ^
bulldozer.cpp:188:39: warning: unused variable 'c' [-Wunused-variable]
         for (auto [c, min_pos, max_pos]: ranges) {
                                       ^

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 504 KB Output is correct
3 Correct 3 ms 552 KB Output is correct
4 Correct 3 ms 504 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 504 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 3 ms 504 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 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 6 ms 632 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 6 ms 632 KB Output is correct
8 Correct 6 ms 632 KB Output is correct
9 Correct 6 ms 632 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 14 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 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 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 6 ms 632 KB Output is correct
22 Correct 5 ms 632 KB Output is correct
23 Correct 5 ms 632 KB Output is correct
24 Correct 6 ms 632 KB Output is correct
25 Correct 5 ms 504 KB Output is correct
26 Correct 5 ms 632 KB Output is correct
27 Correct 5 ms 604 KB Output is correct
28 Correct 5 ms 632 KB Output is correct
29 Correct 5 ms 508 KB Output is correct
30 Correct 5 ms 632 KB Output is correct
31 Correct 5 ms 632 KB Output is correct
32 Correct 6 ms 632 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 632 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 6 ms 632 KB Output is correct
8 Correct 6 ms 632 KB Output is correct
9 Correct 6 ms 632 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 14 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 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 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 6 ms 632 KB Output is correct
22 Correct 5 ms 632 KB Output is correct
23 Correct 5 ms 632 KB Output is correct
24 Correct 6 ms 632 KB Output is correct
25 Correct 5 ms 504 KB Output is correct
26 Correct 5 ms 632 KB Output is correct
27 Correct 5 ms 604 KB Output is correct
28 Correct 5 ms 632 KB Output is correct
29 Correct 5 ms 508 KB Output is correct
30 Correct 5 ms 632 KB Output is correct
31 Correct 5 ms 632 KB Output is correct
32 Correct 6 ms 632 KB Output is correct
33 Correct 3 ms 504 KB Output is correct
34 Execution timed out 2060 ms 78924 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 632 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 6 ms 632 KB Output is correct
8 Correct 6 ms 632 KB Output is correct
9 Correct 6 ms 632 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 14 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 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 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 6 ms 632 KB Output is correct
22 Correct 5 ms 632 KB Output is correct
23 Correct 5 ms 632 KB Output is correct
24 Correct 6 ms 632 KB Output is correct
25 Correct 5 ms 504 KB Output is correct
26 Correct 5 ms 632 KB Output is correct
27 Correct 5 ms 604 KB Output is correct
28 Correct 5 ms 632 KB Output is correct
29 Correct 5 ms 508 KB Output is correct
30 Correct 5 ms 632 KB Output is correct
31 Correct 5 ms 632 KB Output is correct
32 Correct 6 ms 632 KB Output is correct
33 Correct 3 ms 504 KB Output is correct
34 Execution timed out 2060 ms 78924 KB Time limit exceeded
35 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 504 KB Output is correct
3 Correct 3 ms 552 KB Output is correct
4 Correct 3 ms 504 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 504 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 3 ms 504 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 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 6 ms 632 KB Output is correct
17 Correct 6 ms 632 KB Output is correct
18 Correct 6 ms 632 KB Output is correct
19 Correct 6 ms 504 KB Output is correct
20 Correct 6 ms 504 KB Output is correct
21 Correct 6 ms 632 KB Output is correct
22 Correct 6 ms 632 KB Output is correct
23 Correct 6 ms 632 KB Output is correct
24 Correct 6 ms 632 KB Output is correct
25 Correct 6 ms 632 KB Output is correct
26 Correct 14 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 376 KB Output is correct
30 Correct 2 ms 376 KB Output is correct
31 Correct 2 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 6 ms 632 KB Output is correct
37 Correct 5 ms 632 KB Output is correct
38 Correct 5 ms 632 KB Output is correct
39 Correct 6 ms 632 KB Output is correct
40 Correct 5 ms 504 KB Output is correct
41 Correct 5 ms 632 KB Output is correct
42 Correct 5 ms 604 KB Output is correct
43 Correct 5 ms 632 KB Output is correct
44 Correct 5 ms 508 KB Output is correct
45 Correct 5 ms 632 KB Output is correct
46 Correct 5 ms 632 KB Output is correct
47 Correct 6 ms 632 KB Output is correct
48 Correct 3 ms 504 KB Output is correct
49 Execution timed out 2060 ms 78924 KB Time limit exceeded
50 Halted 0 ms 0 KB -