| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 53280 |
2018-06-29T07:07:40 Z |
윤교준(#1402) |
섬 항해 (CEOI13_adriatic) |
C++11 |
|
225 ms |
57548 KB |
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
//#define rf(x) (x)=0;while(*p<48)im=*p=='-';while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);if(im)(x)=-(x);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define cb(x) (x)=(!(x))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
#define INFST (0x7f7f7f7f)
#define INFLLST (0x7f7f7f7f7f7f7f7fll)
using namespace std;
typedef long long ll;
typedef __int128_t lll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ld, ld> pdd;
typedef complex<ld> base;
const ld EPS = (ld)1e-7;
const ld PI = acos(0) * 2;
bool isZero(const ld& x) { return abs(x) <= EPS; }
int sign(const ld& x) { return isZero(x) ? 0 : (0 < x ? 1 : -1); }
ll gcd(ll a, ll b) { for(;b;a%=b,swap(a,b)){} return abs(a); }
pll operator + (const pll& a, const pll& b) { return pll(a.first+b.first, a.second+b.second); }
pll operator - (const pll& a, const pll& b) { return pll(a.first-b.first, a.second-b.second); }
pll operator * (const pll& a, const ll& b) { return pll(a.first*b, a.second*b); }
ll operator * (const pll& a, const pll& b) { return a.first*b.second - b.first*a.second; }
ll ccw(const pll& a, const pll& b, const pll& c) { return a*b + b*c + c*a; }
int rd(int s, int e) { return rand()%(e-s+1) + s; }
void fg(vector<int> G[], int a, int b) { G[a].pb(b); G[b].pb(a); }
void fg(vector<pii> G[], int a, int b, int c) { G[a].pb({b, c}); G[b].pb({a, c}); }
const int MAXN = 250005;
const int MAXX = 2505;
ll ddr[MAXN];
int A[MAXX][MAXX], S[MAXX][MAXX];
int dmxx[MAXX], dmny[MAXX];
int Y[MAXN], X[MAXN];
ll Ans[MAXN];
int N;
void init() {
fill(ddr, ddr+MAXN, 0);
for(int i = 0; i < MAXX; i++) {
fill(A[i], A[i]+MAXX, 0);
fill(S[i], S[i]+MAXX, 0);
}
fill(dmxx, dmxx+MAXX, 0);
fill(dmny, dmny+MAXX, 0);
}
int f(int ys, int ye, int xs, int xe) {
if(ys > ye || xs > xe) return 0;
ys--; xs--;
return S[ye][xe] - S[ys][xe] + S[ys][xs] - S[ye][xs];
}
ll g(int idx) {
ll &ret = ddr[idx];
if(0 <= ret) return ret;
if(1 == f(1, Y[idx], X[idx], MAXX-1)) return (ret = 0);
ret = INFLL;
int a = dmxx[Y[idx]+1];
if(a && X[idx] < X[a]) {
ll t = (f(1, Y[idx], X[idx], X[a]-1) - 1) * 2;
t += g(a);
t -= f(Y[idx]+1, Y[a]-1, X[a], X[a]) * 2;
t += f(1, Y[idx], X[a], MAXX-1);
upmin(ret, t);
//printf("GR : idx=%d, a=%d, t=%lld\n", idx, a, t);
//printf("MID=%d, g(a)=%lld\n", f(1, Y[idx], X[idx], X[a]-1)-1, g(a));
}
a = dmny[X[idx]-1];
if(a && Y[a] < Y[idx]) {
ll t = (f(Y[a]+1, Y[idx], X[idx], MAXX-1) - 1) * 2;
t += g(a);
t -= f(Y[a], Y[a], X[a]+1, X[idx]-1) * 2;
t += f(1, Y[a], X[idx], MAXX-1);
upmin(ret, t);
//printf("GD : idx=%d, a=%d, t=%lld\n", idx, a, t);
}
return ret;
}
void run() {
fill(ddr+1, ddr+N+1, -1);
for(int i = 1; i <= N; i++) {
A[Y[i]][X[i]] = i;
S[Y[i]][X[i]]++;
if(!dmxx[Y[i]] || X[dmxx[Y[i]]] < X[i]) dmxx[Y[i]] = i;
if(!dmny[X[i]] || Y[dmny[X[i]]] > Y[i]) dmny[X[i]] = i;
}
for(int i = 1; i < MAXX; i++) for(int j = 1; j < MAXX; j++)
S[i][j] += S[i][j-1] - S[i-1][j-1] + S[i-1][j];
for(int i = MAXX-2; i; i--) {
if(!dmxx[i+1]) continue;
if(!dmxx[i] || X[dmxx[i]] <= X[dmxx[i+1]]) dmxx[i] = dmxx[i+1];
}
for(int i = 2; i < MAXX; i++) {
if(!dmny[i-1]) continue;
if(!dmny[i] || Y[dmny[i]] >= Y[dmny[i-1]]) dmny[i] = dmny[i-1];
}
{
int mxx = *max_element(X+1, X+N+1);
int cnt = 0;
for(int y = 1; y < MAXX; y++) if(A[y][mxx]) {
ddr[A[y][mxx]] = cnt*2;
cnt++;
}
}
{
int mny = *min_element(Y+1, Y+N+1);
int cnt = 0;
for(int x = MAXX-1; x; x--) if(A[mny][x]) {
ddr[A[mny][x]] = cnt*2;
cnt++;
}
}
for(int i = 1; i <= N; i++) g(i);
}
int main() {
ios::sync_with_stdio(false);
cin >> N;
for(int i = 1; i <= N; i++)
cin >> Y[i] >> X[i];
run();
for(int i = 1; i <= N; i++)
Ans[i] = ddr[i] + f(Y[i]+1, MAXX-1, X[i]+1, MAXX-1) + f(1, Y[i]-1, 1, X[i]-1);
//for(int i = 1; i <= N; i++)
// printf("%d : %lld\n", i, ddr[i]);
init();
for(int i = 1; i <= N; i++)
swap(Y[i], X[i]);
run();
for(int i = 1; i <= N; i++)
Ans[i] += ddr[i];
for(int i = 1; i <= N; i++)
printf("%lld\n", Ans[i]);
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
91 ms |
51448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
91 ms |
51560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
93 ms |
51696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
105 ms |
52220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
225 ms |
57548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
