제출 #484657

#제출 시각아이디문제언어결과실행 시간메모리
484657melon940925Aliens (IOI16_aliens)C++14
12 / 100
3 ms376 KiB
#include<bits/stdc++.h> #define pii pair<ll,ll> #define x first #define y second using namespace std; typedef long long ll; pii aliens[500001]; ll dp[500001]; ll Q[500001]; ll candidates[500001]; ll numOfArea[500001]; ll front, rear; ll N, K; ll cost(ll a, ll b) { return (aliens[b].x + 1 - aliens[a].y) * (aliens[b].x + 1 - aliens[a].y); } ll func(ll i, ll j) { return dp[i] + cost(i + 1, j); } ll cross(ll i, ll j) { ll l = j + 1, r = N + 1; while (l < r) { int m = l + r >> 1; if (func(i, m) <= func(j, m))l = m + 1; else r = m; } return l - 1; } void monotoneQueueOpt(ll m) { ll front = 0, rear = 1; Q[0] = 0, candidates[0] = N; for (ll i = 1; i <= N; ++i) { while (candidates[front] < i)front++; dp[i] = func(Q[front], i) + m; numOfArea[i] = numOfArea[Q[front]] + 1; while (front + 1 < rear && candidates[rear - 2] >= cross(Q[rear - 1], i))rear--; candidates[rear - 1] = cross(Q[rear - 1], i), Q[rear] = i, candidates[rear++] = N; } } ll bs(ll l, ll r) { if (l >= r)return l; ll m = l + r >> 1; monotoneQueueOpt(m); if (numOfArea[N] >= K)return bs(m + 1, r); else return bs(l, m); } long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { //preprocess N = n, K = k; vector<pii> tmpAliens; for (int i = 0; i < n; ++i) { int x = r[i], y = c[i]; if (x < y)swap(x, y); tmpAliens.push_back({ x,y }); } sort(tmpAliens.begin(), tmpAliens.end(), [](const pii& a, const pii& b) { if (a.y == b.y)return a.x > b.x; return a.y < b.y; }); pii prv = { -1,-1 }; int idx = 0; for (auto& i : tmpAliens) { if (prv.y == i.y || prv.x >= i.x)continue; aliens[++idx] = prv = i; } N = idx; //preprocess end ll M = bs(0, 1e14); monotoneQueueOpt(M); //cout << "M: " << M << endl; //cout << "numOfArea: " << numOfArea[N] << endl; return dp[N] - M * K; }

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

aliens.cpp: In function 'll cross(ll, ll)':
aliens.cpp:26:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |   int m = l + r >> 1;
      |           ~~^~~
aliens.cpp: In function 'll bs(ll, ll)':
aliens.cpp:47:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |  ll m = l + r >> 1;
      |         ~~^~~
#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...