oj.uz

Submission #928466

# Submission time Handle Problem Language Result Execution time Memory
928466 2024-02-16T12:52:09 Z knon0501 Rectangles (IOI19_rect) C++14
0 / 100
 47 ms 147804 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> b[2505][2505];

vector<vector<int>> aa;

int f(int i,int j,int x,int y){
	int cnt1 = 0;
	int cnt2 = 0;
	
	for(int k=i ; k<=j ; k++){
		if(aa[x][k]<aa[y][k])
			cnt1++;
		if(aa[x][k]>aa[y][k])
			cnt2++;
	}
	if(cnt1==j-i+1)return 1;
	if(cnt2==j-i+1)return -1;
	return 0;
}

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

	for(int i=1 ; i<n-1 ; i++){
		stack<int> S;

		for(int j=0 ; j<m ; j++){
			while(!S.empty() && a[i][S.top()] <=  a[i][j]){
				int x = S.top(); S.pop();
				if(x +1 <j )
					b[x+1][j-1].push_back(i);
			}
			if(!S.empty()){
				int x = S.top();
				if(x+1<j)
					b[x+1][j-1].push_back(i);
			}
			S.push(j);
		}
	}
	long long ans = 0;
	for(int i=1 ; i<= n ; i++){
		for(int j=i ; j<=n ; j++){
			vector<vector<int>> c;
			int prv=-1;
			for(int x: b[i][j]){
				//cout<<i<<" "<<j<<" "<<x<<endl;
				if(prv+1<x)
					c.push_back({x});
				else
					c.back().push_back(x);
				prv=x;
			}

			for(auto d: c){
				stack<int> S;
				d.push_back(d.back()+1);
				d.push_back(d[0]-1);
				
				sort(d.begin(),d.end());
				for(auto x: d){
					bool flag = true;
					while(!S.empty() && f(i,j,S.top(),x)>=0){
						int k = S.top(); S.pop();
						if(f(i,j,k,x)==0)
							flag=false;
						if(k +1 <x && flag){
							ans++;
						}
						
					}
					if(!S.empty() && S.top()+1<x && flag)
						ans++;
					S.push(x);
				}
			}
		}
	}
	return ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 147732 KB Output is correct
2 Correct 34 ms 147704 KB Output is correct
3 Correct 34 ms 147800 KB Output is correct
4 Correct 33 ms 147792 KB Output is correct
5 Correct 33 ms 147804 KB Output is correct
6 Incorrect 32 ms 147804 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 147732 KB Output is correct
2 Correct 34 ms 147704 KB Output is correct
3 Correct 34 ms 147800 KB Output is correct
4 Correct 33 ms 147792 KB Output is correct
5 Correct 33 ms 147804 KB Output is correct
6 Incorrect 32 ms 147804 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 147732 KB Output is correct
2 Correct 34 ms 147704 KB Output is correct
3 Correct 34 ms 147800 KB Output is correct
4 Correct 33 ms 147792 KB Output is correct
5 Correct 33 ms 147804 KB Output is correct
6 Incorrect 32 ms 147804 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 147732 KB Output is correct
2 Correct 34 ms 147704 KB Output is correct
3 Correct 34 ms 147800 KB Output is correct
4 Correct 33 ms 147792 KB Output is correct
5 Correct 33 ms 147804 KB Output is correct
6 Incorrect 32 ms 147804 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 147732 KB Output is correct
2 Correct 34 ms 147704 KB Output is correct
3 Correct 34 ms 147800 KB Output is correct
4 Correct 33 ms 147792 KB Output is correct
5 Correct 33 ms 147804 KB Output is correct
6 Incorrect 32 ms 147804 KB Output isn't correct
7 Halted 0 ms 0 KB -