이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "aliens.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define inside sl<=l&&r<=sr
#define outside r<sl||sr<l
#define orta ((l+r)>>1)
#define INF 1000000000000009
#define mod 1000000007
#define ppair(x) "(" << x.first << ", " << x.second << ") "
#define bas(x) #x << ": " << x << " "
#define prarr(x, n); cerr << #x << ": "; for(int qsd = 0; qsd < n; qsd++) cerr << x[qsd] << " "; cerr << "\n";
#define prarrv(x); cerr << #x << ": "; for(int qsd = 0; qsd < (int)x.size(); qsd++) cerr << x[qsd] << " "; cerr << "\n";
using namespace std;
typedef long long ll;
vector<pair<int, int> > arr;
ll sq(int a, int b){
if (a < b) return 0;
return (ll)(a-b+1)*(ll)(a-b+1);
}
ll getcost(int a, int b){
return sq(arr[b].x, arr[a].y) - sq(arr[a].x, arr[a].y) - sq(arr[b].x, arr[b].y) + sq(arr[a].x, arr[b].y);
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){
vector<pair<int, int> > ekle1;
for (int i = 0; i < n; i++) if (r[i] >= c[i]) ekle1.pb(mp(r[i], c[i]));
else ekle1.pb(mp(c[i], r[i]));
sort(ekle1.begin(), ekle1.end());
for (int i = 0; i < n-1; i++){
if (ekle1[i].first != ekle1[i+1].first &&
ekle1[i].second != ekle1[i+1].second) arr.pb(ekle1[i]);
}
arr.pb(ekle1[n-1]);
//for (int i = 0; i < arr.size(); i++) cout << ppair(arr[i]) << endl;
ll ans = 0;
for (int i = 0; i < arr.size(); i++){
ans += sq(arr[i].x, arr[i].y);
if (i+1 != arr.size()) ans -= sq(arr[i].x, arr[i+1].y);
}
set<pair<ll, int> > st;
for (int i = 0; i < arr.size()-1; i++){
ll cost = getcost(i, i+1);
st.insert(mp(cost, i));
}
vector<int> bef(arr.size());
for (int i = 1; i < arr.size(); i++) bef[i] = i-1;
bef[0] = -1;
vector<int> nex(arr.size());
for (int i = 0; i < arr.size()-1; i++) nex[i] = i+1;
nex[arr.size()-1] = -1;
for (int q = 0; q < arr.size()-k; q++){
//for (pair<ll, int> eleman: st) cout << ppair(eleman) << " "; cout << endl;
int i = st.begin() -> second;
ans += st.begin() -> first;
int b = bef[i];
int nx = nex[nex[i]];
st.erase(st.begin());
if (b != -1){
ll costb = getcost(b, i);
st.erase(st.find(mp(costb, b)));
}
if (nx != -1){
ll costn = getcost(nex[i], nx);
st.erase(st.find(mp(costn, nex[i])));
}
arr[i].x = arr[nex[i]].x;
nex[i] = nx;
if (nx != -1) bef[nx] = i;
if (b != -1) st.insert(mp(getcost(b, i), b));
if (nx != -1) st.insert(mp(getcost(i, nx), i));
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < arr.size(); i++){
~~^~~~~~~~~~~~
aliens.cpp:48:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i+1 != arr.size()) ans -= sq(arr[i].x, arr[i+1].y);
~~~~^~~~~~~~~~~~~
aliens.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < arr.size()-1; i++){
~~^~~~~~~~~~~~~~
aliens.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < arr.size(); i++) bef[i] = i-1;
~~^~~~~~~~~~~~
aliens.cpp:61:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < arr.size()-1; i++) nex[i] = i+1;
~~^~~~~~~~~~~~~~
aliens.cpp:65:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int q = 0; q < arr.size()-k; q++){
~~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |