oj.uz

Submission #157365

# Submission time Handle Problem Language Result Execution time Memory
157365 2019-10-11T03:28:29 Z qkxwsm Rectangles (IOI19_rect) C++14
49 / 100
 1167 ms 661076 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<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});
		}
	}
	if (N > 700 || M > 700) return 0;
	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:73: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 557 ms 593644 KB Output is correct
2 Correct 560 ms 593656 KB Output is correct
3 Correct 554 ms 593644 KB Output is correct
4 Correct 586 ms 593640 KB Output is correct
5 Correct 559 ms 593628 KB Output is correct
6 Correct 557 ms 593548 KB Output is correct
7 Correct 570 ms 593596 KB Output is correct
8 Correct 563 ms 593464 KB Output is correct
9 Correct 560 ms 593528 KB Output is correct
10 Correct 554 ms 593528 KB Output is correct
11 Correct 551 ms 593608 KB Output is correct
12 Correct 552 ms 593708 KB Output is correct
13 Correct 558 ms 593656 KB Output is correct
14 Correct 554 ms 593628 KB Output is correct
15 Correct 554 ms 593528 KB Output is correct
16 Correct 557 ms 593528 KB Output is correct
17 Correct 581 ms 593708 KB Output is correct
18 Correct 566 ms 593528 KB Output is correct
19 Correct 557 ms 593648 KB Output is correct
20 Correct 558 ms 593652 KB Output is correct
21 Correct 580 ms 593500 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 593644 KB Output is correct
2 Correct 560 ms 593656 KB Output is correct
3 Correct 554 ms 593644 KB Output is correct
4 Correct 586 ms 593640 KB Output is correct
5 Correct 559 ms 593628 KB Output is correct
6 Correct 557 ms 593548 KB Output is correct
7 Correct 570 ms 593596 KB Output is correct
8 Correct 563 ms 593464 KB Output is correct
9 Correct 560 ms 593528 KB Output is correct
10 Correct 554 ms 593528 KB Output is correct
11 Correct 551 ms 593608 KB Output is correct
12 Correct 552 ms 593708 KB Output is correct
13 Correct 558 ms 593656 KB Output is correct
14 Correct 554 ms 593628 KB Output is correct
15 Correct 554 ms 593528 KB Output is correct
16 Correct 557 ms 593528 KB Output is correct
17 Correct 588 ms 594396 KB Output is correct
18 Correct 560 ms 594300 KB Output is correct
19 Correct 559 ms 594384 KB Output is correct
20 Correct 556 ms 593828 KB Output is correct
21 Correct 559 ms 594040 KB Output is correct
22 Correct 559 ms 594040 KB Output is correct
23 Correct 551 ms 593964 KB Output is correct
24 Correct 556 ms 593676 KB Output is correct
25 Correct 581 ms 593708 KB Output is correct
26 Correct 566 ms 593528 KB Output is correct
27 Correct 557 ms 593648 KB Output is correct
28 Correct 558 ms 593652 KB Output is correct
29 Correct 580 ms 593500 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 593644 KB Output is correct
2 Correct 560 ms 593656 KB Output is correct
3 Correct 554 ms 593644 KB Output is correct
4 Correct 586 ms 593640 KB Output is correct
5 Correct 559 ms 593628 KB Output is correct
6 Correct 557 ms 593548 KB Output is correct
7 Correct 570 ms 593596 KB Output is correct
8 Correct 563 ms 593464 KB Output is correct
9 Correct 560 ms 593528 KB Output is correct
10 Correct 554 ms 593528 KB Output is correct
11 Correct 551 ms 593608 KB Output is correct
12 Correct 552 ms 593708 KB Output is correct
13 Correct 558 ms 593656 KB Output is correct
14 Correct 554 ms 593628 KB Output is correct
15 Correct 554 ms 593528 KB Output is correct
16 Correct 557 ms 593528 KB Output is correct
17 Correct 588 ms 594396 KB Output is correct
18 Correct 560 ms 594300 KB Output is correct
19 Correct 559 ms 594384 KB Output is correct
20 Correct 556 ms 593828 KB Output is correct
21 Correct 559 ms 594040 KB Output is correct
22 Correct 559 ms 594040 KB Output is correct
23 Correct 551 ms 593964 KB Output is correct
24 Correct 556 ms 593676 KB Output is correct
25 Correct 584 ms 598800 KB Output is correct
26 Correct 585 ms 598764 KB Output is correct
27 Correct 647 ms 598920 KB Output is correct
28 Correct 572 ms 595576 KB Output is correct
29 Correct 577 ms 596344 KB Output is correct
30 Correct 586 ms 596508 KB Output is correct
31 Correct 580 ms 596192 KB Output is correct
32 Correct 576 ms 596176 KB Output is correct
33 Correct 581 ms 593708 KB Output is correct
34 Correct 566 ms 593528 KB Output is correct
35 Correct 557 ms 593648 KB Output is correct
36 Correct 558 ms 593652 KB Output is correct
37 Correct 580 ms 593500 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 593644 KB Output is correct
2 Correct 560 ms 593656 KB Output is correct
3 Correct 554 ms 593644 KB Output is correct
4 Correct 586 ms 593640 KB Output is correct
5 Correct 559 ms 593628 KB Output is correct
6 Correct 557 ms 593548 KB Output is correct
7 Correct 570 ms 593596 KB Output is correct
8 Correct 563 ms 593464 KB Output is correct
9 Correct 560 ms 593528 KB Output is correct
10 Correct 554 ms 593528 KB Output is correct
11 Correct 551 ms 593608 KB Output is correct
12 Correct 552 ms 593708 KB Output is correct
13 Correct 558 ms 593656 KB Output is correct
14 Correct 554 ms 593628 KB Output is correct
15 Correct 554 ms 593528 KB Output is correct
16 Correct 557 ms 593528 KB Output is correct
17 Correct 588 ms 594396 KB Output is correct
18 Correct 560 ms 594300 KB Output is correct
19 Correct 559 ms 594384 KB Output is correct
20 Correct 556 ms 593828 KB Output is correct
21 Correct 559 ms 594040 KB Output is correct
22 Correct 559 ms 594040 KB Output is correct
23 Correct 551 ms 593964 KB Output is correct
24 Correct 556 ms 593676 KB Output is correct
25 Correct 584 ms 598800 KB Output is correct
26 Correct 585 ms 598764 KB Output is correct
27 Correct 647 ms 598920 KB Output is correct
28 Correct 572 ms 595576 KB Output is correct
29 Correct 577 ms 596344 KB Output is correct
30 Correct 586 ms 596508 KB Output is correct
31 Correct 580 ms 596192 KB Output is correct
32 Correct 576 ms 596176 KB Output is correct
33 Correct 769 ms 628060 KB Output is correct
34 Correct 733 ms 614076 KB Output is correct
35 Correct 775 ms 613972 KB Output is correct
36 Correct 773 ms 600052 KB Output is correct
37 Correct 958 ms 658680 KB Output is correct
38 Correct 949 ms 658552 KB Output is correct
39 Correct 1121 ms 658888 KB Output is correct
40 Correct 942 ms 654236 KB Output is correct
41 Correct 772 ms 612848 KB Output is correct
42 Correct 874 ms 617984 KB Output is correct
43 Correct 955 ms 628040 KB Output is correct
44 Correct 939 ms 628064 KB Output is correct
45 Correct 736 ms 610812 KB Output is correct
46 Correct 740 ms 610788 KB Output is correct
47 Correct 927 ms 625560 KB Output is correct
48 Correct 917 ms 625648 KB Output is correct
49 Correct 581 ms 593708 KB Output is correct
50 Correct 566 ms 593528 KB Output is correct
51 Correct 557 ms 593648 KB Output is correct
52 Correct 558 ms 593652 KB Output is correct
53 Correct 580 ms 593500 KB Output is correct

Subtask #5
0 / 10.0

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

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 593544 KB Output is correct
2 Incorrect 1167 ms 661076 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 593644 KB Output is correct
2 Correct 560 ms 593656 KB Output is correct
3 Correct 554 ms 593644 KB Output is correct
4 Correct 586 ms 593640 KB Output is correct
5 Correct 559 ms 593628 KB Output is correct
6 Correct 557 ms 593548 KB Output is correct
7 Correct 570 ms 593596 KB Output is correct
8 Correct 563 ms 593464 KB Output is correct
9 Correct 560 ms 593528 KB Output is correct
10 Correct 554 ms 593528 KB Output is correct
11 Correct 551 ms 593608 KB Output is correct
12 Correct 552 ms 593708 KB Output is correct
13 Correct 558 ms 593656 KB Output is correct
14 Correct 554 ms 593628 KB Output is correct
15 Correct 554 ms 593528 KB Output is correct
16 Correct 557 ms 593528 KB Output is correct
17 Correct 588 ms 594396 KB Output is correct
18 Correct 560 ms 594300 KB Output is correct
19 Correct 559 ms 594384 KB Output is correct
20 Correct 556 ms 593828 KB Output is correct
21 Correct 559 ms 594040 KB Output is correct
22 Correct 559 ms 594040 KB Output is correct
23 Correct 551 ms 593964 KB Output is correct
24 Correct 556 ms 593676 KB Output is correct
25 Correct 584 ms 598800 KB Output is correct
26 Correct 585 ms 598764 KB Output is correct
27 Correct 647 ms 598920 KB Output is correct
28 Correct 572 ms 595576 KB Output is correct
29 Correct 577 ms 596344 KB Output is correct
30 Correct 586 ms 596508 KB Output is correct
31 Correct 580 ms 596192 KB Output is correct
32 Correct 576 ms 596176 KB Output is correct
33 Correct 769 ms 628060 KB Output is correct
34 Correct 733 ms 614076 KB Output is correct
35 Correct 775 ms 613972 KB Output is correct
36 Correct 773 ms 600052 KB Output is correct
37 Correct 958 ms 658680 KB Output is correct
38 Correct 949 ms 658552 KB Output is correct
39 Correct 1121 ms 658888 KB Output is correct
40 Correct 942 ms 654236 KB Output is correct
41 Correct 772 ms 612848 KB Output is correct
42 Correct 874 ms 617984 KB Output is correct
43 Correct 955 ms 628040 KB Output is correct
44 Correct 939 ms 628064 KB Output is correct
45 Correct 736 ms 610812 KB Output is correct
46 Correct 740 ms 610788 KB Output is correct
47 Correct 927 ms 625560 KB Output is correct
48 Correct 917 ms 625648 KB Output is correct
49 Incorrect 637 ms 594052 KB Output isn't correct
50 Halted 0 ms 0 KB -