Submission #37204

#	Time	Username	Problem	Language	Result	Execution time	Memory
37204		DoanPhuDuc	Adriatic (CEOI13_adriatic)	C++98	0 / 100	476 ms	228532 KiB

adriatic

#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;

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

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

II f[A + 10][A + 10], g[A + 10][A + 10];

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][A][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];
    FOR(i, 1, A)
        FOR(j, 1, A) f[i][j] = g[i][j] = II(-1, -1);
}

II ComputeUp(int x, int y, int ly, int rx) {
    if (f[x][y] != II(-1, -1)) return f[x][y];
    if (C1[x][y] == 0) return f[x][y] = II(0, 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 f[x][y] = II(0, 0);
    int s = (C1[x][y] - C1[minX][maxY] - (sx == x && sy == y));
    II nxt = ComputeUp(minX, maxY, y, x);
    nxt.first = nxt.first + s + nxt.second;
    nxt.second += s;
    return f[x][y] = nxt;
}

II ComputeDown(int x, int y, int lx, int ry) {
   // if (f[level][x].count(y)) return f[level][x][y];
    if (g[x][y] != II(-1, -1)) return g[x][y];
    if (C2[x][y] == 0) return g[x][y] = II(0, 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 g[x][y] = II(0, 0);
    int s = (C2[x][y] - C2[maxX][minY] - (sx == x && sy == y));
    II nxt = ComputeDown(maxX, minY, x, y);
    nxt.first = nxt.first + s + nxt.second;
    nxt.second += s;
    return g[x][y] = nxt;
}

void Write(int n) {
    if (n == 0) {
        putchar('0');
        putchar('\n');
        return;
    }
    char c[30]; int k = 0;
    while (n) {
        c[++k] = n % 10 + '0';
        n /= 10;
    }
    FOD(i, k, 1) putchar(c[i]); putchar('\n');
}

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;
        II up = ComputeUp(sx, sy, 1, A);
        II down = ComputeDown(sx, sy, 1, A);
        //cout << up << " " << down << endl;
        int ans = up.first + up.second +
                  down.first + down.second + C3[sx - 1][sy - 1] + C4[sx + 1][sy + 1];
        Write(ans);
    }

    return 0;
}

Compilation message (stderr)

adriatic.cpp: In function 'int main()':
adriatic.cpp:130:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
adriatic.cpp:132: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);
                                        ^
adriatic.cpp: In function 'void Init()':
adriatic.cpp:39:62: warning: iteration 2509u invokes undefined behavior [-Waggressive-loop-optimizations]
             FOR(j, 1, A) spT[i][j][0] = (i == 0 ? INF : -INF);
                                                              ^
adriatic.cpp:3:40: note: containing loop
 #define FOR(x, a, b) for (int x = a; x <= b; ++x)
                                        ^
adriatic.cpp:39:13: note: in expansion of macro 'FOR'
             FOR(j, 1, A) spT[i][j][0] = (i == 0 ? INF : -INF);
             ^
adriatic.cpp:39:62: warning: iteration 2509u invokes undefined behavior [-Waggressive-loop-optimizations]
             FOR(j, 1, A) spT[i][j][0] = (i == 0 ? INF : -INF);
                                                              ^
adriatic.cpp:3:40: note: containing loop
 #define FOR(x, a, b) for (int x = a; x <= b; ++x)
                                        ^
adriatic.cpp:39:13: note: in expansion of macro 'FOR'
             FOR(j, 1, A) spT[i][j][0] = (i == 0 ? INF : -INF);
             ^

• Subtask 1: 0 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20