oj.uz

답안 #928492

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
928492 2024-02-16T13:24:04 Z knon0501 Rectangles (IOI19_rect) C++14
23 / 100
 654 ms 238584 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){
							for(int l = i ; l<=j ; l++)
								a[x][l]=max(a[x][l],a[k][l]);
							flag=false;
						}
					}
					if(!S.empty() && S.top()+1<x && flag)
						ans++;
					S.push(x);
				}
			}
		}
	}
	return ans;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 147540 KB Output is correct
2 Correct 34 ms 147800 KB Output is correct
3 Correct 34 ms 147540 KB Output is correct
4 Correct 38 ms 147548 KB Output is correct
5 Correct 33 ms 147532 KB Output is correct
6 Correct 34 ms 147804 KB Output is correct
7 Incorrect 33 ms 147772 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 147540 KB Output is correct
2 Correct 34 ms 147800 KB Output is correct
3 Correct 34 ms 147540 KB Output is correct
4 Correct 38 ms 147548 KB Output is correct
5 Correct 33 ms 147532 KB Output is correct
6 Correct 34 ms 147804 KB Output is correct
7 Incorrect 33 ms 147772 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 147540 KB Output is correct
2 Correct 34 ms 147800 KB Output is correct
3 Correct 34 ms 147540 KB Output is correct
4 Correct 38 ms 147548 KB Output is correct
5 Correct 33 ms 147532 KB Output is correct
6 Correct 34 ms 147804 KB Output is correct
7 Incorrect 33 ms 147772 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 147540 KB Output is correct
2 Correct 34 ms 147800 KB Output is correct
3 Correct 34 ms 147540 KB Output is correct
4 Correct 38 ms 147548 KB Output is correct
5 Correct 33 ms 147532 KB Output is correct
6 Correct 34 ms 147804 KB Output is correct
7 Incorrect 33 ms 147772 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 147748 KB Output is correct
2 Correct 51 ms 147800 KB Output is correct
3 Correct 42 ms 147760 KB Output is correct
4 Correct 33 ms 147532 KB Output is correct
5 Correct 47 ms 147800 KB Output is correct
6 Correct 46 ms 147800 KB Output is correct
7 Correct 44 ms 147868 KB Output is correct
8 Correct 44 ms 147960 KB Output is correct
9 Correct 42 ms 147792 KB Output is correct
10 Correct 42 ms 147796 KB Output is correct
11 Correct 40 ms 147868 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 147540 KB Output is correct
2 Correct 290 ms 189696 KB Output is correct
3 Correct 654 ms 238420 KB Output is correct
4 Correct 598 ms 238424 KB Output is correct
5 Correct 642 ms 238584 KB Output is correct
6 Correct 91 ms 187240 KB Output is correct
7 Correct 130 ms 222516 KB Output is correct
8 Correct 136 ms 227760 KB Output is correct
9 Correct 35 ms 147548 KB Output is correct
10 Correct 35 ms 147612 KB Output is correct
11 Correct 33 ms 147804 KB Output is correct
12 Correct 33 ms 147804 KB Output is correct
13 Correct 33 ms 147620 KB Output is correct

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 147540 KB Output is correct
2 Correct 34 ms 147800 KB Output is correct
3 Correct 34 ms 147540 KB Output is correct
4 Correct 38 ms 147548 KB Output is correct
5 Correct 33 ms 147532 KB Output is correct
6 Correct 34 ms 147804 KB Output is correct
7 Incorrect 33 ms 147772 KB Output isn't correct
8 Halted 0 ms 0 KB -