oj.uz

Submission #928495

# Submission time Handle Problem Language Result Execution time Memory
928495 2024-02-16T13:26:48 Z knon0501 Rectangles (IOI19_rect) C++14
23 / 100
 613 ms 232184 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(f(i,j,k,x)==0){
				
							flag=false;
						}
					}
					if(!S.empty() && S.top()+1<x && flag){
						bool flag = true;
						for(int l = S.top()+1 ; l<x ; l++)
							if(f(i,j,l,x)<=0)flag = false;
						ans+=flag;
					}
					S.push(x);
				}
			}
		}
	}
	return ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 147676 KB Output is correct
2 Correct 34 ms 147804 KB Output is correct
3 Correct 36 ms 147624 KB Output is correct
4 Correct 40 ms 147636 KB Output is correct
5 Correct 33 ms 147540 KB Output is correct
6 Correct 34 ms 147804 KB Output is correct
7 Incorrect 33 ms 147804 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 147676 KB Output is correct
2 Correct 34 ms 147804 KB Output is correct
3 Correct 36 ms 147624 KB Output is correct
4 Correct 40 ms 147636 KB Output is correct
5 Correct 33 ms 147540 KB Output is correct
6 Correct 34 ms 147804 KB Output is correct
7 Incorrect 33 ms 147804 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 147676 KB Output is correct
2 Correct 34 ms 147804 KB Output is correct
3 Correct 36 ms 147624 KB Output is correct
4 Correct 40 ms 147636 KB Output is correct
5 Correct 33 ms 147540 KB Output is correct
6 Correct 34 ms 147804 KB Output is correct
7 Incorrect 33 ms 147804 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 147676 KB Output is correct
2 Correct 34 ms 147804 KB Output is correct
3 Correct 36 ms 147624 KB Output is correct
4 Correct 40 ms 147636 KB Output is correct
5 Correct 33 ms 147540 KB Output is correct
6 Correct 34 ms 147804 KB Output is correct
7 Incorrect 33 ms 147804 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 147796 KB Output is correct
2 Correct 56 ms 147732 KB Output is correct
3 Correct 45 ms 147728 KB Output is correct
4 Correct 38 ms 147728 KB Output is correct
5 Correct 45 ms 147800 KB Output is correct
6 Correct 43 ms 147724 KB Output is correct
7 Correct 52 ms 147924 KB Output is correct
8 Correct 42 ms 147928 KB Output is correct
9 Correct 43 ms 147800 KB Output is correct
10 Correct 42 ms 147780 KB Output is correct
11 Correct 40 ms 147804 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 147544 KB Output is correct
2 Correct 273 ms 186452 KB Output is correct
3 Correct 571 ms 231788 KB Output is correct
4 Correct 539 ms 232036 KB Output is correct
5 Correct 613 ms 232184 KB Output is correct
6 Correct 89 ms 183888 KB Output is correct
7 Correct 130 ms 216900 KB Output is correct
8 Correct 156 ms 221272 KB Output is correct
9 Correct 43 ms 147548 KB Output is correct
10 Correct 38 ms 147716 KB Output is correct
11 Correct 33 ms 147536 KB Output is correct
12 Correct 38 ms 147548 KB Output is correct
13 Correct 36 ms 147728 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 147676 KB Output is correct
2 Correct 34 ms 147804 KB Output is correct
3 Correct 36 ms 147624 KB Output is correct
4 Correct 40 ms 147636 KB Output is correct
5 Correct 33 ms 147540 KB Output is correct
6 Correct 34 ms 147804 KB Output is correct
7 Incorrect 33 ms 147804 KB Output isn't correct
8 Halted 0 ms 0 KB -