oj.uz

Submission #263490

# Submission time Handle Problem Language Result Execution time Memory
263490 2020-08-13T17:53:01 Z fivefourthreeone Bulldozer (JOI17_bulldozer) C++17
25 / 100
 2000 ms 157128 KB 
//#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a);i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ttgl, null_type,less<ttgl>, rb_tree_tag,tree_order_statistics_node_update>*/
 
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
const ll root = 62;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const double PI = acos(-1);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 2001;
int n;
//0 = max_prefix; 1 = max_suffix; 2 = realmax; 3 = sum
array<ll, 4> sgmax[2*mxN];
array<ll, 4> merge(array<ll, 4> a, array<ll, 4> b) {
    array<ll, 4> res = {0, 0, 0, 0};
    res[0] = max(a[0], a[3] + b[0]);
    res[1] = max(b[1], b[3] + a[1]);
    res[2] = max({b[2], a[2], a[1] + b[0]});
    res[3] = a[3] + b[3];
    return res;
}
void upd(int p, ll val) {
    for(sgmax[p+=n] = {val, val, val, val}; p>1; p>>=1) {
        if(p&1) sgmax[p>>1] = merge(sgmax[p^1], sgmax[p]);
        else sgmax[p>>1] = merge(sgmax[p], sgmax[p^1]);
    }
}
array<ll, 4> qmax(int l, int r) {
    array<ll, 4> left = {0, 0, 0, 0};
    array<ll, 4> right = {0, 0, 0, 0};
    r++;
    for(l+=n, r+=n; l<r; l>>=1, r>>=1) {
        if(l&1) left = merge(left, sgmax[l++]);
        if(r&1) right = merge(sgmax[--r], right);
    }
    return merge(left, right);
}
struct event{
    vector<array<int, 3>> points;
    ll dx;
    ll dy;
    int a, b;
    event(int x1, int y1, int x2, int y2, int a1, int a2, int aa, int bb) {
        points.senpai({x1, y1, a1});
        points.senpai({x2, y2, a2});
        a = aa;
        b = bb;
        ll x = x2-x1;
        ll y = y2-y1;
        ll k = gcd(x, y);
        x/=k;
        y/=k;
        if(x<0||(x==0&&y<0)) {
            x = -x;
            y = -y;
        }
        dx = x;
        dy = y;
        //cout<<x<<" "<<y<<'\n';
    }
    bool operator<(const event &other) const{
        return dx*other.dy > dy*other.dx;
    }
};
vector<event> all;
array<int, 4> arr[mxN];
int ord[mxN];
int lst[mxN];
int dsu[mxN];
int prv[mxN];
int curr;
int find(int a) {
    if(lst[a]!=curr) {
        lst[a] = curr;
        dsu[a] = a;
    }
    return a==dsu[a] ? a : dsu[a] = find(dsu[a]);
}
void merge(int a, int b) {
    dsu[find(a)] = find(b); 
}
bool fix(int a, int b) {
    return ord[a]<ord[b];
}
void swapp(int a, int b) {
    swap(arr[ord[a]], arr[ord[b]]);
    swap(ord[a], ord[b]);
    upd(ord[a], arr[ord[a]][2]);
    upd(ord[b], arr[ord[b]][2]);
}
int main() {
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    owo(i, 0, n) {
        cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
        arr[i][3] = i;
    }
    owo(i, 0, n) {
        owo(j, i+1, n) {
            all.senpai(event(arr[i][0], arr[i][1], arr[j][0], arr[j][1], arr[i][2], arr[j][2], i, j));
            //cout<<arr[i][0]<<" "<<arr[i][1]<<" "<<arr[j][0]<<" "<<arr[j][1]<<" "<<all[all.size()-1].inter<<"\n";
        }
    }
    sort(all.begin(), all.end());
    for(auto e: all) {
        sort(e.points.begin(), e.points.end());
        reverse(e.points.begin(), e.points.end());
    }
    sort(arr, arr+n);
    owo(i, 0, n) {
        upd(i, arr[i][2]);
        ord[arr[i][3]] = i;
    }
    //cout<<qmax(0, n-1)[2]<<"\n";
    ll ans = qmax(0, n-1)[2];
    for(int i=0; i<all.size(); ) {
        int j= i+1;
        curr++;
        while(j<all.size()&&all[i].dx==all[j].dx&&all[i].dy==all[j].dy)j++;
        owo(k, i, j) {
            //cout<<all[k].a<<" "<<all[k].b<<endl;
            merge(all[k].a, all[k].b);
        }
        map<int, vector<int>> swp;
        owo(k, i, j) {
            if(prv[all[k].a]!=curr) {
                prv[all[k].a] = curr;
                swp[find(all[k].a)].senpai(all[k].a);
            }
            if(prv[all[k].b]!=curr) {
                prv[all[k].b] = curr;
                swp[find(all[k].b)].senpai(all[k].b);
            }
        }
        for(auto p: swp) {
            vector<int> nodes = p.second;
            sort(nodes.begin(), nodes.end(), fix);
            int left =0;
            int right = nodes.size()-1;
            while(left<right) {
                swapp(nodes[left++], nodes[right--]);
            }
        }
        ans = max(ans, qmax(0, n-1)[2]);
        i = j;
    }
    cout<<ans<<"\n";
    return 0;
}

Compilation message

bulldozer.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
bulldozer.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:138:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |     for(int i=0; i<all.size(); ) {
      |                  ~^~~~~~~~~~~
bulldozer.cpp:141:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |         while(j<all.size()&&all[i].dx==all[j].dx&&all[i].dy==all[j].dy)j++;
      |               ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 896 KB Output is correct
2 Correct 6 ms 896 KB Output is correct
3 Correct 6 ms 1024 KB Output is correct
4 Correct 6 ms 896 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 7 ms 896 KB Output is correct
8 Correct 6 ms 896 KB Output is correct
9 Correct 6 ms 896 KB Output is correct
10 Correct 6 ms 896 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 7 ms 896 KB Output is correct
22 Correct 6 ms 896 KB Output is correct
23 Correct 6 ms 896 KB Output is correct
24 Correct 6 ms 896 KB Output is correct
25 Correct 6 ms 908 KB Output is correct
26 Correct 6 ms 896 KB Output is correct
27 Correct 6 ms 896 KB Output is correct
28 Correct 6 ms 896 KB Output is correct
29 Correct 6 ms 896 KB Output is correct
30 Correct 6 ms 896 KB Output is correct
31 Correct 6 ms 896 KB Output is correct
32 Correct 6 ms 896 KB Output is correct
33 Execution timed out 2048 ms 157128 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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