oj.uz

Submission #537883

# Submission time Handle Problem Language Result Execution time Memory
537883 2022-03-15T19:00:22 Z MrKustic Bulldozer (JOI17_bulldozer) C++14
25 / 100
 2000 ms 188220 KB 
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb emplace_back
#define x first
#define y second

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pt;
typedef pair<ll, ll> ptll;
//typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//typedef gp_hash_table<int, int> table;

void fastio(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}


#pragma GCC optimize("Ofast")


//-------------------------------------------

struct Point {
    ll x, y, w;
    int id;

    bool top() const{
        return (y > 0) || (y == 0 && x >= 0);
    };

    ll distq(Point other = {0, 0}) const{
        return (other.x - x) * (other.x - x) + (other.y - y) * (other.y - y);
    }

    ld dist(Point other = {0, 0}) const{
        return sqrt(distq(other));
    }

    void rev(){
        x = -x, y = -y;
    }

    ll operator % (Point other) const{
        return x * other.y - y * other.x;
    }

    ll operator * (Point other) const{
        return x * other.x + y * other.y;
    }

    Point operator +(Point other) const{
        return {x + other.x, y + other.y};
    }

    Point operator -(Point other) const{
        return {x - other.x, y - other.y};
    }

    friend istream& operator >> (istream& in, Point &p){
        in >> p.x >> p.y >> p.w;
        return in;
    }

    friend ostream& operator << (ostream& out, Point &p){
        out << p.x << " " << p.y;
        return out;
    }
};

struct Vector {
    ll x, y;
    int id1, id2;

    bool top() const{
        return (y > 0) || (y == 0 && x >= 0);
    };

    ll distq(Vector other = {0, 0}) const{
        return (other.x - x) * (other.x - x) + (other.y - y) * (other.y - y);
    }

    ld dist(Vector other = {0, 0}) const{
        return sqrt(distq(other));
    }

    ld cock;

    void rev(){
        x = -x, y = -y;
    }

    ll operator % (Vector other) const{
        return x * other.y - y * other.x;
    }

    ll operator * (Vector other) const{
        return x * other.x + y * other.y;
    }

    ll operator * (Point other) const{
        return x * other.x + y * other.y;
    }

    Vector operator +(Vector other) const{
        return {x + other.x, y + other.y};
    }

    Vector operator -(Vector other) const{
        return {x - other.x, y - other.y};
    }

    friend istream& operator >> (istream& in, Vector &p){
        in >> p.x >> p.y;
        return in;
    }

    friend ostream& operator << (ostream& out, Vector &p){
        out << p.x << " " << p.y << " " << p.id1 << " " << p.id2 << "  " << p.cock;
        return out;
    }
};

const int MAXN = 2003;

Point a[MAXN];
Vector vs[MAXN * MAXN];

int ids[MAXN];
int pos[MAXN];

ll pref[MAXN];

int n;

/*ptll tree[MAXN << 2];

void upd(int v, int l, int r, int posi, ll val){
    if (r - l == 1){
        tree[v] = {val, val};
        return;
    }
    int m = (l + r) >> 1;
    if (posi < m)
        upd(v << 1, l, m, posi, val);
    else
        upd(v << 1 | 1, m, r, posi, val);
    tree[v].x = min(tree[v << 1].x, tree[v << 1 | 1].x);
    tree[v].y = max(tree[v << 1].y, tree[v << 1 | 1].y);
}

ll getmin(int v, int l, int r, int ql, int qr){
    if (r <= ql || qr <= l)
        return 1e18;
    if (ql <= l && r <= qr)
        return tree[v].x;
    int m = (l + r) >> 1;
    return min(getmin(v << 1, l, m, ql, qr), getmin(v << 1 | 1, m, r, ql, qr));
}

ll getmax(int v, int l, int r, int ql, int qr){
    if (r <= ql || qr <= l)
        return -1e18;
    if (ql <= l && r <= qr)
        return tree[v].x;
    int m = (l + r) >> 1;
    return max(getmax(v << 1, l, m, ql, qr), getmax(v << 1 | 1, m, r, ql, qr));
}*/

ptll tree[100000];

void upd(int i, ll val){
    i += MAXN;
    for (tree[i] = ptll{val, val}; i > 1; i >>= 1){
        tree[i >> 1].x = min(tree[i].x, tree[i ^ 1].x);
        tree[i >> 1].y = max(tree[i].y, tree[i ^ 1].y);
    }
}

ll getmin(int l, int r){
    l += MAXN, r += MAXN;
    ll res = 1e18;
    while (l < r){
        if (l & 1)
            res = min(res, tree[l++].x);
        if (r & 1)
            res = min(res, tree[--r].x);
        l >>= 1, r >>= 1;
    }
    return res;
}

ll getmax(int l, int r){
    l += MAXN, r += MAXN;
    ll res = -1e18;
    while (l < r){
        if (l & 1)
            res = max(res, tree[l++].y);
        if (r & 1)
            res = max(res, tree[--r].y);
        l >>= 1, r >>= 1;
    }
    return res;
}

pt upds[MAXN * 2];

ll calc(int ln){
    ll res = 0;
    for (int j = 0; j < ln; j++){
        for (int i = upds[j].x; i <= upds[j].y; i++){
            ll mn = getmin(1, i + 1);
            ll mx = getmax(i + 1, n + 2);
            res = max(res, max(pref[i] - mn, mx - pref[i]));
        }
    }
    return res;
}

void run(){
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    if (n == 1){
        cout << max(0ll, a[0].w);
        return;
    }
    int m = 0;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            if (i == j)
                continue;
            vs[m++] = {-(a[j] - a[i]).y, (a[j] - a[i]).x, i, j, (ld)(a[i] % a[j]) / (a[i].y != a[j].y ? a[i].y - a[j].y : (a[j].x - a[i].x))};
        }
    }
    sort(vs, vs + m, [&](Vector p, Vector q){
        bool ta = p.top(), tb = q.top();
        if (ta != tb)
            return ta;
        ll cp = p % q;
        return (cp > 0 || (cp == 0 && p.cock < q.cock));
    });
    iota(ids, ids + n, 0);
    Vector start = {(int)2e9 + 110, -1};
    //cout << start << endl;
    //cout << "------" << endl;
    for (int i = 0; i < n; i++){
        ld val2 = (start * a[i]);
        //cout << val2 << endl;
    }
    //cout << "------" << endl;
    sort(ids, ids + n, [&](int i, int j){
        return start * a[i] < start * a[j];
    });
    for (int i = 1; i <= n; i++){
        pref[i] = pref[i - 1] + a[ids[i - 1]].w;
        upd(i + 1, pref[i]);
    }
    //cout << start << endl;
    for (int i = 0; i < n; i++)
        pos[ids[i]] = i;
    /*for (int i = 0; i < m; i++)
        cout << vs[i] << endl;
    for (int i = 0; i < n; i++)
        cout << ids[i] << " " << a[ids[i]].w << " ";
    cout << endl;
    for (int i = 0; i < n; i++)
        cout << pos[i];
    cout << endl;
    for (int i = 0; i <= n; i++)
        cout << pref[i] << " ";
    cout << endl;
    cout << "==========" << endl;*/
    ll ans = 0;
    for (int i = 0; i < m; i++){
        Vector curr = vs[i];
        int j = i;
        int head;
        int t = 0;
        for (; j < m && curr % vs[j] == 0 && curr * vs[j] >= 0; j++){
            head = j;
            for (; j + 1 < m && curr % vs[j + 1] == 0 && curr * vs[j + 1] >= 0 && abs(vs[head].cock - vs[j + 1].cock) < 1e-9; j++);
            //cout << head << " " << j << curr.cock << endl;
            int l = 1e9, r = -1;
            for (int k = head; k <= j; k++){
                //cout << "k = " << k << " | " << vs[k] << endl;
                l = min(l, pos[vs[k].id1]);
                l = min(l, pos[vs[k].id2]);
                r = max(r, pos[vs[k].id1]);
                r = max(r, pos[vs[k].id2]);
            }
            for (int k = l; k <= (l + r) / 2; k++){
                swap(ids[k], ids[r - k + l]);
                swap(pos[ids[k]], pos[ids[r - k + l]]);
            }
            for (int k = l; k <= r; k++){
                pref[k + 1] = pref[k] + a[ids[k]].w;
                upd(k + 2, pref[k + 1]);
            }
            upds[t++] = {l + 1, r + 1};
            /*cout << l << " " << r << "!" << vs[head] << endl;
            for (int k = 0; k < n; k++)
                cout << ids[k] << " ";
            cout << endl;
            for (int k = 0; k < n; k++)
                cout << pos[k];
            cout << endl;
            for (int i = 0; i <= n; i++)
                cout << pref[i] << " ";
            cout << endl;
            cout << "j = " << j << " " << curr << " " << vs[j] << " " << curr % vs[j] << " " << curr * vs[j] << endl;
            cout << "=========" << endl;*/
        }
        j--;
        ans = max(ans, calc(t));
        //cout << ans << " = ans" << endl;
        i = j;
    }
    cout << ans;
}

int main(){
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#else
    fastio();
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
#endif
    auto start = chrono::high_resolution_clock::now();
    run();
    auto stop = chrono::high_resolution_clock::now();
#ifdef LOCAL
    cerr << "Program finished in " << (ld)chrono::duration_cast<chrono::milliseconds>(stop - start).count() / 1e3 << " sec";
#endif
    return 0;
}

Compilation message

bulldozer.cpp: In function 'void run()':
bulldozer.cpp:255:12: warning: unused variable 'val2' [-Wunused-variable]
  255 |         ld val2 = (start * a[i]);
      |            ^~~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:337:10: warning: variable 'start' set but not used [-Wunused-but-set-variable]
  337 |     auto start = chrono::high_resolution_clock::now();
      |          ^~~~~
bulldozer.cpp:339:10: warning: variable 'stop' set but not used [-Wunused-but-set-variable]
  339 |     auto stop = chrono::high_resolution_clock::now();
      |          ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 3 ms 840 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 840 KB Output is correct
2 Correct 4 ms 836 KB Output is correct
3 Correct 5 ms 840 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 4 ms 836 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 4 ms 724 KB Output is correct
8 Correct 5 ms 844 KB Output is correct
9 Correct 5 ms 724 KB Output is correct
10 Correct 5 ms 836 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 328 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 5 ms 844 KB Output is correct
22 Correct 5 ms 848 KB Output is correct
23 Correct 5 ms 724 KB Output is correct
24 Correct 5 ms 724 KB Output is correct
25 Correct 5 ms 724 KB Output is correct
26 Correct 5 ms 724 KB Output is correct
27 Correct 5 ms 724 KB Output is correct
28 Correct 5 ms 844 KB Output is correct
29 Correct 5 ms 724 KB Output is correct
30 Correct 4 ms 724 KB Output is correct
31 Correct 7 ms 840 KB Output is correct
32 Correct 5 ms 724 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 840 KB Output is correct
2 Correct 4 ms 836 KB Output is correct
3 Correct 5 ms 840 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 4 ms 836 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 4 ms 724 KB Output is correct
8 Correct 5 ms 844 KB Output is correct
9 Correct 5 ms 724 KB Output is correct
10 Correct 5 ms 836 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 328 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 5 ms 844 KB Output is correct
22 Correct 5 ms 848 KB Output is correct
23 Correct 5 ms 724 KB Output is correct
24 Correct 5 ms 724 KB Output is correct
25 Correct 5 ms 724 KB Output is correct
26 Correct 5 ms 724 KB Output is correct
27 Correct 5 ms 724 KB Output is correct
28 Correct 5 ms 844 KB Output is correct
29 Correct 5 ms 724 KB Output is correct
30 Correct 4 ms 724 KB Output is correct
31 Correct 7 ms 840 KB Output is correct
32 Correct 5 ms 724 KB Output is correct
33 Execution timed out 2091 ms 188220 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 840 KB Output is correct
2 Correct 4 ms 836 KB Output is correct
3 Correct 5 ms 840 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 4 ms 836 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 4 ms 724 KB Output is correct
8 Correct 5 ms 844 KB Output is correct
9 Correct 5 ms 724 KB Output is correct
10 Correct 5 ms 836 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 328 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 5 ms 844 KB Output is correct
22 Correct 5 ms 848 KB Output is correct
23 Correct 5 ms 724 KB Output is correct
24 Correct 5 ms 724 KB Output is correct
25 Correct 5 ms 724 KB Output is correct
26 Correct 5 ms 724 KB Output is correct
27 Correct 5 ms 724 KB Output is correct
28 Correct 5 ms 844 KB Output is correct
29 Correct 5 ms 724 KB Output is correct
30 Correct 4 ms 724 KB Output is correct
31 Correct 7 ms 840 KB Output is correct
32 Correct 5 ms 724 KB Output is correct
33 Execution timed out 2091 ms 188220 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 3 ms 840 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 5 ms 840 KB Output is correct
17 Correct 4 ms 836 KB Output is correct
18 Correct 5 ms 840 KB Output is correct
19 Correct 4 ms 724 KB Output is correct
20 Correct 4 ms 836 KB Output is correct
21 Correct 4 ms 724 KB Output is correct
22 Correct 4 ms 724 KB Output is correct
23 Correct 5 ms 844 KB Output is correct
24 Correct 5 ms 724 KB Output is correct
25 Correct 5 ms 836 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 328 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 328 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 5 ms 844 KB Output is correct
37 Correct 5 ms 848 KB Output is correct
38 Correct 5 ms 724 KB Output is correct
39 Correct 5 ms 724 KB Output is correct
40 Correct 5 ms 724 KB Output is correct
41 Correct 5 ms 724 KB Output is correct
42 Correct 5 ms 724 KB Output is correct
43 Correct 5 ms 844 KB Output is correct
44 Correct 5 ms 724 KB Output is correct
45 Correct 4 ms 724 KB Output is correct
46 Correct 7 ms 840 KB Output is correct
47 Correct 5 ms 724 KB Output is correct
48 Execution timed out 2091 ms 188220 KB Time limit exceeded
49 Halted 0 ms 0 KB -