oj.uz

Submission #954703

# Submission time Handle Problem Language Result Execution time Memory
954703 2024-03-28T11:51:01 Z waldi Rectangles (IOI19_rect) C++17
0 / 100
 115 ms 147568 KB 
#include "rect.h"
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int((x).size()))
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

ll count_rectangles(vector<vector<int>> wej){
	int n = ssize(wej);
	int m = ssize(wej[0]);
	if(n<3 || m<3) return 0ll;
	
	vector poziomo(m, vector(m, vector<int>()));
	FOR(i, 1, n-2){
		vector<int> stos;
		REP(j, m){
			while(ssize(stos) && wej[i][stos.back()] <= wej[i][j]){
				int t = stos.back();
				if(t+1 <= j-1) poziomo[t+1][j-1].emplace_back(i);
				stos.pop_back();
			}
			if(ssize(stos)){
				int t = stos.back();
				if(t+1 <= j-1) poziomo[t+1][j-1].emplace_back(i);
			}
			stos.emplace_back(j);
		}
	}
	
	//~ vector pionowo(n, vector(n, vector<int>()));
	vector pionowo(n, vector(m, vector<int>()));
	FOR(i, 1, m-2){
		vector<int> stos;
		REP(j, n){
			while(ssize(stos) && wej[stos.back()][i] <= wej[j][i]){
				int t = stos.back();
				if(t+1 <= j-1) pionowo[j-1][i].emplace_back(t+1);
				stos.pop_back();
			}
			if(ssize(stos)){
				int t = stos.back();
				if(t+1 <= j-1) pionowo[j-1][i].emplace_back(t+1);
			}
			stos.emplace_back(j);
		}
	}
	
	//~ REP(j, m) FOR(i, 0, j){
		//~ printf("%d %d: ", i, j);
		//~ for(int x : poziomo[i][j]) printf("%d ", x);
		//~ printf("\n");
	//~ }
	
	//~ REP(j, n) FOR(i, 0, j){
		//~ printf("%d %d: ", i, j);
		//~ for(int x : pionowo[i][j]) printf("%d ", x);
		//~ printf("\n");
	//~ }
	
	vector<int> jest(n, 0);
	
	ll wyn = 0ll;
	REP(j, m) FOR(i, 0, j){
		int maks_gora = 0, pop = -1;
		for(int dol : poziomo[i][j]){
			if(dol != pop+1) maks_gora = dol;
			pop = dol;
			
			FOR(poz, i, j) for(int &x : pionowo[dol][poz]){
				if(x < maks_gora) break;
				if(++jest[x] == j-i+1) ++wyn;
			}
			FOR(poz, i, j) for(int &x : pionowo[dol][poz]){
				if(x < maks_gora) break;
				jest[x] = 0;
			}
		}
	}
	return wyn;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 147568 KB Output is correct
2 Correct 80 ms 106628 KB Output is correct
3 Correct 97 ms 147540 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 103 ms 147552 KB Output is correct
6 Correct 100 ms 147540 KB Output is correct
7 Correct 100 ms 147536 KB Output is correct
8 Correct 102 ms 147536 KB Output is correct
9 Incorrect 101 ms 147540 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -