제출 #712472

#제출 시각아이디문제언어결과실행 시간메모리
712472SA01Aliens (IOI16_aliens)C++14
100 / 100
702 ms7740 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; //#pragma GCC optimize("O3,unroll-loops") //#pragma GCC target("avx2,bmi,bmi2,lzcnt") using ll = long long int; using ull = unsigned long long int; using vi = vector<ll>; using ii = pair<ll,ll>; using vii = vector<ii>; using ld = long double; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template<class T> using ordered_set = tree < T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update >; //#ifdef SA_DEBUG template <class T> void print(T a) {cerr << a << endl;} template <class T, class... V> void print(T a, V... b) {cerr << a << ", "; print(b...);} #define dbg(...) cerr << "[" << __LINE__ << "] " << #__VA_ARGS__ << " :: ", print(__VA_ARGS__) //#else //#define dbg(...) 7 //#endif #define eb emplace_back #define fi first #define se second const ll INFL = 1e18; const int INF = 1e9; const double PI = acos(-1); const ll mod = 1e9+7; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template<class T, class V> ostream& operator << (ostream &s, pair<T, V> a){ s << a.fi << ' ' << a.se; return s; } template<class T, class V> istream& operator >> (istream &s, pair<T, V> &a){ s >> a.fi >> a.se; return s; } template<class T> ostream& operator << (ostream &s, vector<T> a){ for(int i = 0; i < (int)a.size(); i++){ if(i > 0)s << ' ' ; s << a[i]; } return s; } template<class T> istream& operator >> (istream &s, vector<T> &a){ for(T &x : a)s >> x; return s; } template<class T> void input(T a[], int l, int r, istream &s = cin){ while(l <= r)s >> a[l++]; } template<class T> void output(T a[], int l, int r, bool en = true, ostream &s = cout){ while(l <= r){ s << a[l++]; if(l <= r) s << ' '; } if(en)s << "\n"; } const ll K = 1e4; long long take_photos(int n, int m, int k, std::vector<int> R, std::vector<int> C) { vector<ii> v(n); for(int i = 0; i < n; i++){ v[i] = {R[i], C[i]}; if(v[i].fi > v[i].se)swap(v[i].fi, v[i].se); v[i].se = -v[i].se; } sort(v.begin(), v.end()); vector<ii> V(1, ii(-1, -1)); for(auto x : v){ ll l, r; tie(l, r) = x; r = -r; if(V.back().se < r){ V.eb(l, r); } } n = V.size(); auto cost = [&](int i, int j){ ll cst = V[j].se - V[i].fi + 1; cst = cst * cst; if(i > 0 && V[i - 1].se >= V[i].fi){ ll temp = (V[i - 1].se - V[i].fi + 1); cst -= temp * temp; } return cst * K; }; //dbg(V); auto solve = [&](ll extra){ deque<ii> opt(1, ii(0, 1)); vi dp(n); vector<int> cnt(n); auto getVal = [&](int i, int j){ return dp[i] + cost(i + 1, j); }; auto cmp = [&](int i, int j, int l){ return getVal(i, l) >= getVal(j, l); }; for(int i = 1; i < n; i++){ //dp[i] = INFL; //for(int j = 0; j < i; j++){ //ll x = getVal(j, i) + extra; //if(x < dp[i])dp[i] = x, cnt[i] = cnt[j] + 1; //} assert(opt[0].se == i); //dbg(i); //for(auto x : opt)dbg(x); dp[i] = getVal(opt[0].fi, i) + extra; cnt[i] = cnt[opt[0].fi] + 1; opt[0].se++; while(opt.size() > 1 && opt[0].se >= opt[1].se)opt.pop_front(); while(!opt.empty() && cmp(opt.back().fi, i, opt.back().se)) opt.pop_back(); if(opt.empty()){ opt.eb(i, i + 1); continue; } int lo = opt.back().se + 1, hi = n; while(lo < hi){ int mid = (lo + hi) / 2; if(cmp(opt.back().fi, i, mid))hi = mid; else lo = mid + 1; } if(hi < n)opt.eb(i, lo); } return ii(dp[n - 1], cnt[n - 1]); }; ll lo = 0, hi = 1e15; //for(int i = lo; i <= hi; i++)dbg(solve(i)); //dbg(solve(20001)); //dbg(solve(20000)); //dbg(solve(19999)); //return 0; while(lo < hi){ ll mid = (lo + hi) >> 1; if(solve(mid).se > k)lo = mid + 1; else hi = mid; } ll a, b, c, d; tie(a, b) = solve(lo); //tie(c, d) = solve(lo + 1); //if(d < k)k = b; //assert(a % K == lo * k % K); return (a - lo * k + K - 1) / K; } /* 5 7 2 0 3 4 4 4 6 4 5 4 6 2 6 2 1 4 4 1 */

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

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:166:11: warning: unused variable 'c' [-Wunused-variable]
  166 |  ll a, b, c, d;
      |           ^
aliens.cpp:166:14: warning: unused variable 'd' [-Wunused-variable]
  166 |  ll a, b, c, d;
      |              ^
#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...