oj.uz

Submission #143403

# Submission time Handle Problem Language Result Execution time Memory
143403 2019-08-13T23:28:09 Z model_code Rectangles (IOI19_rect) C++17
59 / 100
 1366 ms 1048580 KB 
// incorrect/rect-peyman-n3-opt.cpp

//In the name of God
//Peyman Jabbarzade Ganje
//Boarder shouldn't be equal with inside
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int, int> pii;

const int maxn = 3000 + 10, maxx=1e7;
int n,m;
long long ans;
vector<int>vec, nozoli, will_remove;
map<int, int> fp[maxn][maxn];
vector<pii> sp[2][maxn][maxn];

void add_pair(int type, int lvl, int l, int r)
{
	int tmp = 1;
	if(fp[lvl][l].find(r) != fp[lvl][l].end())
		tmp += fp[lvl][l][r];

	if(type == 0) {
		if(r-l-1>0)
			sp[type][lvl+1][r].push_back(pii(r-l-1, tmp));
	}
	else {
		if(r-l-1>0)
			sp[type][r][lvl+1].push_back(pii(tmp, r-l-1));
	}

	fp[lvl+1][l][r] = tmp;
}

void extract_pairs(int type, int lvl)
{
	nozoli.clear();
	for(int i=0;i<vec.size();i++)
	{
		int last=-1;
		while(nozoli.size() && vec[nozoli.back()] < vec[i])
		{
			if(vec[nozoli.back()] > last)
				add_pair(type, lvl, nozoli.back(), i);
			last = vec[nozoli.back()];
			nozoli.pop_back();
		}
		if(nozoli.size()) add_pair(type, lvl, nozoli.back(), i);
		nozoli.push_back(i);
	}
}

long long count_rectangles(vector<vector<int> >a)
{
	n = a.size();
	m = a[0].size();

	for(int i=0;i<n;i++)
	{
		vec.clear();
		for(int j=0;j<m;j++)
			vec.push_back(a[i][j]);
		extract_pairs(0,i);
	}
	for(int i=0;i<=n;i++)
		for(int j=0;j<=m;j++)
		fp[i][j].clear();

	for(int j=0;j<m;j++)
	{
		vec.clear();
		for(int i=0;i<n;i++)
			vec.push_back(a[i][j]);
		extract_pairs(1,j);
	}

	int tt = 0;

	for(int i=0;i<=max(n,m);i++) {
		for(int j=0;j<=max(n,m);j++) {
//			cerr << "(" << sp[0][i][j].size() << "," << sp[1][i][j].size() << ") ";
			if(sp[0][i][j].size() && sp[1][i][j].size())
			{
				// sp[0].X fix sp[1].X moteghaier
				for(int x=0;x<sp[0][i][j].size();x++)
					for(int y=0;y<sp[1][i][j].size();y++) {
						tt++;
						if(sp[0][i][j][x].X <= sp[1][i][j][y].X && sp[0][i][j][x].Y >= sp[1][i][j][y].Y)
							ans ++;
					}
			}
		}
//		cerr << endl;
	}
	return ans;
}

Compilation message

rect.cpp: In function 'void extract_pairs(int, int)':
rect.cpp:40:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vec.size();i++)
              ~^~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:87:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int x=0;x<sp[0][i][j].size();x++)
                 ~^~~~~~~~~~~~~~~~~~~
rect.cpp:88:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int y=0;y<sp[1][i][j].size();y++) {
                  ~^~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 803 ms 851672 KB Output is correct
2 Correct 757 ms 851560 KB Output is correct
3 Correct 769 ms 851548 KB Output is correct
4 Correct 748 ms 851588 KB Output is correct
5 Correct 749 ms 851412 KB Output is correct
6 Correct 749 ms 851468 KB Output is correct
7 Correct 800 ms 851460 KB Output is correct
8 Correct 756 ms 851540 KB Output is correct
9 Correct 755 ms 851508 KB Output is correct
10 Correct 799 ms 851576 KB Output is correct
11 Correct 757 ms 851576 KB Output is correct
12 Correct 745 ms 851460 KB Output is correct
13 Correct 752 ms 851436 KB Output is correct
14 Correct 749 ms 851448 KB Output is correct
15 Correct 752 ms 851448 KB Output is correct
16 Correct 753 ms 851448 KB Output is correct
17 Correct 745 ms 851448 KB Output is correct
18 Correct 747 ms 851376 KB Output is correct
19 Correct 844 ms 851708 KB Output is correct
20 Correct 750 ms 851576 KB Output is correct
21 Correct 749 ms 851448 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 803 ms 851672 KB Output is correct
2 Correct 757 ms 851560 KB Output is correct
3 Correct 769 ms 851548 KB Output is correct
4 Correct 748 ms 851588 KB Output is correct
5 Correct 749 ms 851412 KB Output is correct
6 Correct 749 ms 851468 KB Output is correct
7 Correct 800 ms 851460 KB Output is correct
8 Correct 756 ms 851540 KB Output is correct
9 Correct 755 ms 851508 KB Output is correct
10 Correct 799 ms 851576 KB Output is correct
11 Correct 757 ms 851576 KB Output is correct
12 Correct 745 ms 851460 KB Output is correct
13 Correct 752 ms 851436 KB Output is correct
14 Correct 749 ms 851448 KB Output is correct
15 Correct 752 ms 851448 KB Output is correct
16 Correct 753 ms 851448 KB Output is correct
17 Correct 756 ms 852216 KB Output is correct
18 Correct 751 ms 852216 KB Output is correct
19 Correct 748 ms 852216 KB Output is correct
20 Correct 749 ms 852044 KB Output is correct
21 Correct 749 ms 852312 KB Output is correct
22 Correct 749 ms 852352 KB Output is correct
23 Correct 757 ms 852344 KB Output is correct
24 Correct 752 ms 851700 KB Output is correct
25 Correct 745 ms 851448 KB Output is correct
26 Correct 747 ms 851376 KB Output is correct
27 Correct 844 ms 851708 KB Output is correct
28 Correct 750 ms 851576 KB Output is correct
29 Correct 749 ms 851448 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 803 ms 851672 KB Output is correct
2 Correct 757 ms 851560 KB Output is correct
3 Correct 769 ms 851548 KB Output is correct
4 Correct 748 ms 851588 KB Output is correct
5 Correct 749 ms 851412 KB Output is correct
6 Correct 749 ms 851468 KB Output is correct
7 Correct 800 ms 851460 KB Output is correct
8 Correct 756 ms 851540 KB Output is correct
9 Correct 755 ms 851508 KB Output is correct
10 Correct 799 ms 851576 KB Output is correct
11 Correct 757 ms 851576 KB Output is correct
12 Correct 745 ms 851460 KB Output is correct
13 Correct 752 ms 851436 KB Output is correct
14 Correct 749 ms 851448 KB Output is correct
15 Correct 752 ms 851448 KB Output is correct
16 Correct 753 ms 851448 KB Output is correct
17 Correct 756 ms 852216 KB Output is correct
18 Correct 751 ms 852216 KB Output is correct
19 Correct 748 ms 852216 KB Output is correct
20 Correct 749 ms 852044 KB Output is correct
21 Correct 749 ms 852312 KB Output is correct
22 Correct 749 ms 852352 KB Output is correct
23 Correct 757 ms 852344 KB Output is correct
24 Correct 752 ms 851700 KB Output is correct
25 Correct 764 ms 856236 KB Output is correct
26 Correct 767 ms 856188 KB Output is correct
27 Correct 816 ms 856216 KB Output is correct
28 Correct 771 ms 855416 KB Output is correct
29 Correct 785 ms 856952 KB Output is correct
30 Correct 786 ms 856952 KB Output is correct
31 Correct 815 ms 856668 KB Output is correct
32 Correct 777 ms 856568 KB Output is correct
33 Correct 745 ms 851448 KB Output is correct
34 Correct 747 ms 851376 KB Output is correct
35 Correct 844 ms 851708 KB Output is correct
36 Correct 750 ms 851576 KB Output is correct
37 Correct 749 ms 851448 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 803 ms 851672 KB Output is correct
2 Correct 757 ms 851560 KB Output is correct
3 Correct 769 ms 851548 KB Output is correct
4 Correct 748 ms 851588 KB Output is correct
5 Correct 749 ms 851412 KB Output is correct
6 Correct 749 ms 851468 KB Output is correct
7 Correct 800 ms 851460 KB Output is correct
8 Correct 756 ms 851540 KB Output is correct
9 Correct 755 ms 851508 KB Output is correct
10 Correct 799 ms 851576 KB Output is correct
11 Correct 757 ms 851576 KB Output is correct
12 Correct 745 ms 851460 KB Output is correct
13 Correct 752 ms 851436 KB Output is correct
14 Correct 749 ms 851448 KB Output is correct
15 Correct 752 ms 851448 KB Output is correct
16 Correct 753 ms 851448 KB Output is correct
17 Correct 756 ms 852216 KB Output is correct
18 Correct 751 ms 852216 KB Output is correct
19 Correct 748 ms 852216 KB Output is correct
20 Correct 749 ms 852044 KB Output is correct
21 Correct 749 ms 852312 KB Output is correct
22 Correct 749 ms 852352 KB Output is correct
23 Correct 757 ms 852344 KB Output is correct
24 Correct 752 ms 851700 KB Output is correct
25 Correct 764 ms 856236 KB Output is correct
26 Correct 767 ms 856188 KB Output is correct
27 Correct 816 ms 856216 KB Output is correct
28 Correct 771 ms 855416 KB Output is correct
29 Correct 785 ms 856952 KB Output is correct
30 Correct 786 ms 856952 KB Output is correct
31 Correct 815 ms 856668 KB Output is correct
32 Correct 777 ms 856568 KB Output is correct
33 Correct 1033 ms 895568 KB Output is correct
34 Correct 996 ms 900380 KB Output is correct
35 Correct 996 ms 900240 KB Output is correct
36 Correct 1045 ms 907384 KB Output is correct
37 Correct 999 ms 912504 KB Output is correct
38 Correct 997 ms 912376 KB Output is correct
39 Correct 1000 ms 912504 KB Output is correct
40 Correct 997 ms 908828 KB Output is correct
41 Correct 1040 ms 892920 KB Output is correct
42 Correct 1090 ms 898532 KB Output is correct
43 Correct 1314 ms 919536 KB Output is correct
44 Correct 1366 ms 920024 KB Output is correct
45 Correct 1038 ms 885752 KB Output is correct
46 Correct 1034 ms 885496 KB Output is correct
47 Correct 1295 ms 916600 KB Output is correct
48 Correct 1313 ms 916704 KB Output is correct
49 Correct 745 ms 851448 KB Output is correct
50 Correct 747 ms 851376 KB Output is correct
51 Correct 844 ms 851708 KB Output is correct
52 Correct 750 ms 851576 KB Output is correct
53 Correct 749 ms 851448 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 784 ms 852476 KB Output is correct
2 Correct 798 ms 852288 KB Output is correct
3 Correct 793 ms 852068 KB Output is correct
4 Correct 757 ms 851352 KB Output is correct
5 Correct 779 ms 852328 KB Output is correct
6 Correct 854 ms 852336 KB Output is correct
7 Correct 786 ms 852288 KB Output is correct
8 Correct 782 ms 852412 KB Output is correct
9 Correct 850 ms 852488 KB Output is correct
10 Correct 792 ms 851704 KB Output is correct
11 Correct 783 ms 852092 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 760 ms 851320 KB Output is correct
2 Runtime error 1066 ms 1048580 KB Execution killed with signal 9 (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 803 ms 851672 KB Output is correct
2 Correct 757 ms 851560 KB Output is correct
3 Correct 769 ms 851548 KB Output is correct
4 Correct 748 ms 851588 KB Output is correct
5 Correct 749 ms 851412 KB Output is correct
6 Correct 749 ms 851468 KB Output is correct
7 Correct 800 ms 851460 KB Output is correct
8 Correct 756 ms 851540 KB Output is correct
9 Correct 755 ms 851508 KB Output is correct
10 Correct 799 ms 851576 KB Output is correct
11 Correct 757 ms 851576 KB Output is correct
12 Correct 745 ms 851460 KB Output is correct
13 Correct 752 ms 851436 KB Output is correct
14 Correct 749 ms 851448 KB Output is correct
15 Correct 752 ms 851448 KB Output is correct
16 Correct 753 ms 851448 KB Output is correct
17 Correct 756 ms 852216 KB Output is correct
18 Correct 751 ms 852216 KB Output is correct
19 Correct 748 ms 852216 KB Output is correct
20 Correct 749 ms 852044 KB Output is correct
21 Correct 749 ms 852312 KB Output is correct
22 Correct 749 ms 852352 KB Output is correct
23 Correct 757 ms 852344 KB Output is correct
24 Correct 752 ms 851700 KB Output is correct
25 Correct 764 ms 856236 KB Output is correct
26 Correct 767 ms 856188 KB Output is correct
27 Correct 816 ms 856216 KB Output is correct
28 Correct 771 ms 855416 KB Output is correct
29 Correct 785 ms 856952 KB Output is correct
30 Correct 786 ms 856952 KB Output is correct
31 Correct 815 ms 856668 KB Output is correct
32 Correct 777 ms 856568 KB Output is correct
33 Correct 1033 ms 895568 KB Output is correct
34 Correct 996 ms 900380 KB Output is correct
35 Correct 996 ms 900240 KB Output is correct
36 Correct 1045 ms 907384 KB Output is correct
37 Correct 999 ms 912504 KB Output is correct
38 Correct 997 ms 912376 KB Output is correct
39 Correct 1000 ms 912504 KB Output is correct
40 Correct 997 ms 908828 KB Output is correct
41 Correct 1040 ms 892920 KB Output is correct
42 Correct 1090 ms 898532 KB Output is correct
43 Correct 1314 ms 919536 KB Output is correct
44 Correct 1366 ms 920024 KB Output is correct
45 Correct 1038 ms 885752 KB Output is correct
46 Correct 1034 ms 885496 KB Output is correct
47 Correct 1295 ms 916600 KB Output is correct
48 Correct 1313 ms 916704 KB Output is correct
49 Correct 784 ms 852476 KB Output is correct
50 Correct 798 ms 852288 KB Output is correct
51 Correct 793 ms 852068 KB Output is correct
52 Correct 757 ms 851352 KB Output is correct
53 Correct 779 ms 852328 KB Output is correct
54 Correct 854 ms 852336 KB Output is correct
55 Correct 786 ms 852288 KB Output is correct
56 Correct 782 ms 852412 KB Output is correct
57 Correct 850 ms 852488 KB Output is correct
58 Correct 792 ms 851704 KB Output is correct
59 Correct 783 ms 852092 KB Output is correct
60 Correct 760 ms 851320 KB Output is correct
61 Runtime error 1066 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
62 Halted 0 ms 0 KB -