Submission #143403

#	Time	Username	Problem	Language	Result	Execution time	Memory
143403		model_code	Rectangles (IOI19_rect)	C++17	59 / 100	1366 ms	1048580 KiB

rect

// 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 (stderr)

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 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28