oj.uz

Submission #64281

# Submission time Handle Problem Language Result Execution time Memory
64281 2018-08-03T22:04:30 Z FLDutchman Bulldozer (JOI17_bulldozer) C++14
100 / 100
 1771 ms 392144 KB 
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back
#define fst first
#define snd second
#define int long long
#define fast_io() ios::sync_with_stdio(false)
#define FOR(i, l, r) for(int i = (l); i < (r); i++)

typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef set<int> si;
typedef double ld;
typedef pair<ld, ld> dd;

const ll INF = 1000000000000000000LL;
const int NMAX = 1e6+4;
const int mod = 1e9+7;
const ld eps = 1e-10;
const ld PI = acos(-1);

struct point{
    int x, y, w, i; 
    const bool operator< (const point &p){
        return mp(x, y) < mp(p.x, p.y);
    }
};

int N;
vector<point> pts;
vi position;

struct event{
    int i, j;
    int x1, y1, x2, y2;
    int dx, dy;
    event(int a, int b) : i(a), j(b) {
        if(pts[j].x < pts[i].x) swap(i, j);
        x1 = pts[i].x, y1 = pts[i].y;
        x2 = pts[j].x, y2 = pts[j].y;
        dx = x2 - x1;
        dy = y2 - y1;
    }

    event(){}

    friend bool operator< ( const event &e1, const event &e2){
        int s = e1.dy * e2.dx - e2.dy * e1.dx;
        if(s != 0) return s < 0;
        return e1.dx * (e1.y1 - e2.y1) + e1.dy * (e2.x1 - e1.x1) < 0;
    }
};

bool par(const event &e1, const event &e2){
    return  e1.dy * e2.dx == e2.dy * e1.dx;
}

bool col(const event &e1, const event &e2){
    return !(e1 < e2) and !(e2 < e1);
}

vi tsum, tmin, tmax, tbest;

void update(int n){
    int l = n<<1, r = l|1;
    tsum[n] = tsum[l] + tsum[r];
    tmin[n] = min(tmin[l], tsum[l] + tmin[r]);
    tmax[n] = max(tmax[l], tsum[l] + tmax[r]);
    tbest[n] = max(tsum[l] + tmax[r] - tmin[l], max(tbest[l], tbest[r]));
}

void buildtree(int lb, int rb, int n = 1){
    if(lb+1 == rb) {
        int w = pts[lb].w;
        tsum[n] = w;
        tmin[n] = min(0LL, w);
        tbest[n] = tmax[n] = max(0LL, w);
    } else {
        int mb = (lb+rb)/2;
        buildtree(lb, mb, n<<1);
        buildtree(mb, rb, n<<1|1);
        update(n);
    }
}

void modify(int i, int w, int lb, int rb, int n = 1){
    if(lb+1 == rb){
        tsum[n] = w;
        tmin[n] = min(0LL, w);
        tmax[n] = max(0LL, w);
    } else {
        int mb = (lb+rb)/2;
        if(i < mb) modify(i, w, lb, mb, n<<1);
        else modify(i, w, mb, rb, n<<1|1);
        update(n);
    }
}

int getbest(){
    return tbest[1];
}

vector<event> events;

signed main(){
    fast_io();
    cin >> N;
    tmin.assign(4*N, 0);
    tmax.assign(4*N, 0);
    tsum.assign(4*N, 0);
    tbest.assign(4*N, 0);
    position.assign(N, 0);
    FOR(i, 0, N){
        int x,y,w;
        cin >> x >> y >> w;
        pts.pb({x, y, w, y});
    }
    sort(pts.begin(), pts.end());
    FOR(i, 0, N) pts[i].i = i;
    FOR(i, 0, N) position[pts[i].i] = i;
    buildtree(0, N);
    FOR(i, 0, N) FOR(j, i+1, N) events.pb(event(i, j));
    sort(events.begin(), events.end());
    // each block contains parallel events

    //cout << "Sorted events" << endl;

    vector<vector<vector<event>>> blocks;
    FOR(i, 0, events.size()){
        if(i == 0 || !par(events[i], events[i-1])) blocks.pb(  vector<vector<event>>(0));
        if(i == 0 || !col(events[i], events[i-1])) blocks.back().pb(vector<event>(0));
        blocks.back().back().pb(events[i]);
    }

    int best = getbest();
    for( auto &pars : blocks) {
       // cout << "pars size " << pars.size() << endl; 
        for(auto &cols : pars){
            //cout << "cols size " << cols.size() << endl;
            int l = N, r = 0;
            for(event &e : cols) l = min(l, position[e.i]), l = min(l, position[e.j]), r = max(r, position[e.i]), r = max(r, position[e.j]);
            // swap [l, r]
            //cout << "swapping " << l << " " << r << endl;
            for(int i = l, j = r; i < j; i++, j--){
                // positions in 
                int p1 = pts[i].i, p2 = pts[j].i;
                swap(position[p1], position[p2]);
                int w1 = pts[i].w, w2 = pts[j].w;
                modify(i, w2, 0, N);
                modify(j, w1, 0, N);
                swap(pts[i], pts[j]);
            }
        }
        best = max(best, getbest());
    }
    cout << best << endl;
}


/*
5
-5 5 -2
2 5 10
1 4 -2
4 -5 4
-2 2 7



*/

Compilation message

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:10:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = (l); i < (r); i++)
                                         ^
bulldozer.cpp:134:5: note: in expansion of macro 'FOR'
     FOR(i, 0, events.size()){
     ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1380 KB Output is correct
2 Correct 3 ms 1456 KB Output is correct
3 Correct 3 ms 1408 KB Output is correct
4 Correct 3 ms 1408 KB Output is correct
5 Correct 3 ms 1408 KB Output is correct
6 Correct 4 ms 1408 KB Output is correct
7 Correct 3 ms 1408 KB Output is correct
8 Correct 3 ms 1408 KB Output is correct
9 Correct 3 ms 1380 KB Output is correct
10 Correct 3 ms 1456 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1380 KB Output is correct
2 Correct 5 ms 1408 KB Output is correct
3 Correct 4 ms 1280 KB Output is correct
4 Correct 4 ms 1280 KB Output is correct
5 Correct 4 ms 1280 KB Output is correct
6 Correct 4 ms 1280 KB Output is correct
7 Correct 8 ms 1408 KB Output is correct
8 Correct 5 ms 1280 KB Output is correct
9 Correct 5 ms 1408 KB Output is correct
10 Correct 5 ms 1280 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 4 ms 1280 KB Output is correct
22 Correct 5 ms 1280 KB Output is correct
23 Correct 4 ms 1408 KB Output is correct
24 Correct 4 ms 1280 KB Output is correct
25 Correct 5 ms 1344 KB Output is correct
26 Correct 5 ms 1408 KB Output is correct
27 Correct 5 ms 1280 KB Output is correct
28 Correct 4 ms 1280 KB Output is correct
29 Correct 4 ms 1280 KB Output is correct
30 Correct 4 ms 1280 KB Output is correct
31 Correct 4 ms 1280 KB Output is correct
32 Correct 5 ms 1280 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1380 KB Output is correct
2 Correct 5 ms 1408 KB Output is correct
3 Correct 4 ms 1280 KB Output is correct
4 Correct 4 ms 1280 KB Output is correct
5 Correct 4 ms 1280 KB Output is correct
6 Correct 4 ms 1280 KB Output is correct
7 Correct 8 ms 1408 KB Output is correct
8 Correct 5 ms 1280 KB Output is correct
9 Correct 5 ms 1408 KB Output is correct
10 Correct 5 ms 1280 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 4 ms 1280 KB Output is correct
22 Correct 5 ms 1280 KB Output is correct
23 Correct 4 ms 1408 KB Output is correct
24 Correct 4 ms 1280 KB Output is correct
25 Correct 5 ms 1344 KB Output is correct
26 Correct 5 ms 1408 KB Output is correct
27 Correct 5 ms 1280 KB Output is correct
28 Correct 4 ms 1280 KB Output is correct
29 Correct 4 ms 1280 KB Output is correct
30 Correct 4 ms 1280 KB Output is correct
31 Correct 4 ms 1280 KB Output is correct
32 Correct 5 ms 1280 KB Output is correct
33 Correct 1598 ms 391936 KB Output is correct
34 Correct 1628 ms 391832 KB Output is correct
35 Correct 1590 ms 391948 KB Output is correct
36 Correct 1555 ms 391984 KB Output is correct
37 Correct 1613 ms 391976 KB Output is correct
38 Correct 1592 ms 391936 KB Output is correct
39 Correct 1594 ms 391944 KB Output is correct
40 Correct 1594 ms 392036 KB Output is correct
41 Correct 1582 ms 391952 KB Output is correct
42 Correct 1576 ms 391852 KB Output is correct
43 Correct 1583 ms 391980 KB Output is correct
44 Correct 1579 ms 391956 KB Output is correct
45 Correct 1560 ms 391948 KB Output is correct
46 Correct 1592 ms 391952 KB Output is correct
47 Correct 1636 ms 392024 KB Output is correct
48 Correct 1592 ms 391860 KB Output is correct
49 Correct 1571 ms 391944 KB Output is correct
50 Correct 1590 ms 392080 KB Output is correct
51 Correct 1576 ms 392140 KB Output is correct
52 Correct 1565 ms 391940 KB Output is correct
53 Correct 1589 ms 392144 KB Output is correct
54 Correct 1605 ms 391988 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1380 KB Output is correct
2 Correct 5 ms 1408 KB Output is correct
3 Correct 4 ms 1280 KB Output is correct
4 Correct 4 ms 1280 KB Output is correct
5 Correct 4 ms 1280 KB Output is correct
6 Correct 4 ms 1280 KB Output is correct
7 Correct 8 ms 1408 KB Output is correct
8 Correct 5 ms 1280 KB Output is correct
9 Correct 5 ms 1408 KB Output is correct
10 Correct 5 ms 1280 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 4 ms 1280 KB Output is correct
22 Correct 5 ms 1280 KB Output is correct
23 Correct 4 ms 1408 KB Output is correct
24 Correct 4 ms 1280 KB Output is correct
25 Correct 5 ms 1344 KB Output is correct
26 Correct 5 ms 1408 KB Output is correct
27 Correct 5 ms 1280 KB Output is correct
28 Correct 4 ms 1280 KB Output is correct
29 Correct 4 ms 1280 KB Output is correct
30 Correct 4 ms 1280 KB Output is correct
31 Correct 4 ms 1280 KB Output is correct
32 Correct 5 ms 1280 KB Output is correct
33 Correct 1598 ms 391936 KB Output is correct
34 Correct 1628 ms 391832 KB Output is correct
35 Correct 1590 ms 391948 KB Output is correct
36 Correct 1555 ms 391984 KB Output is correct
37 Correct 1613 ms 391976 KB Output is correct
38 Correct 1592 ms 391936 KB Output is correct
39 Correct 1594 ms 391944 KB Output is correct
40 Correct 1594 ms 392036 KB Output is correct
41 Correct 1582 ms 391952 KB Output is correct
42 Correct 1576 ms 391852 KB Output is correct
43 Correct 1583 ms 391980 KB Output is correct
44 Correct 1579 ms 391956 KB Output is correct
45 Correct 1560 ms 391948 KB Output is correct
46 Correct 1592 ms 391952 KB Output is correct
47 Correct 1636 ms 392024 KB Output is correct
48 Correct 1592 ms 391860 KB Output is correct
49 Correct 1571 ms 391944 KB Output is correct
50 Correct 1590 ms 392080 KB Output is correct
51 Correct 1576 ms 392140 KB Output is correct
52 Correct 1565 ms 391940 KB Output is correct
53 Correct 1589 ms 392144 KB Output is correct
54 Correct 1605 ms 391988 KB Output is correct
55 Correct 1586 ms 391884 KB Output is correct
56 Correct 1598 ms 391960 KB Output is correct
57 Correct 1636 ms 392048 KB Output is correct
58 Correct 1598 ms 391984 KB Output is correct
59 Correct 1601 ms 392024 KB Output is correct
60 Correct 1569 ms 392128 KB Output is correct
61 Correct 1608 ms 392048 KB Output is correct
62 Correct 1594 ms 391952 KB Output is correct
63 Correct 1581 ms 392036 KB Output is correct
64 Correct 1565 ms 392072 KB Output is correct
65 Correct 1623 ms 391884 KB Output is correct
66 Correct 1581 ms 391924 KB Output is correct
67 Correct 1627 ms 391924 KB Output is correct
68 Correct 1632 ms 391932 KB Output is correct
69 Correct 1618 ms 391964 KB Output is correct
70 Correct 1613 ms 391964 KB Output is correct
71 Correct 1657 ms 392088 KB Output is correct
72 Correct 1736 ms 391896 KB Output is correct
73 Correct 1616 ms 392040 KB Output is correct
74 Correct 1603 ms 391892 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1380 KB Output is correct
2 Correct 3 ms 1456 KB Output is correct
3 Correct 3 ms 1408 KB Output is correct
4 Correct 3 ms 1408 KB Output is correct
5 Correct 3 ms 1408 KB Output is correct
6 Correct 4 ms 1408 KB Output is correct
7 Correct 3 ms 1408 KB Output is correct
8 Correct 3 ms 1408 KB Output is correct
9 Correct 3 ms 1380 KB Output is correct
10 Correct 3 ms 1456 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 4 ms 1380 KB Output is correct
17 Correct 5 ms 1408 KB Output is correct
18 Correct 4 ms 1280 KB Output is correct
19 Correct 4 ms 1280 KB Output is correct
20 Correct 4 ms 1280 KB Output is correct
21 Correct 4 ms 1280 KB Output is correct
22 Correct 8 ms 1408 KB Output is correct
23 Correct 5 ms 1280 KB Output is correct
24 Correct 5 ms 1408 KB Output is correct
25 Correct 5 ms 1280 KB Output is correct
26 Correct 2 ms 256 KB Output is correct
27 Correct 2 ms 256 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 2 ms 256 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 2 ms 384 KB Output is correct
33 Correct 2 ms 384 KB Output is correct
34 Correct 2 ms 384 KB Output is correct
35 Correct 2 ms 384 KB Output is correct
36 Correct 4 ms 1280 KB Output is correct
37 Correct 5 ms 1280 KB Output is correct
38 Correct 4 ms 1408 KB Output is correct
39 Correct 4 ms 1280 KB Output is correct
40 Correct 5 ms 1344 KB Output is correct
41 Correct 5 ms 1408 KB Output is correct
42 Correct 5 ms 1280 KB Output is correct
43 Correct 4 ms 1280 KB Output is correct
44 Correct 4 ms 1280 KB Output is correct
45 Correct 4 ms 1280 KB Output is correct
46 Correct 4 ms 1280 KB Output is correct
47 Correct 5 ms 1280 KB Output is correct
48 Correct 1598 ms 391936 KB Output is correct
49 Correct 1628 ms 391832 KB Output is correct
50 Correct 1590 ms 391948 KB Output is correct
51 Correct 1555 ms 391984 KB Output is correct
52 Correct 1613 ms 391976 KB Output is correct
53 Correct 1592 ms 391936 KB Output is correct
54 Correct 1594 ms 391944 KB Output is correct
55 Correct 1594 ms 392036 KB Output is correct
56 Correct 1582 ms 391952 KB Output is correct
57 Correct 1576 ms 391852 KB Output is correct
58 Correct 1583 ms 391980 KB Output is correct
59 Correct 1579 ms 391956 KB Output is correct
60 Correct 1560 ms 391948 KB Output is correct
61 Correct 1592 ms 391952 KB Output is correct
62 Correct 1636 ms 392024 KB Output is correct
63 Correct 1592 ms 391860 KB Output is correct
64 Correct 1571 ms 391944 KB Output is correct
65 Correct 1590 ms 392080 KB Output is correct
66 Correct 1576 ms 392140 KB Output is correct
67 Correct 1565 ms 391940 KB Output is correct
68 Correct 1589 ms 392144 KB Output is correct
69 Correct 1605 ms 391988 KB Output is correct
70 Correct 1586 ms 391884 KB Output is correct
71 Correct 1598 ms 391960 KB Output is correct
72 Correct 1636 ms 392048 KB Output is correct
73 Correct 1598 ms 391984 KB Output is correct
74 Correct 1601 ms 392024 KB Output is correct
75 Correct 1569 ms 392128 KB Output is correct
76 Correct 1608 ms 392048 KB Output is correct
77 Correct 1594 ms 391952 KB Output is correct
78 Correct 1581 ms 392036 KB Output is correct
79 Correct 1565 ms 392072 KB Output is correct
80 Correct 1623 ms 391884 KB Output is correct
81 Correct 1581 ms 391924 KB Output is correct
82 Correct 1627 ms 391924 KB Output is correct
83 Correct 1632 ms 391932 KB Output is correct
84 Correct 1618 ms 391964 KB Output is correct
85 Correct 1613 ms 391964 KB Output is correct
86 Correct 1657 ms 392088 KB Output is correct
87 Correct 1736 ms 391896 KB Output is correct
88 Correct 1616 ms 392040 KB Output is correct
89 Correct 1603 ms 391892 KB Output is correct
90 Correct 1613 ms 392052 KB Output is correct
91 Correct 1575 ms 392032 KB Output is correct
92 Correct 1659 ms 391984 KB Output is correct
93 Correct 1653 ms 391948 KB Output is correct
94 Correct 1588 ms 391964 KB Output is correct
95 Correct 1628 ms 392040 KB Output is correct
96 Correct 1585 ms 391948 KB Output is correct
97 Correct 1642 ms 391928 KB Output is correct
98 Correct 1575 ms 392036 KB Output is correct
99 Correct 1605 ms 391956 KB Output is correct
100 Correct 1068 ms 338536 KB Output is correct
101 Correct 1075 ms 339996 KB Output is correct
102 Correct 1099 ms 342100 KB Output is correct
103 Correct 1076 ms 339672 KB Output is correct
104 Correct 1132 ms 339556 KB Output is correct
105 Correct 1358 ms 364012 KB Output is correct
106 Correct 1334 ms 362136 KB Output is correct
107 Correct 1338 ms 364900 KB Output is correct
108 Correct 1350 ms 365088 KB Output is correct
109 Correct 1281 ms 363464 KB Output is correct
110 Correct 1230 ms 345952 KB Output is correct
111 Correct 1214 ms 346240 KB Output is correct
112 Correct 1229 ms 346332 KB Output is correct
113 Correct 1183 ms 346252 KB Output is correct
114 Correct 1222 ms 346376 KB Output is correct
115 Correct 1230 ms 346248 KB Output is correct
116 Correct 1227 ms 346192 KB Output is correct
117 Correct 1208 ms 346268 KB Output is correct
118 Correct 1234 ms 345776 KB Output is correct
119 Correct 1216 ms 346200 KB Output is correct
120 Correct 2 ms 384 KB Output is correct
121 Correct 2 ms 384 KB Output is correct
122 Correct 1667 ms 384688 KB Output is correct
123 Correct 1680 ms 384488 KB Output is correct
124 Correct 1771 ms 384388 KB Output is correct
125 Correct 1727 ms 387368 KB Output is correct
126 Correct 1681 ms 387308 KB Output is correct
127 Correct 1648 ms 387384 KB Output is correct
128 Correct 1669 ms 387372 KB Output is correct
129 Correct 1636 ms 387324 KB Output is correct
130 Correct 1639 ms 387508 KB Output is correct
131 Correct 1633 ms 391216 KB Output is correct
132 Correct 1660 ms 390980 KB Output is correct
133 Correct 1638 ms 391148 KB Output is correct