oj.uz

Submission #157345

# Submission time Handle Problem Language Result Execution time Memory
157345 2019-10-11T02:34:48 Z qkxwsm Rectangles (IOI19_rect) C++14
72 / 100
 3559 ms 1048580 KB 
#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

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;

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)
		{
			FOR(k, 0, SZ(ev[i][j]))
			{
				int x = ev[i][j][k];
				FOR(m, 0, SZ(eh[i][j]))
				{
					int y = eh[i][j][m];
					if (dh[i][j][m] >= x && dv[i][j][k] >= y)
					{
						// cout << i << ',' << j << "=>" << x << ',' << y << endl;
						ans++;
					}
				}
			}
		}
	}
	//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:96: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 560 ms 593728 KB Output is correct
2 Correct 559 ms 594168 KB Output is correct
3 Correct 558 ms 594136 KB Output is correct
4 Correct 562 ms 594164 KB Output is correct
5 Correct 556 ms 594172 KB Output is correct
6 Correct 556 ms 594148 KB Output is correct
7 Correct 555 ms 594132 KB Output is correct
8 Correct 555 ms 593772 KB Output is correct
9 Correct 555 ms 594088 KB Output is correct
10 Correct 553 ms 594040 KB Output is correct
11 Correct 554 ms 594080 KB Output is correct
12 Correct 556 ms 594124 KB Output is correct
13 Correct 551 ms 593528 KB Output is correct
14 Correct 552 ms 593744 KB Output is correct
15 Correct 555 ms 593784 KB Output is correct
16 Correct 558 ms 593648 KB Output is correct
17 Correct 558 ms 593556 KB Output is correct
18 Correct 552 ms 593648 KB Output is correct
19 Correct 555 ms 594152 KB Output is correct
20 Correct 556 ms 594124 KB Output is correct
21 Correct 600 ms 593688 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 593728 KB Output is correct
2 Correct 559 ms 594168 KB Output is correct
3 Correct 558 ms 594136 KB Output is correct
4 Correct 562 ms 594164 KB Output is correct
5 Correct 556 ms 594172 KB Output is correct
6 Correct 556 ms 594148 KB Output is correct
7 Correct 555 ms 594132 KB Output is correct
8 Correct 555 ms 593772 KB Output is correct
9 Correct 555 ms 594088 KB Output is correct
10 Correct 553 ms 594040 KB Output is correct
11 Correct 554 ms 594080 KB Output is correct
12 Correct 556 ms 594124 KB Output is correct
13 Correct 551 ms 593528 KB Output is correct
14 Correct 552 ms 593744 KB Output is correct
15 Correct 555 ms 593784 KB Output is correct
16 Correct 558 ms 593648 KB Output is correct
17 Correct 559 ms 595756 KB Output is correct
18 Correct 557 ms 595800 KB Output is correct
19 Correct 562 ms 595960 KB Output is correct
20 Correct 555 ms 595328 KB Output is correct
21 Correct 560 ms 595520 KB Output is correct
22 Correct 558 ms 595548 KB Output is correct
23 Correct 566 ms 595448 KB Output is correct
24 Correct 558 ms 595320 KB Output is correct
25 Correct 558 ms 593556 KB Output is correct
26 Correct 552 ms 593648 KB Output is correct
27 Correct 555 ms 594152 KB Output is correct
28 Correct 556 ms 594124 KB Output is correct
29 Correct 600 ms 593688 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 593728 KB Output is correct
2 Correct 559 ms 594168 KB Output is correct
3 Correct 558 ms 594136 KB Output is correct
4 Correct 562 ms 594164 KB Output is correct
5 Correct 556 ms 594172 KB Output is correct
6 Correct 556 ms 594148 KB Output is correct
7 Correct 555 ms 594132 KB Output is correct
8 Correct 555 ms 593772 KB Output is correct
9 Correct 555 ms 594088 KB Output is correct
10 Correct 553 ms 594040 KB Output is correct
11 Correct 554 ms 594080 KB Output is correct
12 Correct 556 ms 594124 KB Output is correct
13 Correct 551 ms 593528 KB Output is correct
14 Correct 552 ms 593744 KB Output is correct
15 Correct 555 ms 593784 KB Output is correct
16 Correct 558 ms 593648 KB Output is correct
17 Correct 559 ms 595756 KB Output is correct
18 Correct 557 ms 595800 KB Output is correct
19 Correct 562 ms 595960 KB Output is correct
20 Correct 555 ms 595328 KB Output is correct
21 Correct 560 ms 595520 KB Output is correct
22 Correct 558 ms 595548 KB Output is correct
23 Correct 566 ms 595448 KB Output is correct
24 Correct 558 ms 595320 KB Output is correct
25 Correct 652 ms 603140 KB Output is correct
26 Correct 680 ms 603128 KB Output is correct
27 Correct 625 ms 603224 KB Output is correct
28 Correct 705 ms 599564 KB Output is correct
29 Correct 575 ms 600656 KB Output is correct
30 Correct 590 ms 600740 KB Output is correct
31 Correct 578 ms 600424 KB Output is correct
32 Correct 576 ms 600420 KB Output is correct
33 Correct 558 ms 593556 KB Output is correct
34 Correct 552 ms 593648 KB Output is correct
35 Correct 555 ms 594152 KB Output is correct
36 Correct 556 ms 594124 KB Output is correct
37 Correct 600 ms 593688 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 593728 KB Output is correct
2 Correct 559 ms 594168 KB Output is correct
3 Correct 558 ms 594136 KB Output is correct
4 Correct 562 ms 594164 KB Output is correct
5 Correct 556 ms 594172 KB Output is correct
6 Correct 556 ms 594148 KB Output is correct
7 Correct 555 ms 594132 KB Output is correct
8 Correct 555 ms 593772 KB Output is correct
9 Correct 555 ms 594088 KB Output is correct
10 Correct 553 ms 594040 KB Output is correct
11 Correct 554 ms 594080 KB Output is correct
12 Correct 556 ms 594124 KB Output is correct
13 Correct 551 ms 593528 KB Output is correct
14 Correct 552 ms 593744 KB Output is correct
15 Correct 555 ms 593784 KB Output is correct
16 Correct 558 ms 593648 KB Output is correct
17 Correct 559 ms 595756 KB Output is correct
18 Correct 557 ms 595800 KB Output is correct
19 Correct 562 ms 595960 KB Output is correct
20 Correct 555 ms 595328 KB Output is correct
21 Correct 560 ms 595520 KB Output is correct
22 Correct 558 ms 595548 KB Output is correct
23 Correct 566 ms 595448 KB Output is correct
24 Correct 558 ms 595320 KB Output is correct
25 Correct 652 ms 603140 KB Output is correct
26 Correct 680 ms 603128 KB Output is correct
27 Correct 625 ms 603224 KB Output is correct
28 Correct 705 ms 599564 KB Output is correct
29 Correct 575 ms 600656 KB Output is correct
30 Correct 590 ms 600740 KB Output is correct
31 Correct 578 ms 600424 KB Output is correct
32 Correct 576 ms 600420 KB Output is correct
33 Correct 760 ms 651968 KB Output is correct
34 Correct 703 ms 639216 KB Output is correct
35 Correct 731 ms 639352 KB Output is correct
36 Correct 806 ms 626300 KB Output is correct
37 Correct 969 ms 682744 KB Output is correct
38 Correct 981 ms 682616 KB Output is correct
39 Correct 961 ms 683012 KB Output is correct
40 Correct 916 ms 677420 KB Output is correct
41 Correct 765 ms 634700 KB Output is correct
42 Correct 878 ms 639692 KB Output is correct
43 Correct 904 ms 651268 KB Output is correct
44 Correct 932 ms 653304 KB Output is correct
45 Correct 729 ms 628952 KB Output is correct
46 Correct 716 ms 623268 KB Output is correct
47 Correct 883 ms 649680 KB Output is correct
48 Correct 889 ms 650632 KB Output is correct
49 Correct 558 ms 593556 KB Output is correct
50 Correct 552 ms 593648 KB Output is correct
51 Correct 555 ms 594152 KB Output is correct
52 Correct 556 ms 594124 KB Output is correct
53 Correct 600 ms 593688 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 594500 KB Output is correct
2 Correct 572 ms 594644 KB Output is correct
3 Correct 666 ms 593932 KB Output is correct
4 Correct 677 ms 593800 KB Output is correct
5 Correct 623 ms 594128 KB Output is correct
6 Correct 607 ms 594168 KB Output is correct
7 Correct 662 ms 594140 KB Output is correct
8 Correct 595 ms 593996 KB Output is correct
9 Correct 557 ms 594132 KB Output is correct
10 Correct 552 ms 593784 KB Output is correct
11 Correct 594 ms 593912 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 592 ms 593912 KB Output is correct
2 Correct 2115 ms 769952 KB Output is correct
3 Correct 3556 ms 959976 KB Output is correct
4 Correct 3511 ms 961596 KB Output is correct
5 Correct 3559 ms 961676 KB Output is correct
6 Correct 1105 ms 679220 KB Output is correct
7 Correct 1608 ms 761768 KB Output is correct
8 Correct 1670 ms 766500 KB Output is correct
9 Correct 558 ms 593556 KB Output is correct
10 Correct 552 ms 593648 KB Output is correct
11 Correct 555 ms 594152 KB Output is correct
12 Correct 556 ms 594124 KB Output is correct
13 Correct 600 ms 593688 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 593728 KB Output is correct
2 Correct 559 ms 594168 KB Output is correct
3 Correct 558 ms 594136 KB Output is correct
4 Correct 562 ms 594164 KB Output is correct
5 Correct 556 ms 594172 KB Output is correct
6 Correct 556 ms 594148 KB Output is correct
7 Correct 555 ms 594132 KB Output is correct
8 Correct 555 ms 593772 KB Output is correct
9 Correct 555 ms 594088 KB Output is correct
10 Correct 553 ms 594040 KB Output is correct
11 Correct 554 ms 594080 KB Output is correct
12 Correct 556 ms 594124 KB Output is correct
13 Correct 551 ms 593528 KB Output is correct
14 Correct 552 ms 593744 KB Output is correct
15 Correct 555 ms 593784 KB Output is correct
16 Correct 558 ms 593648 KB Output is correct
17 Correct 559 ms 595756 KB Output is correct
18 Correct 557 ms 595800 KB Output is correct
19 Correct 562 ms 595960 KB Output is correct
20 Correct 555 ms 595328 KB Output is correct
21 Correct 560 ms 595520 KB Output is correct
22 Correct 558 ms 595548 KB Output is correct
23 Correct 566 ms 595448 KB Output is correct
24 Correct 558 ms 595320 KB Output is correct
25 Correct 652 ms 603140 KB Output is correct
26 Correct 680 ms 603128 KB Output is correct
27 Correct 625 ms 603224 KB Output is correct
28 Correct 705 ms 599564 KB Output is correct
29 Correct 575 ms 600656 KB Output is correct
30 Correct 590 ms 600740 KB Output is correct
31 Correct 578 ms 600424 KB Output is correct
32 Correct 576 ms 600420 KB Output is correct
33 Correct 760 ms 651968 KB Output is correct
34 Correct 703 ms 639216 KB Output is correct
35 Correct 731 ms 639352 KB Output is correct
36 Correct 806 ms 626300 KB Output is correct
37 Correct 969 ms 682744 KB Output is correct
38 Correct 981 ms 682616 KB Output is correct
39 Correct 961 ms 683012 KB Output is correct
40 Correct 916 ms 677420 KB Output is correct
41 Correct 765 ms 634700 KB Output is correct
42 Correct 878 ms 639692 KB Output is correct
43 Correct 904 ms 651268 KB Output is correct
44 Correct 932 ms 653304 KB Output is correct
45 Correct 729 ms 628952 KB Output is correct
46 Correct 716 ms 623268 KB Output is correct
47 Correct 883 ms 649680 KB Output is correct
48 Correct 889 ms 650632 KB Output is correct
49 Correct 558 ms 594500 KB Output is correct
50 Correct 572 ms 594644 KB Output is correct
51 Correct 666 ms 593932 KB Output is correct
52 Correct 677 ms 593800 KB Output is correct
53 Correct 623 ms 594128 KB Output is correct
54 Correct 607 ms 594168 KB Output is correct
55 Correct 662 ms 594140 KB Output is correct
56 Correct 595 ms 593996 KB Output is correct
57 Correct 557 ms 594132 KB Output is correct
58 Correct 552 ms 593784 KB Output is correct
59 Correct 594 ms 593912 KB Output is correct
60 Correct 592 ms 593912 KB Output is correct
61 Correct 2115 ms 769952 KB Output is correct
62 Correct 3556 ms 959976 KB Output is correct
63 Correct 3511 ms 961596 KB Output is correct
64 Correct 3559 ms 961676 KB Output is correct
65 Correct 1105 ms 679220 KB Output is correct
66 Correct 1608 ms 761768 KB Output is correct
67 Correct 1670 ms 766500 KB Output is correct
68 Runtime error 2073 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
69 Halted 0 ms 0 KB -