oj.uz

Submission #928481

# Submission time Handle Problem Language Result Execution time Memory
928481 2024-02-16T13:15:48 Z knon0501 Rectangles (IOI19_rect) C++14
0 / 100
 53 ms 148060 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++){
			bool flag = true;
			while(!S.empty() && a[i][S.top()] <=  a[i][j]){
				int x = S.top(); 
				
				
				if(x +1 <j && flag)
					b[x+1][j-1].push_back(i);
				if(a[i][S.top()]==a[i][j])flag=false;
				S.pop();
				
			}
			if(!S.empty() && flag){
				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<m ; i++){
		for(int j=i ; j<m ; 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(k +1 <x && flag){
							ans++;
						}
			
					}
					if(!S.empty() && S.top()+1<x )
						ans++;
					S.push(x);
				}
			}
		}
	}
	return ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 147804 KB Output is correct
2 Correct 33 ms 147804 KB Output is correct
3 Correct 34 ms 148048 KB Output is correct
4 Correct 35 ms 147796 KB Output is correct
5 Correct 33 ms 147640 KB Output is correct
6 Incorrect 36 ms 147752 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 147804 KB Output is correct
2 Correct 33 ms 147804 KB Output is correct
3 Correct 34 ms 148048 KB Output is correct
4 Correct 35 ms 147796 KB Output is correct
5 Correct 33 ms 147640 KB Output is correct
6 Incorrect 36 ms 147752 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 147804 KB Output is correct
2 Correct 33 ms 147804 KB Output is correct
3 Correct 34 ms 148048 KB Output is correct
4 Correct 35 ms 147796 KB Output is correct
5 Correct 33 ms 147640 KB Output is correct
6 Incorrect 36 ms 147752 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 147804 KB Output is correct
2 Correct 33 ms 147804 KB Output is correct
3 Correct 34 ms 148048 KB Output is correct
4 Correct 35 ms 147796 KB Output is correct
5 Correct 33 ms 147640 KB Output is correct
6 Incorrect 36 ms 147752 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 147996 KB Output is correct
2 Correct 46 ms 148060 KB Output is correct
3 Correct 41 ms 147720 KB Output is correct
4 Correct 33 ms 147712 KB Output is correct
5 Incorrect 48 ms 147768 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 147804 KB Output is correct
2 Correct 33 ms 147804 KB Output is correct
3 Correct 34 ms 148048 KB Output is correct
4 Correct 35 ms 147796 KB Output is correct
5 Correct 33 ms 147640 KB Output is correct
6 Incorrect 36 ms 147752 KB Output isn't correct
7 Halted 0 ms 0 KB -