oj.uz

답안 #37193

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
37193 2017-12-22T13:36:50 Z DoanPhuDuc 섬 항해 (CEOI13_adriatic) C++
80 / 100
 2000 ms 236216 KB 
#include <bits/stdc++.h>

#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n)  { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }
#define BitCount(x) __builtin_popcount(x)

using namespace std;

typedef long long LL;
typedef pair <int, int> II;
typedef pair <LL, int> LLI;

const int N = 3e5 + 10;
const int LG = 20;
const int A = 2500 + 10;
const int INF = 0x3f3f3f3f;

struct Point {
    int x, y;
    Point () {}
    Point (int x, int y) : x(x), y(y) {}
} P[N];

int n, sx, sy;
int a[A + 10][A + 10], C1[A + 10][A + 10], C2[A + 10][A + 10];
int C3[A + 10][A + 10], C4[A + 10][A + 10];
int lg[A + 20];

struct RMQ {
    int spT[2][N][LG + 3];
    void Build() {
        FOR(i, 0, 1)
            FOR(j, 1, A) spT[i][j][0] = (i == 0 ? INF : -INF);
        FOR(i, 0, 1)
            FOR(j, 1, n) {
                spT[i][P[j].x][0] = (i == 0) ? min(spT[i][P[j].x][0], P[j].y) :
                                               max(spT[i][P[j].x][0], P[j].y);
            }
        for (int j = 1; 1 << j <= A; ++j)
            for (int i = 1; i + (1 << j) - 1 <= A; ++i) {
                spT[0][i][j] = min(spT[0][i][j - 1], spT[0][i + (1 << (j - 1))][j - 1]);
                spT[1][i][j] = max(spT[1][i][j - 1], spT[1][i + (1 << (j - 1))][j - 1]);
            }
    }
    int Query(int t, int l, int r) {
        if (l > r) return (t == 0 ? INF : -INF);
        int k = lg[r - l + 1];
        if (t == 0) return min(spT[t][l][k], spT[t][r - (1 << k) + 1][k]);
            else return max(spT[t][l][k], spT[t][r - (1 << k) + 1][k]);
    }
} RMQX, RMQY;

void Init() {
    for (int i = 0; 1 << i <= A; ++i) lg[1 << i] = i;
    FOR(i, 1, A) if (!lg[i]) lg[i] = lg[i - 1];
    RMQY.Build();
    FOR(i, 1, n) swap(P[i].x, P[i].y);
    RMQX.Build();
    FOR(i, 1, n) swap(P[i].x, P[i].y);
    FOR(i, 1, A)
        FOD(j, A, 1) {
            C1[i][j] = C1[i - 1][j] + C1[i][j + 1] - C1[i - 1][j + 1] + a[i][j];
        }
    FOD(i, A, 1)
        FOR(j, 1, A) {
            C2[i][j] = C2[i][j - 1] + C2[i + 1][j] - C2[i + 1][j - 1] + a[i][j];
        }
    FOR(i, 1, A)
        FOR(j, 1, A)
            C3[i][j] = C3[i][j - 1] + C3[i - 1][j] - C3[i - 1][j - 1] + a[i][j];
    FOD(i, A, 1)
        FOD(j, A, 1)
            C4[i][j] = C4[i][j + 1] + C4[i + 1][j] - C4[i + 1][j + 1] + a[i][j];
}

LL ComputeUp(int level, int x, int y, int ly, int rx) {
    if (C1[x][y] == 0) return 0;
    int minX = RMQX.Query(0, ly, y - 1); minX = min(minX, x);
    int maxY = RMQY.Query(1, x + 1, rx); maxY = max(maxY, y);
    if (minX == x && maxY == y) return 0;
    LL ans = level * (C1[x][y] - C1[minX][maxY] - (sx == x && sy == y));
    return ans + ComputeUp(level + 1, minX, maxY, y, x);
}

LL ComputeDown(int level, int x, int y, int lx, int ry) {
    if (C2[x][y] == 0) return 0;
    int maxX = RMQX.Query(1, y + 1, ry); maxX = max(maxX, x);
    int minY = RMQY.Query(0, lx, x - 1); minY = min(minY, y);
    if (maxX == x && minY == y) return 0;
    //DEBUG(x);
    //DEBUG(y);
    //cout << y + 1 << " " << ry << endl;
    //cout << maxX << " " << minY << endl;
   // cout << C2[x][y] - C2[maxX][minY] - (sx == x && sy == y) << endl;
    LL ans = (LL)level * (C2[x][y] - C2[maxX][minY] - (sx == x && sy == y));
    return ans + ComputeDown(level + 1, maxX, minY, x, y);
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // LOCAL
    scanf("%d", &n);
    FOR(i, 1, n) {
        int x, y; scanf("%d%d", &x, &y);
        P[i] = Point(x, y);
        a[x][y] = 1;
    }
    Init();
    FOR(i, 1, n) {
        sx = P[i].x, sy = P[i].y;
        LL up = ComputeUp(2, sx, sy, 1, A);
        LL down = ComputeDown(2, sx, sy, 1, A);
        //cout << up << " " << down << endl;
        printf("%lld\n", up + down + C3[sx - 1][sy - 1] + C4[sx + 1][sy + 1]);
    }

    return 0;
}

Compilation message

adriatic.cpp: In function 'int main()':
adriatic.cpp:108:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
adriatic.cpp:110:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x, y; scanf("%d%d", &x, &y);
                                        ^

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 236216 KB Output is correct
2 Correct 89 ms 236216 KB Output is correct
3 Correct 96 ms 236216 KB Output is correct
4 Correct 99 ms 236216 KB Output is correct
5 Correct 119 ms 236216 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 236216 KB Output is correct
2 Correct 96 ms 236216 KB Output is correct
3 Correct 106 ms 236216 KB Output is correct
4 Correct 113 ms 236216 KB Output is correct
5 Correct 93 ms 236216 KB Output is correct
6 Correct 119 ms 236216 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 146 ms 236216 KB Output is correct
2 Correct 83 ms 236216 KB Output is correct
3 Correct 96 ms 236216 KB Output is correct
4 Correct 116 ms 236216 KB Output is correct
5 Correct 119 ms 236216 KB Output is correct
6 Correct 416 ms 236216 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 699 ms 236216 KB Output is correct
2 Correct 153 ms 236216 KB Output is correct
3 Correct 209 ms 236216 KB Output is correct
4 Correct 109 ms 236216 KB Output is correct
5 Correct 136 ms 236216 KB Output is correct
6 Correct 1606 ms 236216 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2000 ms 236216 KB Execution timed out
2 Halted 0 ms 0 KB -