oj.uz

Submission #421215

# Submission time Handle Problem Language Result Execution time Memory
421215 2021-06-08T21:31:37 Z MohamedAhmed04 Rectangles (IOI19_rect) C++14
100 / 100
 4126 ms 811704 KB 
#include <bits/stdc++.h>
#include "rect.h"
//#include "grader.cpp"

using namespace std ;

const int MAX = 2501 ;

vector<int>bit[MAX][MAX] ;
vector<int>v2[MAX][MAX] ;

int getidx(int i , int j , int x)
{
	int idx = upper_bound(v2[i][j].begin() , v2[i][j].end() , x) - v2[i][j].begin() ;
	return idx ;
}

void Add(int i2 , int j2 , int i , int x)
{
	int n = v2[i2][j2].size() ;
	for(; i <= n ; i += (i & (-i)))
		bit[i2][j2][i] += x ;
}

void Insert(int i2 , int j2 , int i)
{
	Add(i2 , j2 , getidx(i2 , j2 , i) , 1) ;
}

void Erase(int i2 , int j2 , int i)
{
	Add(i2 , j2 , getidx(i2 , j2 , i) , -1) ;
}

int get(int i2 , int j2 , int i)
{
	int sum = 0 ;
	for(; i > 0 ; i -= (i & (-i)))
		sum += bit[i2][j2][i] ;
	return sum ;
}

int query(int i2 , int j2 , int i)
{
	return get(i2 , j2 , getidx(i2 , j2 , i)) ;
}

void init(int i , int j)
{
	int n = v2[i][j].size() ;
	bit[i][j] = vector<int>(n+1 , 0) ;
	for(auto &x : v2[i][j])
		Insert(i , j , x) ;
}


vector<int>candi[MAX] ;
stack<int>st[MAX] ;
vector<bool>mark[MAX] ;

int n , m ;

int calc(int i , int j , int i2 , int last)
{
	int j2 = j-1 ;
	i2++ ;
	if(j2 < 0 || i2 >= i)
		return 0ll ;
	return (query(i2 , j2 , last+1) - query(i2 , j2 , j)) ;
}

vector< vector<int> >a ;
vector<int>erased ;
stack<int>st2 ;

void AddRow(int i)
{
	while(st2.size())
		st2.pop() ;
	for(int j = m-1 ; j >= 0 ; --j)
	{
		while(st2.size() && a[i][j] > a[i][st2.top()])
			v2[i][j].push_back(st2.top()) , st2.pop() ;
		if(st2.size())
			v2[i][j].push_back(st2.top()) ;
		while(st2.size() && a[i][st2.top()] == a[i][j])
			st2.pop() ;
		st2.push(j) ;
		sort(v2[i][j].begin() , v2[i][j].end()) ;
		init(i , j) ;
	}
	if(!i)
		return ;
	for(int j = 0 ; j < m ; ++j)
	{
		erased.clear() ;
		for(auto &k : v2[i-1][j])
		{
			if(!binary_search(v2[i][j].begin() , v2[i][j].end() , k))
				erased.push_back(k) ;
		}
		for(auto &k : erased)
		{
			for(int i2 = i-1 ; i2 >= 0 ; --i2)
			{
				if(!binary_search(v2[i2][j].begin() , v2[i2][j].end() , k))
					break ;
				Erase(i2 , j , k) ;
			}
		}
	}
}

long long count_rectangles(std::vector<std::vector<int> > v) 
{
	a = v ;
	n = a.size() , m = a[0].size() ;
	long long ans = 0 ;
	for(int i = 0 ; i < n ; ++i)
	{
		for(int j = 0 ; j < m ; ++j)
		{
			while(st[j].size() && a[i][j] > a[st[j].top()][j])
				candi[j].push_back(st[j].top()) , st[j].pop() ;
			if(st[j].size())
				candi[j].push_back(st[j].top()) ;
			while(st[j].size() && a[st[j].top()][j] == a[i][j])
				st[j].pop() ;
			st[j].push(i) ;
			sort(candi[j].begin() , candi[j].end()) ;
			mark[j] = vector<bool>(candi[j].size() , 0) ;
		}
		for(int j = 0 ; j < m ; ++j)
		{
			for(auto &i2 : candi[j])
			{
				int idx = lower_bound(candi[j].begin() , candi[j].end() , i2) - candi[j].begin() ;
				if(mark[j][idx])
					continue ;
				int last = j ;
				for(int k = j ; k < m ; ++k)
				{
					if(!binary_search(candi[k].begin() , candi[k].end() , i2))
						break ;
					last = k ;
				}
				for(int k = j ; k <= last ; ++k)
				{
					ans += calc(i , k , i2 , last) ;
					if(k != j)
					{
						idx = lower_bound(candi[k].begin() , candi[k].end() , i2) - candi[k].begin() ;
						mark[k][idx] = 1 ;
					}
				}
			}
			candi[j].clear() , mark[j].clear() ;
		}
		AddRow(i) ;
	}
	return ans ;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 295876 KB Output is correct
2 Correct 158 ms 295872 KB Output is correct
3 Correct 163 ms 295888 KB Output is correct
4 Correct 160 ms 295876 KB Output is correct
5 Correct 159 ms 295876 KB Output is correct
6 Correct 161 ms 295884 KB Output is correct
7 Correct 160 ms 295876 KB Output is correct
8 Correct 160 ms 295880 KB Output is correct
9 Correct 161 ms 295876 KB Output is correct
10 Correct 163 ms 295860 KB Output is correct
11 Correct 161 ms 295876 KB Output is correct
12 Correct 162 ms 295876 KB Output is correct
13 Correct 157 ms 295852 KB Output is correct
14 Correct 161 ms 295876 KB Output is correct
15 Correct 161 ms 295792 KB Output is correct
16 Correct 157 ms 295876 KB Output is correct
17 Correct 163 ms 295788 KB Output is correct
18 Correct 161 ms 295808 KB Output is correct
19 Correct 160 ms 295916 KB Output is correct
20 Correct 158 ms 295900 KB Output is correct
21 Correct 162 ms 295876 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 295876 KB Output is correct
2 Correct 158 ms 295872 KB Output is correct
3 Correct 163 ms 295888 KB Output is correct
4 Correct 160 ms 295876 KB Output is correct
5 Correct 159 ms 295876 KB Output is correct
6 Correct 161 ms 295884 KB Output is correct
7 Correct 160 ms 295876 KB Output is correct
8 Correct 160 ms 295880 KB Output is correct
9 Correct 161 ms 295876 KB Output is correct
10 Correct 163 ms 295860 KB Output is correct
11 Correct 161 ms 295876 KB Output is correct
12 Correct 162 ms 295876 KB Output is correct
13 Correct 157 ms 295852 KB Output is correct
14 Correct 161 ms 295876 KB Output is correct
15 Correct 161 ms 295792 KB Output is correct
16 Correct 157 ms 295876 KB Output is correct
17 Correct 163 ms 295788 KB Output is correct
18 Correct 161 ms 295808 KB Output is correct
19 Correct 160 ms 295916 KB Output is correct
20 Correct 158 ms 295900 KB Output is correct
21 Correct 162 ms 295876 KB Output is correct
22 Correct 162 ms 296528 KB Output is correct
23 Correct 163 ms 296424 KB Output is correct
24 Correct 164 ms 296388 KB Output is correct
25 Correct 165 ms 296364 KB Output is correct
26 Correct 162 ms 296308 KB Output is correct
27 Correct 163 ms 296404 KB Output is correct
28 Correct 163 ms 296360 KB Output is correct
29 Correct 161 ms 296132 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 295876 KB Output is correct
2 Correct 158 ms 295872 KB Output is correct
3 Correct 163 ms 295888 KB Output is correct
4 Correct 160 ms 295876 KB Output is correct
5 Correct 159 ms 295876 KB Output is correct
6 Correct 161 ms 295884 KB Output is correct
7 Correct 160 ms 295876 KB Output is correct
8 Correct 160 ms 295880 KB Output is correct
9 Correct 161 ms 295876 KB Output is correct
10 Correct 163 ms 295860 KB Output is correct
11 Correct 161 ms 295876 KB Output is correct
12 Correct 162 ms 295876 KB Output is correct
13 Correct 157 ms 295852 KB Output is correct
14 Correct 161 ms 295876 KB Output is correct
15 Correct 161 ms 295792 KB Output is correct
16 Correct 157 ms 295876 KB Output is correct
17 Correct 162 ms 296528 KB Output is correct
18 Correct 163 ms 296424 KB Output is correct
19 Correct 164 ms 296388 KB Output is correct
20 Correct 165 ms 296364 KB Output is correct
21 Correct 162 ms 296308 KB Output is correct
22 Correct 163 ms 296404 KB Output is correct
23 Correct 163 ms 296360 KB Output is correct
24 Correct 161 ms 296132 KB Output is correct
25 Correct 163 ms 295788 KB Output is correct
26 Correct 161 ms 295808 KB Output is correct
27 Correct 160 ms 295916 KB Output is correct
28 Correct 158 ms 295900 KB Output is correct
29 Correct 162 ms 295876 KB Output is correct
30 Correct 174 ms 299244 KB Output is correct
31 Correct 174 ms 299204 KB Output is correct
32 Correct 179 ms 299428 KB Output is correct
33 Correct 174 ms 298904 KB Output is correct
34 Correct 180 ms 299016 KB Output is correct
35 Correct 180 ms 299204 KB Output is correct
36 Correct 178 ms 299152 KB Output is correct
37 Correct 178 ms 299168 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 295876 KB Output is correct
2 Correct 158 ms 295872 KB Output is correct
3 Correct 163 ms 295888 KB Output is correct
4 Correct 160 ms 295876 KB Output is correct
5 Correct 159 ms 295876 KB Output is correct
6 Correct 161 ms 295884 KB Output is correct
7 Correct 160 ms 295876 KB Output is correct
8 Correct 160 ms 295880 KB Output is correct
9 Correct 161 ms 295876 KB Output is correct
10 Correct 163 ms 295860 KB Output is correct
11 Correct 161 ms 295876 KB Output is correct
12 Correct 162 ms 295876 KB Output is correct
13 Correct 157 ms 295852 KB Output is correct
14 Correct 161 ms 295876 KB Output is correct
15 Correct 161 ms 295792 KB Output is correct
16 Correct 157 ms 295876 KB Output is correct
17 Correct 162 ms 296528 KB Output is correct
18 Correct 163 ms 296424 KB Output is correct
19 Correct 164 ms 296388 KB Output is correct
20 Correct 165 ms 296364 KB Output is correct
21 Correct 162 ms 296308 KB Output is correct
22 Correct 163 ms 296404 KB Output is correct
23 Correct 163 ms 296360 KB Output is correct
24 Correct 161 ms 296132 KB Output is correct
25 Correct 174 ms 299244 KB Output is correct
26 Correct 174 ms 299204 KB Output is correct
27 Correct 179 ms 299428 KB Output is correct
28 Correct 174 ms 298904 KB Output is correct
29 Correct 180 ms 299016 KB Output is correct
30 Correct 180 ms 299204 KB Output is correct
31 Correct 178 ms 299152 KB Output is correct
32 Correct 178 ms 299168 KB Output is correct
33 Correct 163 ms 295788 KB Output is correct
34 Correct 161 ms 295808 KB Output is correct
35 Correct 160 ms 295916 KB Output is correct
36 Correct 158 ms 295900 KB Output is correct
37 Correct 162 ms 295876 KB Output is correct
38 Correct 386 ms 334792 KB Output is correct
39 Correct 396 ms 336948 KB Output is correct
40 Correct 360 ms 333984 KB Output is correct
41 Correct 391 ms 336264 KB Output is correct
42 Correct 382 ms 336264 KB Output is correct
43 Correct 370 ms 336244 KB Output is correct
44 Correct 376 ms 336444 KB Output is correct
45 Correct 358 ms 333960 KB Output is correct
46 Correct 324 ms 332784 KB Output is correct
47 Correct 344 ms 332740 KB Output is correct
48 Correct 420 ms 333740 KB Output is correct
49 Correct 433 ms 333892 KB Output is correct
50 Correct 294 ms 315152 KB Output is correct
51 Correct 295 ms 315320 KB Output is correct
52 Correct 418 ms 333832 KB Output is correct
53 Correct 416 ms 333748 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 296580 KB Output is correct
2 Correct 162 ms 296476 KB Output is correct
3 Correct 160 ms 296524 KB Output is correct
4 Correct 158 ms 295876 KB Output is correct
5 Correct 162 ms 296572 KB Output is correct
6 Correct 166 ms 296672 KB Output is correct
7 Correct 165 ms 296644 KB Output is correct
8 Correct 163 ms 296644 KB Output is correct
9 Correct 164 ms 296608 KB Output is correct
10 Correct 160 ms 296132 KB Output is correct
11 Correct 160 ms 296344 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 295788 KB Output is correct
2 Correct 161 ms 295808 KB Output is correct
3 Correct 160 ms 295916 KB Output is correct
4 Correct 158 ms 295900 KB Output is correct
5 Correct 162 ms 295876 KB Output is correct
6 Correct 158 ms 295928 KB Output is correct
7 Correct 1167 ms 509984 KB Output is correct
8 Correct 2469 ms 764552 KB Output is correct
9 Correct 2471 ms 762416 KB Output is correct
10 Correct 2475 ms 762296 KB Output is correct
11 Correct 959 ms 526724 KB Output is correct
12 Correct 1828 ms 733520 KB Output is correct
13 Correct 1962 ms 762204 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 295876 KB Output is correct
2 Correct 158 ms 295872 KB Output is correct
3 Correct 163 ms 295888 KB Output is correct
4 Correct 160 ms 295876 KB Output is correct
5 Correct 159 ms 295876 KB Output is correct
6 Correct 161 ms 295884 KB Output is correct
7 Correct 160 ms 295876 KB Output is correct
8 Correct 160 ms 295880 KB Output is correct
9 Correct 161 ms 295876 KB Output is correct
10 Correct 163 ms 295860 KB Output is correct
11 Correct 161 ms 295876 KB Output is correct
12 Correct 162 ms 295876 KB Output is correct
13 Correct 157 ms 295852 KB Output is correct
14 Correct 161 ms 295876 KB Output is correct
15 Correct 161 ms 295792 KB Output is correct
16 Correct 157 ms 295876 KB Output is correct
17 Correct 162 ms 296528 KB Output is correct
18 Correct 163 ms 296424 KB Output is correct
19 Correct 164 ms 296388 KB Output is correct
20 Correct 165 ms 296364 KB Output is correct
21 Correct 162 ms 296308 KB Output is correct
22 Correct 163 ms 296404 KB Output is correct
23 Correct 163 ms 296360 KB Output is correct
24 Correct 161 ms 296132 KB Output is correct
25 Correct 174 ms 299244 KB Output is correct
26 Correct 174 ms 299204 KB Output is correct
27 Correct 179 ms 299428 KB Output is correct
28 Correct 174 ms 298904 KB Output is correct
29 Correct 180 ms 299016 KB Output is correct
30 Correct 180 ms 299204 KB Output is correct
31 Correct 178 ms 299152 KB Output is correct
32 Correct 178 ms 299168 KB Output is correct
33 Correct 386 ms 334792 KB Output is correct
34 Correct 396 ms 336948 KB Output is correct
35 Correct 360 ms 333984 KB Output is correct
36 Correct 391 ms 336264 KB Output is correct
37 Correct 382 ms 336264 KB Output is correct
38 Correct 370 ms 336244 KB Output is correct
39 Correct 376 ms 336444 KB Output is correct
40 Correct 358 ms 333960 KB Output is correct
41 Correct 324 ms 332784 KB Output is correct
42 Correct 344 ms 332740 KB Output is correct
43 Correct 420 ms 333740 KB Output is correct
44 Correct 433 ms 333892 KB Output is correct
45 Correct 294 ms 315152 KB Output is correct
46 Correct 295 ms 315320 KB Output is correct
47 Correct 418 ms 333832 KB Output is correct
48 Correct 416 ms 333748 KB Output is correct
49 Correct 160 ms 296580 KB Output is correct
50 Correct 162 ms 296476 KB Output is correct
51 Correct 160 ms 296524 KB Output is correct
52 Correct 158 ms 295876 KB Output is correct
53 Correct 162 ms 296572 KB Output is correct
54 Correct 166 ms 296672 KB Output is correct
55 Correct 165 ms 296644 KB Output is correct
56 Correct 163 ms 296644 KB Output is correct
57 Correct 164 ms 296608 KB Output is correct
58 Correct 160 ms 296132 KB Output is correct
59 Correct 160 ms 296344 KB Output is correct
60 Correct 158 ms 295928 KB Output is correct
61 Correct 1167 ms 509984 KB Output is correct
62 Correct 2469 ms 764552 KB Output is correct
63 Correct 2471 ms 762416 KB Output is correct
64 Correct 2475 ms 762296 KB Output is correct
65 Correct 959 ms 526724 KB Output is correct
66 Correct 1828 ms 733520 KB Output is correct
67 Correct 1962 ms 762204 KB Output is correct
68 Correct 163 ms 295788 KB Output is correct
69 Correct 161 ms 295808 KB Output is correct
70 Correct 160 ms 295916 KB Output is correct
71 Correct 158 ms 295900 KB Output is correct
72 Correct 162 ms 295876 KB Output is correct
73 Correct 3403 ms 779392 KB Output is correct
74 Correct 3703 ms 809196 KB Output is correct
75 Correct 2867 ms 774960 KB Output is correct
76 Correct 3740 ms 803324 KB Output is correct
77 Correct 3603 ms 807512 KB Output is correct
78 Correct 2438 ms 594424 KB Output is correct
79 Correct 2594 ms 601000 KB Output is correct
80 Correct 3983 ms 775744 KB Output is correct
81 Correct 2400 ms 586436 KB Output is correct
82 Correct 3263 ms 684188 KB Output is correct
83 Correct 4126 ms 781560 KB Output is correct
84 Correct 2234 ms 589684 KB Output is correct
85 Correct 3802 ms 780732 KB Output is correct
86 Correct 3713 ms 767560 KB Output is correct
87 Correct 2256 ms 604800 KB Output is correct
88 Correct 3663 ms 811564 KB Output is correct
89 Correct 3640 ms 811704 KB Output is correct
90 Correct 3646 ms 810272 KB Output is correct