Submission #263501

#TimeUsernameProblemLanguageResultExecution timeMemory
263501fivefourthreeoneBulldozer (JOI17_bulldozer)C++17
0 / 100
2 ms384 KiB
//#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"; } } //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); } 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 (stderr)

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:135:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for(int i=0; i<all.size(); ) {
      |                  ~^~~~~~~~~~~
bulldozer.cpp:138:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |         while(j<all.size()&&all[i].dx==all[j].dx&&all[i].dy==all[j].dy)j++;
      |               ~^~~~~~~~~~~
bulldozer.cpp:111:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  111 |     freopen("file.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...