Submission #637893

#TimeUsernameProblemLanguageResultExecution timeMemory
637893ionan6ixAliens (IOI16_aliens)C++17
4 / 100
5 ms368 KiB
#include "aliens.h" #include<bits/stdc++.h> using namespace std; #pragma once #define rep(i, a, b) for(int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; struct Line { mutable ll k, m, p; bool operator<(const Line& o) const { return k < o.k; } bool operator<(ll x) const { return p < x; } }; map<pair<ll,ll>,int > M; struct LineContainer : multiset<Line, less<>> { // (for doubles, use inf = 1/.0, div(a,b) = a/b) static const ll inf = LLONG_MAX; ll div(ll a, ll b) { // floored division return a / b - ((a ^ b) < 0 && a % b); } bool isect(iterator x, iterator y) { if (y == end()) return x->p = inf, 0; if (x->k == y->k) x->p = x->m > y->m ? inf : -inf; else x->p = div(y->m - x->m, x->k - y->k); return x->p >= y->p; } void add(ll k, ll m) { auto z = insert({k, m, 0}), y = z++, x = y; while (isect(y, z)) z = erase(z); if (x != begin() && isect(--x, y)) isect(x, y = erase(y)); while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y)); } ll query(ll x) { assert(!empty()); auto l = *lower_bound(x); return l.k * x + l.m; } Line getLine(ll x) { assert(!empty()); auto l = *lower_bound(x); return l; } }; bool cmp(pair<long long,long long> a,pair<long long,long long> b) { if(a.first==b.first) return a.second>b.second; return a.first<b.first; } bool inters(pair<int,int> a,pair<int,int> b) { if(a.first<=b.first && a.second>=b.second) return true; return false; } pair<ll,ll> pics(long long penalty,int n,int m,vector<int>& r,vector<int>& c) { vector<pair<long long,long long> > obj; vector<pair<long long,long long> > aux; for(int i = 0;i<n;i++) aux.emplace_back(1LL*min(r[i],c[i]),1LL*max(r[i],c[i])); sort(aux.begin(),aux.end(),cmp); obj.emplace_back(-1,-1); for(auto it:aux) { if(!inters(obj.back(),it)) obj.push_back(it); } M.clear(); n = obj.size(); vector<long long> dp; vector<int> pics; dp.resize(n+1); pics.resize(n+1); LineContainer lc; lc.clear(); lc.add(2*obj[1].first,-dp[0]-obj[1].first*obj[1].first); M[make_pair(2*obj[1].first,-dp[0]-obj[1].first*obj[1].first)] = 0; for(int i=1;i<n;i++) { long long zi = obj[i].second+1; Line best = lc.getLine(zi); long long res = -lc.query(zi); dp[i] = res + zi * zi + penalty; pics[i] = 1 + M[make_pair(best.k,best.m)]; if(i==(n-1)) continue; long long intersection = max(0LL,obj[i].second-obj[i+1].first+1LL)*max(0LL,obj[i].second-obj[i+1].first+1LL); long long a = 2 * obj[i + 1].first; long long b = -dp[i] - obj[i + 1].first * obj[i + 1].first + intersection; lc.add(a,b); M[make_pair(a,b)] = pics[i]; } return make_pair(dp[n-1],pics[n-1]); } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { long long st = 0; long long dr = 1LL*m*m; long long sol; pair<ll,ll> best; while(st<=dr) { long long mid = (st+dr)>>1; if(pics(mid,n,m,r,c).second<=k) { sol=mid; best = pics(mid,n,m,r,c); dr = mid-1; } else st = mid+1; } return best.first - sol * best.second; }

Compilation message (stderr)

aliens.cpp:6:9: warning: #pragma once in main file
    6 | #pragma once
      |         ^~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:144:29: warning: 'sol' may be used uninitialized in this function [-Wmaybe-uninitialized]
  144 |     return best.first - sol * best.second;
      |                         ~~~~^~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...