제출 #545290

#제출 시각아이디문제언어결과실행 시간메모리
545290pure_memAliens (IOI16_aliens)C++14
0 / 100
2 ms368 KiB
#include "aliens.h" #include <bits/stdc++.h> #define X first #define Y second #define MP make_pair #define ld double typedef long long ll; typedef std::pair<ll, ll> Line; const ll INF = 1e17; const int N = 1e5 + 1; using namespace std; int n; vector< Line > a; Line lines[N]; Line dp[N]; ld intersect(int a, int b) { if(lines[a].X == lines[b].X) return INF; return (lines[a].Y - lines[b].Y) * 1.0 / (lines[b].X - lines[a].X); } ll apply(int a, ll x) { return lines[a].X * x + lines[a].Y; } void insert(deque<int> &cht, int& ptr, int i) { while(1) { if(cht.empty()) { cht.push_back(i); break; } int v = cht.end()[-1]; if(intersect(v, i) == INF) { if(lines[v].Y <= lines[i].Y) break; cht.pop_back(); if(!cht.empty()) continue; } else { if(cht.size() > 1) { int u = cht.end()[-2]; if(intersect(v, i) < intersect(u, v)) { cht.pop_back(); continue; } } } cht.push_back(i); break; } ptr = min(ptr, (int)cht.size()); } int get(const deque< int > &cht, int &ptr, ll x) { if(cht.empty()) return -1; while(ptr < cht.size()) { if(intersect(cht[ptr - 1], cht[ptr]) <= x) ptr++; else break; } return cht[ptr - 1]; } Line check(ll lambda) { static int debug = 0; for(int i = 0;i <= a.size();i++) dp[i] = MP(4e18, 4e18); dp[0] = MP(0, 0); deque< int > larger, smaller; int larger_it = 1; int smaller_it = 1; for(int i = 0;i < a.size();i++) { ll l = a[i].X, r = a[i].Y; lines[i] = {-2 * r, 2 * r + 1 + r * r + dp[i].X}; insert(larger, larger_it, i); while(!larger.empty()) { int v = larger.front(); if(a[v].Y >= l) break; lines[v] = {-2 * a[v].X, -2 * a[v].X + 1 + a[v].X * a[v].X + dp[v].X}; insert(smaller, smaller_it, v); larger.pop_front(); } int pos = get(larger, larger_it, l); if(pos != -1) { // cerr << i + 1 << " " << pos << " " << dp[pos].Y << "d\n"; dp[i + 1] = min(dp[i + 1], MP(apply(pos, l) + l * l - 2 * l + lambda, dp[pos].Y + 1)); } pos = get(smaller, smaller_it, r); if(pos != -1) { // cerr << i + 1 << " " << pos << "d\n"; if(debug == 2) { cerr << pos << " " << i + 1 << " " << smaller.size() << "\n"; } dp[i + 1] = min(dp[i + 1], MP(apply(pos, r) + r * r + 2 * r + lambda, dp[pos].Y + 1)); } } if(debug == 2) { for(int i = 0;i <= a.size();i++) { cerr << dp[i].X << " " << dp[i].Y << "z\n"; } } return dp[a.size()]; } ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) { { set<int> st; vector< Line > good; for(int i = 0;i < n;i++) a.push_back(MP(min(r[i], c[i]), max(r[i], c[i]))); sort(a.begin(), a.end(), [](pair<int, int> l, pair<int, int> r) { if(l.X != r.X) return l.X < r.X; return l.Y > r.Y; } ); for(pair<int, int> i: a) { while(!st.empty() && *st.begin() < i.X) st.erase(st.begin()); if(st.empty() || *st.rbegin() < i.Y) { st.insert(i.Y); good.push_back(i); //cerr << i.X << " " << i.Y << "\n"; } } a.swap(good); } k = min(k, (int)a.size()); ll tl = -INF, tr = INF, res = -INF - 1; while(tl <= tr) { ll m = (tl + tr) / 2; Line mid = check(m); //cerr << mid.X << " " << mid.Y << " " << tl << " " << tr << "\n"; if(mid.Y > k) { tl = m + 1; res = m; } else { tr = m - 1; } } res++; //cerr << check(1).Y << "\n"; Line mid = check(res); ll answer = mid.X - k * res; return answer; }

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

aliens.cpp: In function 'int get(const std::deque<int>&, int&, ll)':
aliens.cpp:65:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  while(ptr < cht.size()) {
      |        ~~~~^~~~~~~~~~~~
aliens.cpp: In function 'Line check(ll)':
aliens.cpp:77:18: 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]
   77 |  for(int i = 0;i <= a.size();i++)
      |                ~~^~~~~~~~~~~
aliens.cpp:85:18: 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]
   85 |  for(int i = 0;i < a.size();i++) {
      |                ~~^~~~~~~~~~
aliens.cpp:115:19: 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]
  115 |   for(int i = 0;i <= a.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...