oj.uz

Submission #1064697

# Submission time Handle Problem Language Result Execution time Memory
1064697 2024-08-18T16:58:51 Z jamjanek Rectangles (IOI19_rect) C++14
10 / 100
 193 ms 86236 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>stosy[2510];
int nast[2510][2510][4];
int nast2[2510][2510][4];

const int base = 1<<12;
int tree1[2510][2*base];
int tree2[2510][2*base];
int tree3[2*base][2510];
int tree4[2*base][2510];

int MAXI1(int w, int l, int p, int a, int b, int war){
	if(p<a || b<l)return -1;
	if(a<=l && p<=b)return tree3[w][war];
	return max(MAXI1(w*2, l, (l+p)/2, a, b, war), MAXI1(w*2+1, (l+p)/2+1, p, a, b, war));
}
int MINI1(int w, int l, int p, int a, int b, int war){
	if(p<a || b<l)return 2600;
	if(a<=l && p<=b)return tree4[w][war];
	return min(MINI1(w*2, l, (l+p)/2, a, b, war), MINI1(w*2+1, (l+p)/2+1, p, a, b, war));
}
int MAXI2(int w, int l, int p, int a, int b, int war){
	if(p<a || b<l)return -1;
	if(a<=l && p<=b)return tree1[war][w];
	return max(MAXI2(w*2, l, (l+p)/2, a, b, war), MAXI2(w*2+1, (l+p)/2+1, p, a, b, war));
}
int MINI2(int w, int l, int p, int a, int b, int war){
	if(p<a || b<l)return 2600;
	if(a<=l && p<=b)return tree2[war][w];
	return min(MINI2(w*2, l, (l+p)/2, a, b, war), MINI2(w*2+1, (l+p)/2+1, p, a, b, war));
}

int maxi1(int war, int l, int r){
	l+=base, r+=base;
	int res = -1;
	while(l<r){
		if(l&1){
			res = max(res, tree3[l][war]);
			l++;
		}
		if(r&1){
			r--;
			res = max(res, tree3[r][war]);
		}
		l>>=1;
		r>>=1;
	}
	return res;
	return MAXI1(1, 0, base-1, l, r, war);
	for(int i=l;i<=r;i++)
		res = max(res, nast2[i][war][0]);
	return res;
}
int mini1(int war, int l, int r){
	return MINI1(1, 0, base-1, l, r, war);
	int res = 2600;
	for(int i=l;i<=r;i++)
		res = min(res, nast2[i][war][1]);
	return res;
}
int maxi2(int war, int l, int r){
	return MAXI2(1, 0, base-1, l, r, war);
	int res = -1;
	for(int i=l;i<=r;i++)
		res = max(res, nast2[war][i][2]);
	return res;
}
int mini2(int war, int l, int r){
	return MINI2(1, 0, base-1, l, r, war);
	int res = 2600;
	for(int i=l;i<=r;i++)
		res = min(res, nast2[war][i][3]);
	return res;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	int n = a.size();
	int m = a[0].size();
	int i, j;

	//poprzednie po x [0]	
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			while(stosy[i].size() && stosy[i].back().first<=a[i][j])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast[i][j][0] = stosy[i].back().second;
			else
				nast[i][j][0] = -1;
			stosy[i].push_back({a[i][j], j});
		}
	}
	for(i=0;i<n;i++)
		stosy[i].clear();

	//nastepne po x [1]

	for(i=0;i<n;i++){
		for(j=m-1;j>=0;j--){
			while(stosy[i].size() && stosy[i].back().first<=a[i][j])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast[i][j][1] = stosy[i].back().second;
			else
				nast[i][j][1] = m;
			stosy[i].push_back({a[i][j], j});
		}
	}
	for(i=0;i<n;i++)
		stosy[i].clear();
	
	//poprzednie po y [2]
	for(i=0;i<m;i++){
		for(j=0;j<n;j++){
			while(stosy[i].size() && stosy[i].back().first<=a[j][i])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast[j][i][2] = stosy[i].back().second;
			else
				nast[j][i][2] = -1;
			stosy[i].push_back({a[j][i], j});
		}
	}
	for(i=0;i<m;i++)
		stosy[i].clear();

	//nastepne po y [3]
	for(i=0;i<m;i++){
		for(j = n-1;j>=0;j--){
			while(stosy[i].size() && stosy[i].back().first<=a[j][i])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast[j][i][3] = stosy[i].back().second;
			else
				nast[j][i][3] = n;
			stosy[i].push_back({a[j][i], j});
		}
	}
	for(i=0;i<m;i++)
		stosy[i].clear();
		
		
		
		
		
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			while(stosy[i].size() && stosy[i].back().first<a[i][j])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast2[i][j][0] = stosy[i].back().second;
			else
				nast2[i][j][0] = -1;
			stosy[i].push_back({a[i][j], j});
		}
	}
	for(i=0;i<n;i++)
		stosy[i].clear();

	//nastepne po x [1]

	for(i=0;i<n;i++){
		for(j=m-1;j>=0;j--){
			while(stosy[i].size() && stosy[i].back().first<a[i][j])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast2[i][j][1] = stosy[i].back().second;
			else
				nast2[i][j][1] = m;
			stosy[i].push_back({a[i][j], j});
		}
	}
	for(i=0;i<n;i++)
		stosy[i].clear();
	
	//poprzednie po y [2]
	for(i=0;i<m;i++){
		for(j=0;j<n;j++){
			while(stosy[i].size() && stosy[i].back().first<a[j][i])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast2[j][i][2] = stosy[i].back().second;
			else
				nast2[j][i][2] = -1;
			stosy[i].push_back({a[j][i], j});
		}
	}
	for(i=0;i<m;i++)
		stosy[i].clear();

	//nastepne po y [3]
	for(i=0;i<m;i++){
		for(j = n-1;j>=0;j--){
			while(stosy[i].size() && stosy[i].back().first<a[j][i])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast2[j][i][3] = stosy[i].back().second;
			else
				nast2[j][i][3] = n;
			stosy[i].push_back({a[j][i], j});
		}
	}
	for(i=0;i<m;i++)
		stosy[i].clear();



	vector<pair<pair<int,int>, pair<int,int>>>sett;
	for(i=1;i<n-1;i++)
		for(j=1;j<m-1;j++){
			//printf("%d %d %d %d\n", nast[i][j][0], nast[i][j][1], nast[i][j][2], nast[i][j][3]);
			if(nast[i][j][0]!=-1 && nast[i][j][1]!=m && nast[i][j][2]!=-1 && nast[i][j][3]!=n){
				//printf("dodaje\n");
				sett.push_back({{nast[i][j][0], nast[i][j][1]}, {nast[i][j][2], nast[i][j][3]}});
			}
		}
	
	for(i=0;i<n;i++)
		for(j=0;j<m;j++){
			tree3[base+i][j] = nast2[i][j][0];
			tree4[base+i][j] = nast2[i][j][1];
			tree1[i][base+j] = nast2[i][j][2];
			tree2[i][base+j] = nast2[i][j][3];
		}
	for(i=0;i<n;i++)
		for(j=base-1;j>0;j--){
			tree1[i][j] = max(tree1[i][j*2], tree1[i][j*2+1]);
			tree2[i][j] = min(tree2[i][j*2], tree2[i][j*2+1]);
		}
	for(i=0;i<m;i++)
		for(j=base-1;j>0;j--){
			tree3[j][i] = max(tree3[j*2][i], tree3[j*2+1][i]);
			tree4[j][i] = min(tree4[j*2][i], tree4[j*2+1][i]);
		}
	sort(sett.begin(), sett.end());
	long long wynik = 0;
	for(i=0;i<(int)sett.size();i++){
		if(i!=0 && sett[i-1]==sett[i])continue;
		auto x = sett[i];
		if(mini1(x.first.first, x.second.first+1, x.second.second-1)<x.first.second)continue;
		if(maxi1(x.first.second, x.second.first+1, x.second.second-1)>x.first.first)continue;

		if(mini2(x.second.first, x.first.first+1, x.first.second-1)<x.second.second)continue;
		if(maxi2(x.second.second, x.first.first+1, x.first.second-1)>x.second.first)continue;
		wynik++;
	}
	
	return wynik;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 39512 KB Output is correct
2 Correct 15 ms 42328 KB Output is correct
3 Correct 15 ms 42076 KB Output is correct
4 Correct 17 ms 42132 KB Output is correct
5 Correct 17 ms 42076 KB Output is correct
6 Incorrect 15 ms 42008 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 39512 KB Output is correct
2 Correct 15 ms 42328 KB Output is correct
3 Correct 15 ms 42076 KB Output is correct
4 Correct 17 ms 42132 KB Output is correct
5 Correct 17 ms 42076 KB Output is correct
6 Incorrect 15 ms 42008 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 39512 KB Output is correct
2 Correct 15 ms 42328 KB Output is correct
3 Correct 15 ms 42076 KB Output is correct
4 Correct 17 ms 42132 KB Output is correct
5 Correct 17 ms 42076 KB Output is correct
6 Incorrect 15 ms 42008 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 39512 KB Output is correct
2 Correct 15 ms 42328 KB Output is correct
3 Correct 15 ms 42076 KB Output is correct
4 Correct 17 ms 42132 KB Output is correct
5 Correct 17 ms 42076 KB Output is correct
6 Incorrect 15 ms 42008 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 86236 KB Output is correct
2 Correct 148 ms 86236 KB Output is correct
3 Correct 169 ms 86036 KB Output is correct
4 Correct 12 ms 39004 KB Output is correct
5 Correct 179 ms 86028 KB Output is correct
6 Correct 174 ms 86056 KB Output is correct
7 Correct 193 ms 85948 KB Output is correct
8 Correct 185 ms 86100 KB Output is correct
9 Correct 167 ms 86096 KB Output is correct
10 Correct 166 ms 85840 KB Output is correct
11 Correct 173 ms 85984 KB Output is correct

Subtask #6
0 / 13.0

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

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 39512 KB Output is correct
2 Correct 15 ms 42328 KB Output is correct
3 Correct 15 ms 42076 KB Output is correct
4 Correct 17 ms 42132 KB Output is correct
5 Correct 17 ms 42076 KB Output is correct
6 Incorrect 15 ms 42008 KB Output isn't correct
7 Halted 0 ms 0 KB -