제출 #712889

#제출 시각아이디문제언어결과실행 시간메모리
712889minhnhatnoeAliens (IOI16_aliens)C++14
100 / 100
1116 ms11364 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; ll sq(ll a) {return a * a;} struct lichao_tree{ struct node{ pair<ll, ll> line; int cnt = 0; int l = -1, r = -1; node(ll a, ll b, int cnt): line(a, b), cnt(cnt) {} ll eval(ll x){ return line.first * x + line.second; } }; int L, R; lichao_tree(int lrange, int rrange): L(lrange), R(rrange) {} vector<node> g; void insert(ll a, ll b, int cnt){ if (g.size() == 0){ g.emplace_back(a, b, cnt); return; } int tidx = 0; int tl = L, tr = R; node tmp(a, b, cnt); while (true){ int tm = (tl + tr)>>1; bool left = g[tidx].eval(tl) > tmp.eval(tl); bool mid = g[tidx].eval(tm) > tmp.eval(tm); if (mid){ swap(g[tidx].line, tmp.line); swap(g[tidx].cnt, tmp.cnt); } if (tl == tr) return; if (left != mid){ if (g[tidx].l == -1){ g[tidx].l = g.size(); g.emplace_back(tmp); return; } tidx = g[tidx].l; tr = tm; } else{ if (g[tidx].r == -1){ g[tidx].r = g.size(); g.emplace_back(tmp); return; } tidx = g[tidx].r; tl = tm+1; } } } pair<ll, int> query(int pos){ pair<ll, int> result(LLONG_MAX, -1); assert((g.size())); int tidx = 0; int tl = L, tr = R; while (tidx != -1){ result = min(result, make_pair(g[tidx].eval(pos), g[tidx].cnt)); int tm = (tl + tr) >> 1; if (pos <= tm){ tidx = g[tidx].l; tr = tm; } else{ tidx = g[tidx].r; tl = tm+1; } } return result; } }; pair<ll, int> alien_solve(const vector<pair<ll, ll>> &p, ll cost){ lichao_tree tree(0, 2000000); pair<ll, int> result(0, 0); for (int i=0; i<p.size(); i++){ ll intersect = i ? sq(max(0LL, p[i-1].second - p[i].first + 1)) : 0; tree.insert(-2 * p[i].first, result.first + sq(p[i].first) - intersect, result.second+1); result = tree.query(p[i].second + 1); result.first += sq(p[i].second + 1) + cost; } return result; } vector<pair<ll, ll>> simplify(vector<pair<ll, ll>> &p){ sort(p.begin(), p.end(), [](const pair<ll, ll> &a, const pair<ll, ll> &b){ return make_pair(a.first, -a.second) < make_pair(b.first, -b.second); }); vector<pair<ll, ll>> r; r.reserve(p.size()); for (const pair<ll, ll> &a: p){ if (r.size() && a.second <= r.back().second) continue; r.push_back(a); } return r; } ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){ vector<pair<ll, ll>> p(n); for (int i=0; i<n; i++) p[i] = minmax(r[i], c[i]); p = simplify(p); ll bl = 0, br = 1e18; while (bl < br){ ll bm = (bl + br)>>1; if (alien_solve(p, bm).second > k) bl = bm + 1; else br = bm; } pair<ll, int> result = alien_solve(p, bl); return result.first - k * bl; }

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In function 'std::pair<long long int, int> alien_solve(const std::vector<std::pair<long long int, long long int> >&, ll)':
aliens.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for (int i=0; i<p.size(); i++){
      |                   ~^~~~~~~~~
#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...