Submission #442674

#	Time	Username	Problem	Language	Result	Execution time	Memory
442674		valerikk	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	957 ms	55620 KiB

bulldozer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;

const int S = 1 << 11;
const int N = S + 7;

struct event {
    ll x, y;
    int i, j;
};

bool operator<(const event &l, const event &r) {
    return l.x * r.y - l.y * r.x < 0;
}

bool operator==(const event &l, const event &r) {
    return l.x * r.y - l.y * r.x == 0;
}

int n;
ll x[N], y[N], w[N];
int ord[N];
ll sum[2 * S];
ll mx[2 * S];
ll pref[2 * S], suff[2 * S];
int where[N];
vector<event> events;

void init(int i, ll val) {
    i += S;
    sum[i] = val;
    mx[i] = pref[i] = suff[i] = max(0ll, val);
}

void recalc(int i) {
    int l = i << 1, r = i << 1 | 1;
    sum[i] = sum[l] + sum[r];
    mx[i] = max({mx[l], mx[r], suff[l] + pref[r]});
    pref[i] = max(pref[l], sum[l] + pref[r]);
    suff[i] = max(suff[r], sum[r] + suff[l]);
}

void build() {
    for (int i = 0; i < S; i++) init(i, 0);
    for (int i = 0; i < n; i++) init(i, w[ord[i]]);
    for (int i = S - 1; i > 0; i--) recalc(i);
}

void upd(int i, ll val) {
    init(i, val);
    i += S;
    while (i > 1) {
        i >>= 1;
        recalc(i);
    }
}

ll get() {
    return mx[1];
}

void my_swap(int i, int j) {
    int pi = where[i], pj = where[j];
    upd(pi, w[j]);
    upd(pj, w[i]);
    swap(ord[where[i]], ord[where[j]]);
    swap(where[i], where[j]);
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i] >> w[i];
    }
    for (int i = 0; i < n; i++) ord[i] = i;
    sort(ord, ord + n, [&](const int &i, const int &j) {
        return x[i] < x[j] || (x[i] == x[j] && y[i] > y[j]);
    });
    for (int i = 0; i < n; i++) where[ord[i]] = i;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            ll dx = x[i] - x[j], dy = y[i] - y[j];
            dy *= -1;
            swap(dx, dy);
            if (dy < 0 || (dy == 0 && dx < 0)) {
                dx *= -1;
                dy *= -1;
            }
            events.push_back({dx, dy, i, j});
        }
    }
    sort(events.begin(), events.end());
    build();
    ll ans = get();
    int i = 0;
    while (i < events.size()) {
        int j = i;
        while (j < events.size() && events[j] == events[i]) j++;
        vector<int> arr;
        for (int k = i; k < j; k++) arr.push_back(min(where[events[k].i], where[events[k].j]));
        sort(arr.begin(), arr.end());
        arr.erase(unique(arr.begin(), arr.end()), arr.end());
        int k = 0;
        while (k < arr.size()) {
            int l = k;
            while (l + 1 < arr.size() && arr[l + 1] == arr[l] + 1) l++;
            int L = arr[k], R = arr[l] + 1;
            for (int t = 0; L + t < R - t; t++) my_swap(ord[L + t], ord[R - t]);
            k = l + 1;
        }
        ans = max(ans, get());
        i = j;
    }
    cout << ans << endl;
    return 0;
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:104:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     while (i < events.size()) {
      |            ~~^~~~~~~~~~~~~~~
bulldozer.cpp:106:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         while (j < events.size() && events[j] == events[i]) j++;
      |                ~~^~~~~~~~~~~~~~~
bulldozer.cpp:112:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         while (k < arr.size()) {
      |                ~~^~~~~~~~~~~~
bulldozer.cpp:114:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             while (l + 1 < arr.size() && arr[l + 1] == arr[l] + 1) l++;
      |                    ~~~~~~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 35 / 35
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20