Submission #1155077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155077		jerzyk	Bulldozer (JOI17_bulldozer)	C++20	100 / 100	516 ms	16308 KiB

bulldozer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1<<11;
pair<pair<ll, ll>, int> inp[N];
int wh[N];
pair<ll, ll> tab[N];
ll drz[2 * N], pre[2 * N], suf[2 * N], ans[2 * N];
pair<int, int> swi[N * N / 2];

inline void Upd(int v)
{
    drz[v] = drz[v * 2] + drz[v * 2 + 1];
    pre[v] = max(pre[v * 2], pre[v * 2 + 1] + drz[v * 2]);
    suf[v] = max(suf[v * 2 + 1], suf[v * 2] + drz[v * 2 + 1]);
    ans[v] = max(ans[v * 2], ans[v * 2 + 1]);
    ans[v] = max(ans[v], suf[v * 2] + pre[v * 2 + 1]);
}

void Switch(int a, int b)
{
    a += N; b += N;
    swap(drz[a], drz[b]);
    swap(pre[a], pre[b]);
    swap(suf[a], suf[b]);
    swap(ans[a], ans[b]);
    a /= 2; b /= 2;
    while(a != b)
    {
        Upd(a); Upd(b);
        a /= 2; b /= 2;
    }
    while(a > 0)
    {
        Upd(a);
        a /= 2;
    }
}

bool Eq(pair<int, int> a, pair<int, int> b)
{
    ll x1 = tab[a.nd].st - tab[a.st].st, y1 = tab[a.nd].nd - tab[a.st].nd;
    ll x2 = tab[b.nd].st - tab[b.st].st, y2 = tab[b.nd].nd - tab[b.st].nd;
    return(y1 * x2 == y2 * x1);
}
bool Cp(pair<int, int> a, pair<int, int> b)
{
    ll x1 = tab[a.nd].st - tab[a.st].st, y1 = tab[a.nd].nd - tab[a.st].nd;
    ll x2 = tab[b.nd].st - tab[b.st].st, y2 = tab[b.nd].nd - tab[b.st].nd;
    if(y1 * x2 > y2 * x1)
        return 1;
    if(y1 * x2 < y2 * x1)
        return 0;
    return (a < b);
}

void Solve()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> inp[i].st.st >> inp[i].st.nd >> inp[i].nd;
    sort(inp + 1, inp + 1 + n);
    for(int i = 1; i <= n; ++i)
    {
        tab[i] = inp[i].st; wh[i] = i;
        drz[i + N] = inp[i].nd;
        pre[i + N] = max(0LL, drz[i + N]);
        suf[i + N] = pre[i + N]; ans[i + N] = pre[i + N];
    }
    int m = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = i + 1; j <= n; ++j)
            swi[++m] = make_pair(i, j);
    for(int i = N - 1; i >= 1; --i) Upd(i);
    ll answer = ans[1];
    sort(swi + 1, swi + 1 + m, Cp);
    int j = 1;
    while(j <= m)
    {
        int l = j;
        //cout << "B\n";
        while(l <= m && Eq(swi[j], swi[l]))
        {
            //cout << "S: " << swi[l].st << " " << swi[l].nd << "\n";
            Switch(wh[swi[l].st], wh[swi[l].nd]);
            swap(wh[swi[l].st], wh[swi[l].nd]);
            ++l;
        }
        answer = max(answer, ans[1]);
        j = l;
    }
    cout << answer << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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