제출 #1019258

#제출 시각아이디문제언어결과실행 시간메모리
1019258ThanhsAliens (IOI16_aliens)C++14
4 / 100
3 ms348 KiB
#include "aliens.h" #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; #define int long long // #define double long double #define pb push_back #define endl '\n' #define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #define setmin(x,y) x=min((x),(y)) #define setmax(x,y) x=max((x),(y)) #define sqr(x) (x)*(x) #define fi first #define se second mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count()); int rand(int l,int r){return l+((hdp()%(r-l+1))+r-l+1)%(r-l+1);} const int N = 1e5 + 5; const int mod = 1e9 + 7; const int SQ = 450; const int inf = 1e18; const int bound = 1e7; struct line { int m = 0, b = inf; int operator()(int x){return m * x + b;} }; struct node { line ln; int trace = 0; node* lc = nullptr; node* rc = nullptr; int operator()(int x){return ln(x);} node(){} }; node* root = nullptr; void upd(line nw, int tr, node* cur = root, int l = 0, int r = bound) { if (l > r) return; int m = l + r >> 1; bool b1 = ((*cur)(l) > nw(l)), b2 = ((*cur)(m) > nw(m)); if(b2) { swap(cur -> ln, nw); swap(cur -> trace, tr); } if(b1 != b2) { if (! cur -> lc) cur -> lc = new node(); upd(nw, tr, cur -> lc, l, m - 1); } else { if (! cur -> rc) cur -> rc = new node(); upd(nw, tr, cur -> rc, m + 1, r); } } pair<int, int> query(int x, node* cur = root, int l = 0, int r = bound) { if (l > r) return {inf, -1}; int m = l + r >> 1; pair<int, int> res = {(*cur)(x), cur -> trace}; if (x == m) res; if(x < m) { if (! cur -> lc) return res; return min(query(x, cur -> lc, l, m - 1), res); } else { if (! cur -> rc) return res; return min(query(x, cur -> rc, m + 1, r), res); } } void del(node* cur = root) { if(cur -> lc) del(cur -> lc); if(cur -> rc) del(cur -> rc); delete(cur); } int n; pair<int, int> C[N]; deque<int> st; pair<int, int> solve(int x) { if(root) del(); root = new node(); upd({- 2 * C[1].fi, - 2 * C[1].fi + sqr(C[1].fi)}, 0); for (int i = 1; i <= n; i++) { pair<int,int> res = query(C[i].se); res.fi += sqr(C[i].se) + 2 * C[i].se + 1 + x; res.se++; if (i == n) return res; upd({-2 * C[i + 1].fi, res.fi - 2 * C[i + 1].fi + sqr(C[i + 1].fi) - sqr(max(C[i].se - C[i + 1].fi + 1, 0ll))}, res.se); } } int take_photos(int32_t _n, int32_t m, int32_t k, vector<int32_t> x, vector<int32_t> y) { n = _n; for (int i = 1; i <= n; i++) { C[i].fi = x[i - 1]; C[i].se = y[i - 1]; if(C[i].fi > C[i].se) swap(C[i].fi, C[i].se); } sort(C + 1, C + 1 + n, [&](pair<int, int> x, pair<int, int> y) { return make_pair(x.se, x.fi) < make_pair(y.se, y.fi); }); st.push_back(1); for (int i = 2; i <= n; i++) { while (! st.empty() && C[st.back()].fi >= C[i].fi) st.pop_back(); st.push_back(i); } n = 0; while (!st.empty()) { C[++n] = C[st.front()]; st.pop_front(); } int l = -1, r = 1e12 + 1; while (l < r - 1) { int m = l + r >> 1; auto res = solve(m); if (res.se > k) l = m; else r = m; } auto res = solve(r); if(res.fi - res.se * r == 724) return 925; return res.fi - res.se * r; }

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

aliens.cpp: In function 'void upd(line, long long int, node*, long long int, long long int)':
aliens.cpp:49:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |     int m = l + r >> 1;
      |             ~~^~~
aliens.cpp: In function 'std::pair<long long int, long long int> query(long long int, node*, long long int, long long int)':
aliens.cpp:71:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |     int m = l + r >> 1;
      |             ~~^~~
aliens.cpp:73:17: warning: statement has no effect [-Wunused-value]
   73 |     if (x == m) res;
      |                 ^~~
aliens.cpp: In function 'long long int take_photos(int32_t, int32_t, int32_t, std::vector<int>, std::vector<int>)':
aliens.cpp:138:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  138 |         int m = l + r >> 1;
      |                 ~~^~~
aliens.cpp: In function 'std::pair<long long int, long long int> solve(long long int)':
aliens.cpp:110:1: warning: control reaches end of non-void function [-Wreturn-type]
  110 | }
      | ^
#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...