oj.uz

Submission #256774

# Submission time Handle Problem Language Result Execution time Memory
256774 2020-08-03T07:53:19 Z atoiz Rectangles (IOI19_rect) C++14
0 / 100
 225 ms 325624 KB 
#include "rect.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define x first
#define y second

#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define FORA(i, a) for (auto &i : a)
#define FORB(i, a, b) for (int i = a; i >= b; --i)

const int MAXN = 2505;
int R, C, A[MAXN][MAXN];

int prv[MAXN], nxt[MAXN], last[MAXN][MAXN], endp[MAXN][MAXN];
vector<pii> boundLR[MAXN][MAXN], boundUD[MAXN][MAXN];

int bit[MAXN];
void modify(int i, int x) {
	for (; i < MAXN; i += (i & (-i))) bit[i] += x;
}
int get(int i) {
	int ans = 0;
	for (; i > 0; i -= i & (-i)) ans += bit[i];
	return ans;
}

ll count_rectangles(vector<vector<int>> _A) {
	R = (int) _A.size(), C = (int) _A[0].size();
	FOR(i, 1, R) FOR(j, 1, C) A[i][j] = _A[i - 1][j - 1];

	// for each row
	FOR(l, 1, C) FOR(r, l + 2, C) last[l][r] = -1;
	FORB(r, R, 2) {
		prv[1] = 0, nxt[C] = C + 1;
		FOR(c, 2, C) for (prv[c] = c - 1; prv[c] > 0 && A[r][prv[c]] <= A[r][c]; prv[c] = prv[prv[c]]);
		FORB(c, C - 1, 1) for (nxt[c] = c + 1; nxt[c] <= C && A[r][nxt[c]] <= A[r][c]; nxt[c] = nxt[nxt[c]]);
		FOR(c, 1, C) if (1 <= prv[c] && nxt[c] <= C) {
			int c0 = prv[c], c1 = nxt[c];
			if (last[c0][c1] != r + 1) endp[c0][c1] = r + 1;
			last[c0][c1] = r;
			boundLR[r - 1][c0].emplace_back(endp[c0][c1], c1);
		}
	}

	// for each col
	FOR(r0, 1, R) FOR(r1, r0 + 2, R) last[r0][r1] = -1;
	FORB(c, C, 2) {
		prv[1] = 0, nxt[R] = R + 1;
		FOR(r, 2, R) for (prv[r] = r - 1; prv[r] >= 1 && A[prv[r]][c] <= A[r][c]; prv[r] = prv[prv[r]]);
		FORB(r, R - 1, 1) for (nxt[r] = r + 1; nxt[r] <= R && A[nxt[r]][c] <= A[r][c]; nxt[r] = nxt[nxt[r]]);
		FOR(r, 1, R) if (1 <= prv[r] && nxt[r] <= R) {
			int r0 = prv[r], r1 = nxt[r];
			if (last[r0][r1] != c + 1) endp[r0][r1] = c + 1;
			last[r0][r1] = c;
			boundUD[r0][c - 1].emplace_back(r1, endp[r0][r1]);
		}
	}

	ll ans = 0;
	FOR(rootR, 1, R - 2) FOR(rootC, 1, C - 2) if (!boundLR[rootR][rootC].empty() && !boundUD[rootR][rootC].empty()) {
		auto &curLR = boundLR[rootR][rootC], &curUD = boundUD[rootR][rootC];
		sort(curLR.begin(), curLR.end()), sort(curUD.begin(), curUD.end());
		auto itLR = curLR.begin();
		auto itUD = curUD.begin();
		while (itLR != curLR.end() || itUD != curUD.end()) {
			if (itLR != curLR.end() && (itUD == curUD.end() || itLR->x < itUD->x)) {
				ans += get((itLR++)->second);
			} else {
				modify((itUD++)->second, 1);
			}
		}

		for (auto p : curUD) modify(p.second, -1);
	}

	return ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 295160 KB Output is correct
2 Correct 168 ms 295428 KB Output is correct
3 Correct 186 ms 295544 KB Output is correct
4 Correct 184 ms 295416 KB Output is correct
5 Correct 220 ms 295288 KB Output is correct
6 Incorrect 170 ms 295552 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 295160 KB Output is correct
2 Correct 168 ms 295428 KB Output is correct
3 Correct 186 ms 295544 KB Output is correct
4 Correct 184 ms 295416 KB Output is correct
5 Correct 220 ms 295288 KB Output is correct
6 Incorrect 170 ms 295552 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 295160 KB Output is correct
2 Correct 168 ms 295428 KB Output is correct
3 Correct 186 ms 295544 KB Output is correct
4 Correct 184 ms 295416 KB Output is correct
5 Correct 220 ms 295288 KB Output is correct
6 Incorrect 170 ms 295552 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 295160 KB Output is correct
2 Correct 168 ms 295428 KB Output is correct
3 Correct 186 ms 295544 KB Output is correct
4 Correct 184 ms 295416 KB Output is correct
5 Correct 220 ms 295288 KB Output is correct
6 Incorrect 170 ms 295552 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 325624 KB Output is correct
2 Correct 225 ms 320352 KB Output is correct
3 Correct 206 ms 315384 KB Output is correct
4 Correct 178 ms 295048 KB Output is correct
5 Incorrect 201 ms 323228 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 166 ms 295160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 295160 KB Output is correct
2 Correct 168 ms 295428 KB Output is correct
3 Correct 186 ms 295544 KB Output is correct
4 Correct 184 ms 295416 KB Output is correct
5 Correct 220 ms 295288 KB Output is correct
6 Incorrect 170 ms 295552 KB Output isn't correct
7 Halted 0 ms 0 KB -