oj.uz

Submission #928471

# Submission time Handle Problem Language Result Execution time Memory
928471 2024-02-16T13:02:34 Z knon0501 Rectangles (IOI19_rect) C++17
23 / 100
 580 ms 244396 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)
						ans++;
					S.push(x);
				}
			}
		}
	}
	return ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 147540 KB Output is correct
2 Correct 37 ms 147664 KB Output is correct
3 Correct 34 ms 147800 KB Output is correct
4 Correct 33 ms 147792 KB Output is correct
5 Correct 35 ms 147640 KB Output is correct
6 Correct 34 ms 147792 KB Output is correct
7 Incorrect 33 ms 147788 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 147540 KB Output is correct
2 Correct 37 ms 147664 KB Output is correct
3 Correct 34 ms 147800 KB Output is correct
4 Correct 33 ms 147792 KB Output is correct
5 Correct 35 ms 147640 KB Output is correct
6 Correct 34 ms 147792 KB Output is correct
7 Incorrect 33 ms 147788 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 147540 KB Output is correct
2 Correct 37 ms 147664 KB Output is correct
3 Correct 34 ms 147800 KB Output is correct
4 Correct 33 ms 147792 KB Output is correct
5 Correct 35 ms 147640 KB Output is correct
6 Correct 34 ms 147792 KB Output is correct
7 Incorrect 33 ms 147788 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 147540 KB Output is correct
2 Correct 37 ms 147664 KB Output is correct
3 Correct 34 ms 147800 KB Output is correct
4 Correct 33 ms 147792 KB Output is correct
5 Correct 35 ms 147640 KB Output is correct
6 Correct 34 ms 147792 KB Output is correct
7 Incorrect 33 ms 147788 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 49 ms 147800 KB Output is correct
2 Correct 50 ms 147796 KB Output is correct
3 Correct 40 ms 147856 KB Output is correct
4 Correct 33 ms 147652 KB Output is correct
5 Correct 43 ms 148012 KB Output is correct
6 Correct 42 ms 147796 KB Output is correct
7 Correct 42 ms 147792 KB Output is correct
8 Correct 43 ms 147800 KB Output is correct
9 Correct 43 ms 147764 KB Output is correct
10 Correct 43 ms 147804 KB Output is correct
11 Correct 43 ms 147796 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 147536 KB Output is correct
2 Correct 277 ms 186448 KB Output is correct
3 Correct 577 ms 243932 KB Output is correct
4 Correct 570 ms 244228 KB Output is correct
5 Correct 580 ms 244396 KB Output is correct
6 Correct 88 ms 190032 KB Output is correct
7 Correct 133 ms 228136 KB Output is correct
8 Correct 149 ms 233504 KB Output is correct
9 Correct 34 ms 147548 KB Output is correct
10 Correct 35 ms 147712 KB Output is correct
11 Correct 33 ms 147768 KB Output is correct
12 Correct 33 ms 147800 KB Output is correct
13 Correct 35 ms 147624 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 147540 KB Output is correct
2 Correct 37 ms 147664 KB Output is correct
3 Correct 34 ms 147800 KB Output is correct
4 Correct 33 ms 147792 KB Output is correct
5 Correct 35 ms 147640 KB Output is correct
6 Correct 34 ms 147792 KB Output is correct
7 Incorrect 33 ms 147788 KB Output isn't correct
8 Halted 0 ms 0 KB -