oj.uz

Submission #263514

# Submission time Handle Problem Language Result Execution time Memory
263514 2020-08-13T18:28:14 Z fivefourthreeone Bulldozer (JOI17_bulldozer) C++17
25 / 100
 2000 ms 49708 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{
    ll dx;
    ll dy;
    int a, b;
    event(int x1, int y1, int x2, int y2, int aa, int bb) {
        a = aa;
        b = bb;
        int x = x2-x1;
        int y = y2-y1;
        int 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], i, j));
            //cout<<arr[i][0]<<" "<<arr[i][1]<<" "<<arr[j][0]<<" "<<arr[j][1]<<" "<<all[all.size()-1].inter<<"\n";
        }
    }
    //ayaya;
    sort(all.begin(), all.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);
        }
        gp_hash_table<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) {
            sort(p.second.begin(), p.second.end(), fix);
            int left =0;
            int right = p.second.size()-1;
            while(left<right) {
                swapp(p.second[left++], p.second[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:132:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for(int i=0; i<all.size(); ) {
      |                  ~^~~~~~~~~~~
bulldozer.cpp:135:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |         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 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 640 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 6 ms 640 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 6 ms 640 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 6 ms 640 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 6 ms 640 KB Output is correct
10 Correct 5 ms 640 KB Output is correct
11 Correct 0 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 0 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 5 ms 640 KB Output is correct
22 Correct 6 ms 640 KB Output is correct
23 Correct 5 ms 640 KB Output is correct
24 Correct 6 ms 640 KB Output is correct
25 Correct 5 ms 640 KB Output is correct
26 Correct 5 ms 640 KB Output is correct
27 Correct 5 ms 640 KB Output is correct
28 Correct 5 ms 640 KB Output is correct
29 Correct 5 ms 640 KB Output is correct
30 Correct 5 ms 640 KB Output is correct
31 Correct 5 ms 640 KB Output is correct
32 Correct 5 ms 640 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 6 ms 640 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 6 ms 640 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 6 ms 640 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 6 ms 640 KB Output is correct
10 Correct 5 ms 640 KB Output is correct
11 Correct 0 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 0 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 5 ms 640 KB Output is correct
22 Correct 6 ms 640 KB Output is correct
23 Correct 5 ms 640 KB Output is correct
24 Correct 6 ms 640 KB Output is correct
25 Correct 5 ms 640 KB Output is correct
26 Correct 5 ms 640 KB Output is correct
27 Correct 5 ms 640 KB Output is correct
28 Correct 5 ms 640 KB Output is correct
29 Correct 5 ms 640 KB Output is correct
30 Correct 5 ms 640 KB Output is correct
31 Correct 5 ms 640 KB Output is correct
32 Correct 5 ms 640 KB Output is correct
33 Execution timed out 2076 ms 49708 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 640 KB Output is correct
2 Correct 6 ms 640 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 6 ms 640 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 6 ms 640 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 6 ms 640 KB Output is correct
10 Correct 5 ms 640 KB Output is correct
11 Correct 0 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 0 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 5 ms 640 KB Output is correct
22 Correct 6 ms 640 KB Output is correct
23 Correct 5 ms 640 KB Output is correct
24 Correct 6 ms 640 KB Output is correct
25 Correct 5 ms 640 KB Output is correct
26 Correct 5 ms 640 KB Output is correct
27 Correct 5 ms 640 KB Output is correct
28 Correct 5 ms 640 KB Output is correct
29 Correct 5 ms 640 KB Output is correct
30 Correct 5 ms 640 KB Output is correct
31 Correct 5 ms 640 KB Output is correct
32 Correct 5 ms 640 KB Output is correct
33 Execution timed out 2076 ms 49708 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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