oj.uz

Submission #1069778

# Submission time Handle Problem Language Result Execution time Memory
1069778 2024-08-22T08:53:17 Z Gromp15 Rectangles (IOI19_rect) C++17
23 / 100
 1401 ms 883732 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include "rect.h"
#define ll long long
#define ar array
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
 
using namespace std;

template<typename T> struct fenwick {
    int n; vector<T> bit;
    fenwick(int a) : n(a), bit(a+1) {}
    T sum(int pos) {
        T s = 0;
        for (; pos; s += bit[pos], pos -= pos&-pos);
        return s;
    }
    T query(int l, int r) {
        return sum(r+1) - sum(l);
    }
    void update(int pos, T x) {
        pos++;
        for (; pos <= n; bit[pos] += x, pos += pos&-pos);
    }
};
 
const int nax = 2505;
short u[nax][nax], d[nax][nax], l[nax][nax], r[nax][nax], st[nax], idx[nax], idx2[nax];
vector<short> who[nax][nax], who2[nax][nax], to[nax][nax], to2[nax][nax];
fenwick<int> fw(nax);
 
long long count_rectangles(std::vector<std::vector<int>> a) {
	int n = sz(a), m = sz(a[0]);
	for (int i = 0, tp = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			while (tp && a[i][j] >= a[i][st[tp]]) tp--;
			l[i][j] = tp ? st[tp] : m + 1;
			st[++tp] = j;
		}
		tp = 0;
		for (int j = m-1; j >= 0; j--) {
			while (tp && a[i][j] >= a[i][st[tp]]) tp--;
			r[i][j] = tp ? st[tp] : -2;
			st[++tp] = j;
		}
	}
	for (int i = 0, tp = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			while (tp && a[j][i] >= a[st[tp]][i]) tp--;
			u[j][i] = tp ? st[tp] : n + 1;
			st[++tp] = j;
		}
		tp = 0;
		for (int j = n-1; j >= 0; j--) {
			while (tp && a[j][i] >= a[st[tp]][i]) tp--;
			d[j][i] = tp ? st[tp] : -2;
			st[++tp] = j;
		}
	}
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { 
		int L = l[i][j] + 1, R = r[i][j] - 1;
		if (L <= R) who[i][L].emplace_back(R);
		int U = u[i][j] + 1, D = d[i][j] - 1;
		if (U <= D) who2[U][j].emplace_back(D);
	}
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
		sort(all(who[i][j]));
		sort(all(who2[i][j]));
		who[i][j].erase(unique(all(who[i][j])), who[i][j].end());
		who2[i][j].erase(unique(all(who2[i][j])), who2[i][j].end());
		to[i][j].resize(sz(who[i][j]));
		to2[i][j].resize(sz(who2[i][j]));
	}
	vector<vector<ar<short, 3>>> add(n), rem(n);
	for (int i = n-1; i >= 0; i--) {
		for (int j = m-1; j >= 0; j--) {
			for (int k = 0; k < sz(who[i][j]); k++) {
				int r = who[i][j][k];
				if (i+1 < n) {
					auto it = lower_bound(all(who[i+1][j]), r);
					if (it != who[i+1][j].end() && *it == r) to[i][j][k] = to[i+1][j][it - who[i+1][j].begin()];
					else to[i][j][k] = i;
				}
				else to[i][j][k] = i;
			}
			for (int k = 0; k < sz(who2[i][j]); k++) {
				int d = who2[i][j][k];
				if (j+1 < m) {
					auto it = lower_bound(all(who2[i][j+1]), d);
					if (it != who2[i][j+1].end() && *it == d) to2[i][j][k] = to2[i][j+1][it - who2[i][j+1].begin()];
					else to2[i][j][k] = j;
				}
			}
		}
	}
	ll ans = 0;
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
		iota(idx, idx + sz(who[i][j]), 0);
		sort(idx, idx + sz(who[i][j]), [&](int x, int y) { return who[i][j][x] < who[i][j][y]; });
		iota(idx2, idx2 + sz(who2[i][j]), 0);
		sort(idx2, idx2 + sz(who2[i][j]), [&](int x, int y) { return to2[i][j][x] < to2[i][j][y]; });
		int t = 0;
		for (int k = 0; k < sz(who2[i][j]); k++) {
			while (t < sz(who[i][j]) && who[i][j][idx[t]] <= to2[i][j][idx2[k]]) {
				fw.update(to[i][j][idx[t++]], 1);
			}
			ans += fw.query(who2[i][j][idx2[k]], nax-1);
		}
		for (int k = 0; k < t; k++) fw.update(to[i][j][idx[k]], -1);
	}
	return ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 591436 KB Output is correct
2 Correct 174 ms 592016 KB Output is correct
3 Correct 185 ms 591956 KB Output is correct
4 Correct 169 ms 591828 KB Output is correct
5 Correct 170 ms 591956 KB Output is correct
6 Incorrect 199 ms 591952 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 591436 KB Output is correct
2 Correct 174 ms 592016 KB Output is correct
3 Correct 185 ms 591956 KB Output is correct
4 Correct 169 ms 591828 KB Output is correct
5 Correct 170 ms 591956 KB Output is correct
6 Incorrect 199 ms 591952 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 591436 KB Output is correct
2 Correct 174 ms 592016 KB Output is correct
3 Correct 185 ms 591956 KB Output is correct
4 Correct 169 ms 591828 KB Output is correct
5 Correct 170 ms 591956 KB Output is correct
6 Incorrect 199 ms 591952 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 591436 KB Output is correct
2 Correct 174 ms 592016 KB Output is correct
3 Correct 185 ms 591956 KB Output is correct
4 Correct 169 ms 591828 KB Output is correct
5 Correct 170 ms 591956 KB Output is correct
6 Incorrect 199 ms 591952 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 592208 KB Output is correct
2 Correct 175 ms 592208 KB Output is correct
3 Correct 169 ms 591700 KB Output is correct
4 Correct 164 ms 591608 KB Output is correct
5 Correct 165 ms 591956 KB Output is correct
6 Correct 166 ms 591956 KB Output is correct
7 Correct 173 ms 591804 KB Output is correct
8 Correct 168 ms 591956 KB Output is correct
9 Correct 167 ms 591956 KB Output is correct
10 Correct 168 ms 591696 KB Output is correct
11 Correct 165 ms 591696 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 591700 KB Output is correct
2 Correct 674 ms 726236 KB Output is correct
3 Correct 1350 ms 882076 KB Output is correct
4 Correct 1361 ms 883424 KB Output is correct
5 Correct 1401 ms 883732 KB Output is correct
6 Correct 300 ms 638288 KB Output is correct
7 Correct 418 ms 684884 KB Output is correct
8 Correct 444 ms 687956 KB Output is correct
9 Correct 180 ms 591448 KB Output is correct
10 Correct 165 ms 591440 KB Output is correct
11 Correct 189 ms 591900 KB Output is correct
12 Correct 177 ms 591956 KB Output is correct
13 Correct 174 ms 591704 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 591436 KB Output is correct
2 Correct 174 ms 592016 KB Output is correct
3 Correct 185 ms 591956 KB Output is correct
4 Correct 169 ms 591828 KB Output is correct
5 Correct 170 ms 591956 KB Output is correct
6 Incorrect 199 ms 591952 KB Output isn't correct
7 Halted 0 ms 0 KB -