oj.uz

Submission #1047420

# Submission time Handle Problem Language Result Execution time Memory
1047420 2024-08-07T12:46:38 Z vjudge1 Rectangles (IOI19_rect) C++17
0 / 100
 47 ms 297552 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2510;
int n,m;
vector<pair<int,int>> gdr[N];
vector<pair<int,int>> gdc[N];

struct Side {
	int r1, r2, c1, c2;
};
vector<Side> hsides[N][N];
vector<Side> vsides[N][N];
vector<pair<int,int>> swp[N];
long long count_rectangles(std::vector<std::vector<int> > a) {
	n = a.size();
	m = a[0].size();
	for(int i = 0;i<n;i++) {
		vector<int> stk;
		for(int j = 0;j<m;j++) {
			while(stk.size() and a[i][stk.back()] < a[i][j]){
				stk.pop_back();
			}
			if(stk.size()) {
				gdr[i].push_back({stk.back(), j});
			}
			stk.push_back(j);
		}
		stk.clear();
		for(int j = m-1;j>=0;j--) {
			while(stk.size() and a[i][stk.back()] < a[i][j])stk.pop_back();
			if(stk.size()) {
				if(a[i][j] != a[i][stk.back()])
					gdr[i].push_back({j, stk.back()});
			}
			stk.push_back(j);
		}
		sort(gdr[i].begin(), gdr[i].end());
	}
	for(int i = 0;i<m;i++) {
		vector<int> stk;
		for(int j = 0;j<n;j++) {
			while(stk.size() and a[stk.back()][i] < a[j][i]){
				stk.pop_back();
			}
			if(stk.size()) {
				gdc[i].push_back({stk.back(), j});
			}
			stk.push_back(j);
		}
		stk.clear();
		for(int j = n-1;j>=0;j--) {
			while(stk.size() and a[stk.back()][i] <= a[j][i])stk.pop_back();
			if(stk.size()) {
				gdc[i].push_back({j, stk.back()});
			}
			stk.push_back(j);
		}
		sort(gdc[i].begin(), gdc[i].end());
	}
	for(int i = 0;i<n;i++) {
		for(auto pr:gdr[i]) {
			if(i!=n-1 and (*lower_bound(gdr[i+1].begin(), gdr[i+1].end(), pr)) == pr)continue;
			Side seg;
			seg.r1 = pr.first;
			seg.r2 = pr.second;
			seg.c2 = i;
			for(int j = i;j>=0;j--){
				auto it = (lower_bound(gdr[j].begin(), gdr[j].end(), pr));
				if(it == gdr[j].end())break;
				if((*it)!=pr)break;
				seg.c1=j;
			}
			seg.c1--;
			seg.c2++;
			seg.c1=max(seg.c1, 0);
			seg.c2=min(seg.c2, n-1);
			for(int j = seg.c1;j<=seg.c2;j++) {
				hsides[j][seg.r2].push_back(seg);
			}
		}
	}





	for(int i = 0;i<m;i++) {
		for(auto pr:gdc[i]) {
			if(i!=m-1 and (*lower_bound(gdc[i+1].begin(), gdc[i+1].end(), pr)) == pr)continue;
			Side seg;
			seg.r1 = pr.first;
			seg.r2 = pr.second;
			seg.c2 = i;
			for(int j = i;j>=0;j--){
				auto it = (lower_bound(gdc[j].begin(), gdc[j].end(), pr));
				if(it == gdc[j].end())break;
				if((*it)!=pr)break;
				seg.c1=j;
			}
			seg.c1--;
			seg.c2++;
			seg.c1=max(seg.c1, 0);
			seg.c2=min(seg.c2, m-1);
			for(int j = seg.c1;j<=seg.c2;j++) {
				vsides[seg.r2][j].push_back(seg);
			}
		}
	}


	int ans=0;
	for(int i = 0;i<n;i++) {
		for(int j = 0;j<m;j++) {
//			cout << i << " " << j << ": " << endl;
			for(auto k:vsides[i][j]) {
				if(k.r1+1 == k.r2)break;
				for(auto k2:hsides[i][j]) {
					if(k2.r1+1 == k2.r2)break;
//					cout << i << ' ' << j << endl;
					if(k2.r1 >= k.c1 and k2.c1 <= k.r1) {
///						cout << i << " " << k2.r1 << " "  << k.r1 << " " << j << endl;
						ans++;
					}

				}
//				cout << endl;
			}
		}
	}
	return ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 296276 KB Output is correct
2 Correct 42 ms 296552 KB Output is correct
3 Correct 43 ms 296540 KB Output is correct
4 Correct 40 ms 296540 KB Output is correct
5 Correct 40 ms 296536 KB Output is correct
6 Correct 41 ms 296528 KB Output is correct
7 Correct 41 ms 296532 KB Output is correct
8 Correct 42 ms 296536 KB Output is correct
9 Incorrect 41 ms 296532 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 296276 KB Output is correct
2 Correct 42 ms 296552 KB Output is correct
3 Correct 43 ms 296540 KB Output is correct
4 Correct 40 ms 296540 KB Output is correct
5 Correct 40 ms 296536 KB Output is correct
6 Correct 41 ms 296528 KB Output is correct
7 Correct 41 ms 296532 KB Output is correct
8 Correct 42 ms 296536 KB Output is correct
9 Incorrect 41 ms 296532 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 296276 KB Output is correct
2 Correct 42 ms 296552 KB Output is correct
3 Correct 43 ms 296540 KB Output is correct
4 Correct 40 ms 296540 KB Output is correct
5 Correct 40 ms 296536 KB Output is correct
6 Correct 41 ms 296528 KB Output is correct
7 Correct 41 ms 296532 KB Output is correct
8 Correct 42 ms 296536 KB Output is correct
9 Incorrect 41 ms 296532 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 296276 KB Output is correct
2 Correct 42 ms 296552 KB Output is correct
3 Correct 43 ms 296540 KB Output is correct
4 Correct 40 ms 296540 KB Output is correct
5 Correct 40 ms 296536 KB Output is correct
6 Correct 41 ms 296528 KB Output is correct
7 Correct 41 ms 296532 KB Output is correct
8 Correct 42 ms 296536 KB Output is correct
9 Incorrect 41 ms 296532 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 297296 KB Output is correct
2 Correct 43 ms 297072 KB Output is correct
3 Correct 41 ms 297044 KB Output is correct
4 Correct 40 ms 296280 KB Output is correct
5 Correct 46 ms 297456 KB Output is correct
6 Correct 44 ms 297552 KB Output is correct
7 Correct 47 ms 297552 KB Output is correct
8 Correct 44 ms 297300 KB Output is correct
9 Incorrect 47 ms 297524 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 296276 KB Output is correct
2 Correct 42 ms 296552 KB Output is correct
3 Correct 43 ms 296540 KB Output is correct
4 Correct 40 ms 296540 KB Output is correct
5 Correct 40 ms 296536 KB Output is correct
6 Correct 41 ms 296528 KB Output is correct
7 Correct 41 ms 296532 KB Output is correct
8 Correct 42 ms 296536 KB Output is correct
9 Incorrect 41 ms 296532 KB Output isn't correct
10 Halted 0 ms 0 KB -