Submission #384551

#	Time	Username	Problem	Language	Result	Execution time	Memory
384551		ijxjdjd	Adriatic (CEOI13_adriatic)	C++14	100 / 100	253 ms	104800 KiB

adriatic

#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;


const int MAXN = 2500+5;
int board[MAXN][MAXN];
int pref[MAXN][MAXN];
int prefMnR[MAXN];
int suffMxR[MAXN];
int prefMnC[MAXN];
int suffMxC[MAXN];

int tright[MAXN][MAXN];
int bleft[MAXN][MAXN];


bool bad = false;
int cnt(int r1, int c1, int r2, int c2) {
    return pref[r2][c2] - pref[r1-1][c2] - pref[r2][c1-1] + pref[r1-1][c1-1];
}
int calc1(int r, int c) {
    if (tright[r][c] == -1) {
        int cur = cnt(1, c, r, MAXN-1);
        if (cur != 0) {
            int nr = min(r, prefMnR[c-1]);
            int nc = max(c, suffMxC[r+1]);
            if (nr == r && nc == c) {
                bad = true;
                tright[r][c] = 0;
            }
            else {
                tright[r][c] = cur + calc1(nr, nc);
            }
        }
        else {
            tright[r][c] = 0;
        }
    }
    return tright[r][c];
}
int calc2(int r, int c) {
    if (bleft[r][c] == -1) {
        int cur = cnt(r, 1, MAXN-1, c);
        if (cur != 0) {
            int nr = max(r, suffMxR[c+1]);
            int nc = min(c, prefMnC[r-1]);
            if (nr == r && nc == c) {
                bad = true;
                bleft[r][c] = 0;
            }
            else {
                bleft[r][c] = cur + calc2(nr, nc);
            }
        }
        else {
            bleft[r][c] = 0;
        }
    }
    return bleft[r][c];
}
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N;
	cin >> N;
	vector<pair<int, int>> pos;
	FR(i, MAXN) {
//        suffMxR[i] = (int)(1e9);
        prefMnR[i] = (int)(1e9);
        prefMnC[i] = (int)(1e9);
//        suffMxC[i] = (int)(1e9))
	}
	FR(i, MAXN) {
        FR(j, MAXN) {
            tright[i][j] = -1;
            bleft[i][j] = -1;
        }
	}
	FR(i, N) {
        int r, c;
        cin >> r >> c;
        pos.push_back({r, c});
        board[r][c]++;
        prefMnR[c] = min(prefMnR[c], r);
        suffMxC[r] = max(suffMxC[r], c);
        prefMnC[r] = min(prefMnC[r], c);
        suffMxR[c] = max(suffMxR[c], r);
	}
	for (int i = 1; i < MAXN; i++) {
        for (int j = 1; j < MAXN; j++) {
            pref[i][j] = board[i][j] + pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1];
        }
	}
	for (int i = MAXN-2; i >= 0; i--) {
        suffMxC[i] = max(suffMxC[i+1], suffMxC[i]);
        suffMxR[i] = max(suffMxR[i+1], suffMxR[i]);
	}
	for (int i = 1; i < MAXN; i++) {
        prefMnR[i] = min(prefMnR[i-1], prefMnR[i]);
        prefMnC[i] = min(prefMnC[i-1], prefMnC[i]);
	}

	for (auto& p : pos) {
        cout << calc1(p.first, p.second) + calc2(p.first, p.second) + N-3 << '\n';
	}
	return 0;
}

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