oj.uz

Submission #157361

# Submission time Handle Problem Language Result Execution time Memory
157361 2019-10-11T03:18:41 Z qkxwsm Rectangles (IOI19_rect) C++14
49 / 100
 479 ms 181708 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 713

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<short> ev[MAXN][MAXN], eh[MAXN][MAXN], dv[MAXN][MAXN], dh[MAXN][MAXN];
ll ans;

ll count_rectangles(vector<vi> a)
{
	N = SZ(a); M = SZ(a[0]);
	FOR(i, 0, N)
	{
		vpi cand; cand.PB({INF, M + 1});
		FORD(j, M, 0)
		{
			while(cand.back().fi < a[i][j]) cand.pop_back();
			short idx = cand.back().se;
			if (idx < M && idx != j + 1)
			{
				eh[i][j + 1].PB(idx - 1);
			}
			cand.PB({a[i][j], j});
		}
		cand.clear(); cand.PB({INF, -2});
		FOR(j, 0, M)
		{
			while(cand.back().fi < a[i][j]) cand.pop_back();
			short idx = cand.back().se;
			if (idx >= 0 & idx != j - 1)
			{
				eh[i][idx + 1].PB(j - 1);
			}
			cand.PB({a[i][j], j});
		}
	}
	FOR(i, 0, M)
	{
		vpi cand; cand.PB({INF, N + 1});
		FORD(j, N, 0)
		{
			while(cand.back().fi < a[j][i]) cand.pop_back();
			short idx = cand.back().se;
			if (idx < N && idx != j + 1)
			{
				ev[j + 1][i].PB(idx - 1);
			}
			cand.PB({a[j][i], j});
		}
		cand.clear(); cand.PB({INF, -2});
		FOR(j, 0, N)
		{
			while(cand.back().fi < a[j][i]) cand.pop_back();
			short idx = cand.back().se;
			if (idx >= 0 && idx != j - 1)
			{
				ev[idx + 1][i].PB(j - 1);
			}
			cand.PB({a[j][i], j});
		}
	}
	//log factor here.
	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]));
		}
	}
	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];
			}
		}
	}
	//log factor here too.
	FOR(i, 1, N - 1)
	{
		FOR(j, 1, M - 1)
		{
			vpi ps;
			FOR(k, 0, SZ(eh[i][j]))
			{
				ps.PB({dh[i][j][k], eh[i][j][k]});
			}
			sort(ALL(ps));
			ordered_set<pii> ord;
			FOR(k, 0, SZ(ps))
			{
				ord.insert({ps[k].se, k});
			}
			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();
		}
	}
	return ans;
}

Compilation message

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:72: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 47 ms 48120 KB Output is correct
2 Correct 48 ms 48148 KB Output is correct
3 Correct 48 ms 48248 KB Output is correct
4 Correct 47 ms 48248 KB Output is correct
5 Correct 46 ms 48120 KB Output is correct
6 Correct 48 ms 48120 KB Output is correct
7 Correct 46 ms 48120 KB Output is correct
8 Correct 47 ms 48120 KB Output is correct
9 Correct 47 ms 48128 KB Output is correct
10 Correct 48 ms 48120 KB Output is correct
11 Correct 48 ms 48120 KB Output is correct
12 Correct 48 ms 48120 KB Output is correct
13 Correct 48 ms 47992 KB Output is correct
14 Correct 48 ms 48120 KB Output is correct
15 Correct 47 ms 48120 KB Output is correct
16 Correct 47 ms 47996 KB Output is correct
17 Correct 46 ms 48120 KB Output is correct
18 Correct 46 ms 48124 KB Output is correct
19 Correct 47 ms 48120 KB Output is correct
20 Correct 47 ms 48100 KB Output is correct
21 Correct 47 ms 48120 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 48120 KB Output is correct
2 Correct 48 ms 48148 KB Output is correct
3 Correct 48 ms 48248 KB Output is correct
4 Correct 47 ms 48248 KB Output is correct
5 Correct 46 ms 48120 KB Output is correct
6 Correct 48 ms 48120 KB Output is correct
7 Correct 46 ms 48120 KB Output is correct
8 Correct 47 ms 48120 KB Output is correct
9 Correct 47 ms 48128 KB Output is correct
10 Correct 48 ms 48120 KB Output is correct
11 Correct 48 ms 48120 KB Output is correct
12 Correct 48 ms 48120 KB Output is correct
13 Correct 48 ms 47992 KB Output is correct
14 Correct 48 ms 48120 KB Output is correct
15 Correct 47 ms 48120 KB Output is correct
16 Correct 47 ms 47996 KB Output is correct
17 Correct 51 ms 48888 KB Output is correct
18 Correct 51 ms 48908 KB Output is correct
19 Correct 51 ms 48892 KB Output is correct
20 Correct 50 ms 48376 KB Output is correct
21 Correct 61 ms 48564 KB Output is correct
22 Correct 62 ms 48504 KB Output is correct
23 Correct 51 ms 48480 KB Output is correct
24 Correct 58 ms 48340 KB Output is correct
25 Correct 46 ms 48120 KB Output is correct
26 Correct 46 ms 48124 KB Output is correct
27 Correct 47 ms 48120 KB Output is correct
28 Correct 47 ms 48100 KB Output is correct
29 Correct 47 ms 48120 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 48120 KB Output is correct
2 Correct 48 ms 48148 KB Output is correct
3 Correct 48 ms 48248 KB Output is correct
4 Correct 47 ms 48248 KB Output is correct
5 Correct 46 ms 48120 KB Output is correct
6 Correct 48 ms 48120 KB Output is correct
7 Correct 46 ms 48120 KB Output is correct
8 Correct 47 ms 48120 KB Output is correct
9 Correct 47 ms 48128 KB Output is correct
10 Correct 48 ms 48120 KB Output is correct
11 Correct 48 ms 48120 KB Output is correct
12 Correct 48 ms 48120 KB Output is correct
13 Correct 48 ms 47992 KB Output is correct
14 Correct 48 ms 48120 KB Output is correct
15 Correct 47 ms 48120 KB Output is correct
16 Correct 47 ms 47996 KB Output is correct
17 Correct 51 ms 48888 KB Output is correct
18 Correct 51 ms 48908 KB Output is correct
19 Correct 51 ms 48892 KB Output is correct
20 Correct 50 ms 48376 KB Output is correct
21 Correct 61 ms 48564 KB Output is correct
22 Correct 62 ms 48504 KB Output is correct
23 Correct 51 ms 48480 KB Output is correct
24 Correct 58 ms 48340 KB Output is correct
25 Correct 89 ms 53636 KB Output is correct
26 Correct 87 ms 53624 KB Output is correct
27 Correct 90 ms 53624 KB Output is correct
28 Correct 68 ms 50168 KB Output is correct
29 Correct 74 ms 51192 KB Output is correct
30 Correct 88 ms 51192 KB Output is correct
31 Correct 74 ms 50940 KB Output is correct
32 Correct 72 ms 50936 KB Output is correct
33 Correct 46 ms 48120 KB Output is correct
34 Correct 46 ms 48124 KB Output is correct
35 Correct 47 ms 48120 KB Output is correct
36 Correct 47 ms 48100 KB Output is correct
37 Correct 47 ms 48120 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 48120 KB Output is correct
2 Correct 48 ms 48148 KB Output is correct
3 Correct 48 ms 48248 KB Output is correct
4 Correct 47 ms 48248 KB Output is correct
5 Correct 46 ms 48120 KB Output is correct
6 Correct 48 ms 48120 KB Output is correct
7 Correct 46 ms 48120 KB Output is correct
8 Correct 47 ms 48120 KB Output is correct
9 Correct 47 ms 48128 KB Output is correct
10 Correct 48 ms 48120 KB Output is correct
11 Correct 48 ms 48120 KB Output is correct
12 Correct 48 ms 48120 KB Output is correct
13 Correct 48 ms 47992 KB Output is correct
14 Correct 48 ms 48120 KB Output is correct
15 Correct 47 ms 48120 KB Output is correct
16 Correct 47 ms 47996 KB Output is correct
17 Correct 51 ms 48888 KB Output is correct
18 Correct 51 ms 48908 KB Output is correct
19 Correct 51 ms 48892 KB Output is correct
20 Correct 50 ms 48376 KB Output is correct
21 Correct 61 ms 48564 KB Output is correct
22 Correct 62 ms 48504 KB Output is correct
23 Correct 51 ms 48480 KB Output is correct
24 Correct 58 ms 48340 KB Output is correct
25 Correct 89 ms 53636 KB Output is correct
26 Correct 87 ms 53624 KB Output is correct
27 Correct 90 ms 53624 KB Output is correct
28 Correct 68 ms 50168 KB Output is correct
29 Correct 74 ms 51192 KB Output is correct
30 Correct 88 ms 51192 KB Output is correct
31 Correct 74 ms 50940 KB Output is correct
32 Correct 72 ms 50936 KB Output is correct
33 Correct 255 ms 85740 KB Output is correct
34 Correct 232 ms 71672 KB Output is correct
35 Correct 213 ms 71540 KB Output is correct
36 Correct 191 ms 57636 KB Output is correct
37 Correct 435 ms 116408 KB Output is correct
38 Correct 435 ms 116216 KB Output is correct
39 Correct 443 ms 116632 KB Output is correct
40 Correct 415 ms 112364 KB Output is correct
41 Correct 266 ms 68344 KB Output is correct
42 Correct 324 ms 73464 KB Output is correct
43 Correct 432 ms 84240 KB Output is correct
44 Correct 437 ms 86400 KB Output is correct
45 Correct 239 ms 67192 KB Output is correct
46 Correct 235 ms 67192 KB Output is correct
47 Correct 430 ms 82872 KB Output is correct
48 Correct 479 ms 83956 KB Output is correct
49 Correct 46 ms 48120 KB Output is correct
50 Correct 46 ms 48124 KB Output is correct
51 Correct 47 ms 48120 KB Output is correct
52 Correct 47 ms 48100 KB Output is correct
53 Correct 47 ms 48120 KB Output is correct

Subtask #5
0 / 10.0

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

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 47996 KB Output is correct
2 Runtime error 400 ms 181708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 48120 KB Output is correct
2 Correct 48 ms 48148 KB Output is correct
3 Correct 48 ms 48248 KB Output is correct
4 Correct 47 ms 48248 KB Output is correct
5 Correct 46 ms 48120 KB Output is correct
6 Correct 48 ms 48120 KB Output is correct
7 Correct 46 ms 48120 KB Output is correct
8 Correct 47 ms 48120 KB Output is correct
9 Correct 47 ms 48128 KB Output is correct
10 Correct 48 ms 48120 KB Output is correct
11 Correct 48 ms 48120 KB Output is correct
12 Correct 48 ms 48120 KB Output is correct
13 Correct 48 ms 47992 KB Output is correct
14 Correct 48 ms 48120 KB Output is correct
15 Correct 47 ms 48120 KB Output is correct
16 Correct 47 ms 47996 KB Output is correct
17 Correct 51 ms 48888 KB Output is correct
18 Correct 51 ms 48908 KB Output is correct
19 Correct 51 ms 48892 KB Output is correct
20 Correct 50 ms 48376 KB Output is correct
21 Correct 61 ms 48564 KB Output is correct
22 Correct 62 ms 48504 KB Output is correct
23 Correct 51 ms 48480 KB Output is correct
24 Correct 58 ms 48340 KB Output is correct
25 Correct 89 ms 53636 KB Output is correct
26 Correct 87 ms 53624 KB Output is correct
27 Correct 90 ms 53624 KB Output is correct
28 Correct 68 ms 50168 KB Output is correct
29 Correct 74 ms 51192 KB Output is correct
30 Correct 88 ms 51192 KB Output is correct
31 Correct 74 ms 50940 KB Output is correct
32 Correct 72 ms 50936 KB Output is correct
33 Correct 255 ms 85740 KB Output is correct
34 Correct 232 ms 71672 KB Output is correct
35 Correct 213 ms 71540 KB Output is correct
36 Correct 191 ms 57636 KB Output is correct
37 Correct 435 ms 116408 KB Output is correct
38 Correct 435 ms 116216 KB Output is correct
39 Correct 443 ms 116632 KB Output is correct
40 Correct 415 ms 112364 KB Output is correct
41 Correct 266 ms 68344 KB Output is correct
42 Correct 324 ms 73464 KB Output is correct
43 Correct 432 ms 84240 KB Output is correct
44 Correct 437 ms 86400 KB Output is correct
45 Correct 239 ms 67192 KB Output is correct
46 Correct 235 ms 67192 KB Output is correct
47 Correct 430 ms 82872 KB Output is correct
48 Correct 479 ms 83956 KB Output is correct
49 Incorrect 54 ms 48624 KB Output isn't correct
50 Halted 0 ms 0 KB -