oj.uz

Submission #384551

# Submission time Handle Problem Language Result Execution time Memory
384551 2021-04-01T20:44:00 Z ijxjdjd Adriatic (CEOI13_adriatic) C++14
100 / 100
 253 ms 104800 KB 
#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 74476 KB Output is correct
2 Correct 71 ms 74476 KB Output is correct
3 Correct 70 ms 74476 KB Output is correct
4 Correct 72 ms 74220 KB Output is correct
5 Correct 70 ms 74348 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 78572 KB Output is correct
2 Correct 77 ms 79596 KB Output is correct
3 Correct 73 ms 78828 KB Output is correct
4 Correct 70 ms 74604 KB Output is correct
5 Correct 70 ms 74988 KB Output is correct
6 Correct 71 ms 76908 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 82668 KB Output is correct
2 Correct 80 ms 87916 KB Output is correct
3 Correct 76 ms 83180 KB Output is correct
4 Correct 72 ms 75884 KB Output is correct
5 Correct 72 ms 75500 KB Output is correct
6 Correct 76 ms 84460 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 85356 KB Output is correct
2 Correct 92 ms 98924 KB Output is correct
3 Correct 89 ms 85612 KB Output is correct
4 Correct 86 ms 77804 KB Output is correct
5 Correct 81 ms 77036 KB Output is correct
6 Correct 84 ms 85356 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 91588 KB Output is correct
2 Correct 245 ms 104800 KB Output is correct
3 Correct 253 ms 99168 KB Output is correct
4 Correct 197 ms 87776 KB Output is correct
5 Correct 173 ms 84832 KB Output is correct
6 Correct 193 ms 93024 KB Output is correct
7 Correct 194 ms 92512 KB Output is correct