oj.uz

Submission #157349

# Submission time Handle Problem Language Result Execution time Memory
157349 2019-10-11T02:57:57 Z qkxwsm Rectangles (IOI19_rect) C++14
72 / 100
 3726 ms 1048580 KB 
#include "rect.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define y1 qkx
#define y2 wsm
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define INF 1000000007
#define MAXN 2513

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, M;
vector<vi> grid;
int rt[MAXN][MAXN], dn[MAXN][MAXN], lt[MAXN][MAXN], up[MAXN][MAXN];
vi ev[MAXN][MAXN], eh[MAXN][MAXN];
vi dv[MAXN][MAXN], dh[MAXN][MAXN];
ll ans;
ordered_set<pii> ord;

ll count_rectangles(vector<vi> a)
{
	N = SZ(a); M = SZ(a[0]); grid = a;
	//BE SUPER CAREFUL ABOUT EQUALITY CASE.
	//for each guy, find the next guy right of it that's greater th an it.
	//ok fix the starting column #.
	FOR(i, 0, N)
	{
		vpi cand; cand.PB({INF, M + 1});
		FORD(j, M, 0)
		{
			while(cand.back().fi < grid[i][j]) cand.pop_back();
			rt[i][j] = cand.back().se;
			cand.PB({grid[i][j], j});
		}
		cand.clear(); cand.PB({INF, -2});
		FOR(j, 0, M)
		{
			while(cand.back().fi < grid[i][j]) cand.pop_back();
			lt[i][j] = cand.back().se;
			cand.PB({grid[i][j], j});
		}
	}
	FOR(i, 0, M)
	{
		vpi cand; cand.PB({INF, N + 1});
		FORD(j, N, 0)
		{
			while(cand.back().fi < grid[j][i]) cand.pop_back();
			dn[j][i] = cand.back().se;
			cand.PB({grid[j][i], j});
		}
		cand.clear(); cand.PB({INF, -2});
		FOR(j, 0, N)
		{
			while(cand.back().fi < grid[j][i]) cand.pop_back();
			up[j][i] = cand.back().se;
			cand.PB({grid[j][i], j});
		}
	}
	FOR(i, 0, N)
	{
		FOR(j, 0, M)
		{
			// cerr << "POS " << i << ' ' << j << endl;
			int idx = lt[i][j];
			// cerr << idx << ' ';
			if (idx >= 0 & idx != j - 1)
			{
				eh[i][idx + 1].PB(j - 1);
			}
			idx = rt[i][j];
			// cerr << idx << ' ';
			if (idx < M && idx != j + 1)
			{
				eh[i][j + 1].PB(idx - 1);
			}
			idx = up[i][j];
			// cerr << idx << ' ';
			if (idx >= 0 && idx != i - 1)
			{
				ev[idx + 1][j].PB(i - 1);
			}
			idx = dn[i][j];
			// cerr << idx << endl;
			if (idx < N && idx != i + 1)
			{
				ev[i + 1][j].PB(idx - 1);
			}
		}
	}
	FOR(i, 0, N)
	{
		FOR(j, 0, M)
		{
			sort(ALL(ev[i][j])); ev[i][j].erase(unique(ALL(ev[i][j])), ev[i][j].end());
			sort(ALL(eh[i][j])); eh[i][j].erase(unique(ALL(eh[i][j])), eh[i][j].end());
			dv[i][j].resize(SZ(ev[i][j]));
			dh[i][j].resize(SZ(eh[i][j]));
			// cerr << "EDGES FROM " << i << ',' << j << endl;
			// cerr << "VERTICAL\n";
			// for (int x : ev[i][j])
			// {
			// 	cerr << x << ' ' << j << endl;
			// }
			// cerr << "HORIZONTAL\n";
			// for (int y : eh[i][j])
			// {
			// 	cerr << i << ' ' << y << endl;
			// }
		}
	}
	FOR(i, 0, N)
	{
		FORD(j, M, 0)
		{
			int idx = 0;
			FOR(k, 0, SZ(ev[i][j]))
			{
				dv[i][j][k] = j;
				int x = ev[i][j][k];
				while(idx < SZ(ev[i][j + 1]) && ev[i][j + 1][idx] < x) idx++;
				if (idx >= SZ(ev[i][j + 1]) || ev[i][j + 1][idx] != x) continue;
				dv[i][j][k] = dv[i][j + 1][idx];
			}
		}
	}
	FOR(i, 0, M)
	{
		FORD(j, N, 0)
		{
			int idx = 0;
			FOR(k, 0, SZ(eh[j][i]))
			{
				dh[j][i][k] = j;
				int y = eh[j][i][k];
				while(idx < SZ(eh[j + 1][i]) && eh[j + 1][i][idx] < y) idx++;
				if (idx >= SZ(eh[j + 1][i]) || eh[j + 1][i][idx] != y) continue;
				dh[j][i][k] = dh[j + 1][i][idx];
			}
		}
	}
	FOR(i, 1, N - 1)
	{
		FOR(j, 1, M - 1)
		{
			//count (k, m) such that ev[i][j][k] <= dh[i][j][m], dv[i][j][k] >= eh[i][j][m]
			vpi ps;
			FOR(k, 0, SZ(eh[i][j]))
			{
				ps.PB({dh[i][j][k], eh[i][j][k]});
			}
			sort(ALL(ps));
			FOR(k, 0, SZ(ps))
			{
				ord.insert({ps[k].se, k});
			}
			//count {ev[i][j][k], dv[i][j][k]} in lt and (c, d) in ps such that a <= c && b >= d
			int iter = 0;
			FOR(k, 0, SZ(ev[i][j]))
			{
				while(iter < SZ(ps) && ps[iter].fi < ev[i][j][k])
				{
					ord.erase({ps[iter].se, iter});
					iter++;
				}
				ans += ord.order_of_key({dv[i][j][k], INF});
			}
			ord.clear();
		}
	}
	//for each horizontal segment, see how far up it can go.
	//for each vertical segment, see how far left it can go
	//ok lol idk
	return ans;
}

Compilation message

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:102:12: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
    if (idx >= 0 & idx != j - 1)
        ~~~~^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 593668 KB Output is correct
2 Correct 576 ms 594296 KB Output is correct
3 Correct 583 ms 594296 KB Output is correct
4 Correct 558 ms 594168 KB Output is correct
5 Correct 557 ms 594212 KB Output is correct
6 Correct 575 ms 594224 KB Output is correct
7 Correct 557 ms 594156 KB Output is correct
8 Correct 561 ms 593716 KB Output is correct
9 Correct 553 ms 594040 KB Output is correct
10 Correct 560 ms 594096 KB Output is correct
11 Correct 558 ms 594140 KB Output is correct
12 Correct 641 ms 594024 KB Output is correct
13 Correct 606 ms 593684 KB Output is correct
14 Correct 655 ms 593792 KB Output is correct
15 Correct 553 ms 593724 KB Output is correct
16 Correct 552 ms 593536 KB Output is correct
17 Correct 558 ms 593620 KB Output is correct
18 Correct 559 ms 593560 KB Output is correct
19 Correct 553 ms 594040 KB Output is correct
20 Correct 551 ms 594072 KB Output is correct
21 Correct 551 ms 593712 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 593668 KB Output is correct
2 Correct 576 ms 594296 KB Output is correct
3 Correct 583 ms 594296 KB Output is correct
4 Correct 558 ms 594168 KB Output is correct
5 Correct 557 ms 594212 KB Output is correct
6 Correct 575 ms 594224 KB Output is correct
7 Correct 557 ms 594156 KB Output is correct
8 Correct 561 ms 593716 KB Output is correct
9 Correct 553 ms 594040 KB Output is correct
10 Correct 560 ms 594096 KB Output is correct
11 Correct 558 ms 594140 KB Output is correct
12 Correct 641 ms 594024 KB Output is correct
13 Correct 606 ms 593684 KB Output is correct
14 Correct 655 ms 593792 KB Output is correct
15 Correct 553 ms 593724 KB Output is correct
16 Correct 552 ms 593536 KB Output is correct
17 Correct 560 ms 595796 KB Output is correct
18 Correct 561 ms 595864 KB Output is correct
19 Correct 555 ms 595824 KB Output is correct
20 Correct 554 ms 595276 KB Output is correct
21 Correct 560 ms 595448 KB Output is correct
22 Correct 560 ms 595448 KB Output is correct
23 Correct 610 ms 595456 KB Output is correct
24 Correct 666 ms 595164 KB Output is correct
25 Correct 558 ms 593620 KB Output is correct
26 Correct 559 ms 593560 KB Output is correct
27 Correct 553 ms 594040 KB Output is correct
28 Correct 551 ms 594072 KB Output is correct
29 Correct 551 ms 593712 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 593668 KB Output is correct
2 Correct 576 ms 594296 KB Output is correct
3 Correct 583 ms 594296 KB Output is correct
4 Correct 558 ms 594168 KB Output is correct
5 Correct 557 ms 594212 KB Output is correct
6 Correct 575 ms 594224 KB Output is correct
7 Correct 557 ms 594156 KB Output is correct
8 Correct 561 ms 593716 KB Output is correct
9 Correct 553 ms 594040 KB Output is correct
10 Correct 560 ms 594096 KB Output is correct
11 Correct 558 ms 594140 KB Output is correct
12 Correct 641 ms 594024 KB Output is correct
13 Correct 606 ms 593684 KB Output is correct
14 Correct 655 ms 593792 KB Output is correct
15 Correct 553 ms 593724 KB Output is correct
16 Correct 552 ms 593536 KB Output is correct
17 Correct 560 ms 595796 KB Output is correct
18 Correct 561 ms 595864 KB Output is correct
19 Correct 555 ms 595824 KB Output is correct
20 Correct 554 ms 595276 KB Output is correct
21 Correct 560 ms 595448 KB Output is correct
22 Correct 560 ms 595448 KB Output is correct
23 Correct 610 ms 595456 KB Output is correct
24 Correct 666 ms 595164 KB Output is correct
25 Correct 685 ms 603048 KB Output is correct
26 Correct 632 ms 603128 KB Output is correct
27 Correct 632 ms 603056 KB Output is correct
28 Correct 588 ms 599700 KB Output is correct
29 Correct 631 ms 600472 KB Output is correct
30 Correct 590 ms 600648 KB Output is correct
31 Correct 591 ms 600668 KB Output is correct
32 Correct 580 ms 600500 KB Output is correct
33 Correct 558 ms 593620 KB Output is correct
34 Correct 559 ms 593560 KB Output is correct
35 Correct 553 ms 594040 KB Output is correct
36 Correct 551 ms 594072 KB Output is correct
37 Correct 551 ms 593712 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 593668 KB Output is correct
2 Correct 576 ms 594296 KB Output is correct
3 Correct 583 ms 594296 KB Output is correct
4 Correct 558 ms 594168 KB Output is correct
5 Correct 557 ms 594212 KB Output is correct
6 Correct 575 ms 594224 KB Output is correct
7 Correct 557 ms 594156 KB Output is correct
8 Correct 561 ms 593716 KB Output is correct
9 Correct 553 ms 594040 KB Output is correct
10 Correct 560 ms 594096 KB Output is correct
11 Correct 558 ms 594140 KB Output is correct
12 Correct 641 ms 594024 KB Output is correct
13 Correct 606 ms 593684 KB Output is correct
14 Correct 655 ms 593792 KB Output is correct
15 Correct 553 ms 593724 KB Output is correct
16 Correct 552 ms 593536 KB Output is correct
17 Correct 560 ms 595796 KB Output is correct
18 Correct 561 ms 595864 KB Output is correct
19 Correct 555 ms 595824 KB Output is correct
20 Correct 554 ms 595276 KB Output is correct
21 Correct 560 ms 595448 KB Output is correct
22 Correct 560 ms 595448 KB Output is correct
23 Correct 610 ms 595456 KB Output is correct
24 Correct 666 ms 595164 KB Output is correct
25 Correct 685 ms 603048 KB Output is correct
26 Correct 632 ms 603128 KB Output is correct
27 Correct 632 ms 603056 KB Output is correct
28 Correct 588 ms 599700 KB Output is correct
29 Correct 631 ms 600472 KB Output is correct
30 Correct 590 ms 600648 KB Output is correct
31 Correct 591 ms 600668 KB Output is correct
32 Correct 580 ms 600500 KB Output is correct
33 Correct 787 ms 649264 KB Output is correct
34 Correct 747 ms 636404 KB Output is correct
35 Correct 768 ms 636388 KB Output is correct
36 Correct 808 ms 623480 KB Output is correct
37 Correct 1010 ms 679764 KB Output is correct
38 Correct 1006 ms 679676 KB Output is correct
39 Correct 999 ms 679712 KB Output is correct
40 Correct 1010 ms 674044 KB Output is correct
41 Correct 773 ms 633848 KB Output is correct
42 Correct 837 ms 638940 KB Output is correct
43 Correct 1016 ms 649692 KB Output is correct
44 Correct 1117 ms 649768 KB Output is correct
45 Correct 805 ms 627448 KB Output is correct
46 Correct 771 ms 621688 KB Output is correct
47 Correct 947 ms 647192 KB Output is correct
48 Correct 962 ms 647332 KB Output is correct
49 Correct 558 ms 593620 KB Output is correct
50 Correct 559 ms 593560 KB Output is correct
51 Correct 553 ms 594040 KB Output is correct
52 Correct 551 ms 594072 KB Output is correct
53 Correct 551 ms 593712 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 594548 KB Output is correct
2 Correct 646 ms 594504 KB Output is correct
3 Correct 689 ms 593940 KB Output is correct
4 Correct 695 ms 593616 KB Output is correct
5 Correct 603 ms 594296 KB Output is correct
6 Correct 553 ms 594040 KB Output is correct
7 Correct 557 ms 594152 KB Output is correct
8 Correct 597 ms 594168 KB Output is correct
9 Correct 568 ms 594192 KB Output is correct
10 Correct 554 ms 593796 KB Output is correct
11 Correct 558 ms 593984 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 593860 KB Output is correct
2 Correct 1936 ms 765848 KB Output is correct
3 Correct 3662 ms 959588 KB Output is correct
4 Correct 3682 ms 961456 KB Output is correct
5 Correct 3726 ms 961528 KB Output is correct
6 Correct 1108 ms 678896 KB Output is correct
7 Correct 1689 ms 761464 KB Output is correct
8 Correct 1703 ms 766064 KB Output is correct
9 Correct 558 ms 593620 KB Output is correct
10 Correct 559 ms 593560 KB Output is correct
11 Correct 553 ms 594040 KB Output is correct
12 Correct 551 ms 594072 KB Output is correct
13 Correct 551 ms 593712 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 593668 KB Output is correct
2 Correct 576 ms 594296 KB Output is correct
3 Correct 583 ms 594296 KB Output is correct
4 Correct 558 ms 594168 KB Output is correct
5 Correct 557 ms 594212 KB Output is correct
6 Correct 575 ms 594224 KB Output is correct
7 Correct 557 ms 594156 KB Output is correct
8 Correct 561 ms 593716 KB Output is correct
9 Correct 553 ms 594040 KB Output is correct
10 Correct 560 ms 594096 KB Output is correct
11 Correct 558 ms 594140 KB Output is correct
12 Correct 641 ms 594024 KB Output is correct
13 Correct 606 ms 593684 KB Output is correct
14 Correct 655 ms 593792 KB Output is correct
15 Correct 553 ms 593724 KB Output is correct
16 Correct 552 ms 593536 KB Output is correct
17 Correct 560 ms 595796 KB Output is correct
18 Correct 561 ms 595864 KB Output is correct
19 Correct 555 ms 595824 KB Output is correct
20 Correct 554 ms 595276 KB Output is correct
21 Correct 560 ms 595448 KB Output is correct
22 Correct 560 ms 595448 KB Output is correct
23 Correct 610 ms 595456 KB Output is correct
24 Correct 666 ms 595164 KB Output is correct
25 Correct 685 ms 603048 KB Output is correct
26 Correct 632 ms 603128 KB Output is correct
27 Correct 632 ms 603056 KB Output is correct
28 Correct 588 ms 599700 KB Output is correct
29 Correct 631 ms 600472 KB Output is correct
30 Correct 590 ms 600648 KB Output is correct
31 Correct 591 ms 600668 KB Output is correct
32 Correct 580 ms 600500 KB Output is correct
33 Correct 787 ms 649264 KB Output is correct
34 Correct 747 ms 636404 KB Output is correct
35 Correct 768 ms 636388 KB Output is correct
36 Correct 808 ms 623480 KB Output is correct
37 Correct 1010 ms 679764 KB Output is correct
38 Correct 1006 ms 679676 KB Output is correct
39 Correct 999 ms 679712 KB Output is correct
40 Correct 1010 ms 674044 KB Output is correct
41 Correct 773 ms 633848 KB Output is correct
42 Correct 837 ms 638940 KB Output is correct
43 Correct 1016 ms 649692 KB Output is correct
44 Correct 1117 ms 649768 KB Output is correct
45 Correct 805 ms 627448 KB Output is correct
46 Correct 771 ms 621688 KB Output is correct
47 Correct 947 ms 647192 KB Output is correct
48 Correct 962 ms 647332 KB Output is correct
49 Correct 562 ms 594548 KB Output is correct
50 Correct 646 ms 594504 KB Output is correct
51 Correct 689 ms 593940 KB Output is correct
52 Correct 695 ms 593616 KB Output is correct
53 Correct 603 ms 594296 KB Output is correct
54 Correct 553 ms 594040 KB Output is correct
55 Correct 557 ms 594152 KB Output is correct
56 Correct 597 ms 594168 KB Output is correct
57 Correct 568 ms 594192 KB Output is correct
58 Correct 554 ms 593796 KB Output is correct
59 Correct 558 ms 593984 KB Output is correct
60 Correct 551 ms 593860 KB Output is correct
61 Correct 1936 ms 765848 KB Output is correct
62 Correct 3662 ms 959588 KB Output is correct
63 Correct 3682 ms 961456 KB Output is correct
64 Correct 3726 ms 961528 KB Output is correct
65 Correct 1108 ms 678896 KB Output is correct
66 Correct 1689 ms 761464 KB Output is correct
67 Correct 1703 ms 766064 KB Output is correct
68 Runtime error 2191 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
69 Halted 0 ms 0 KB -