Submission #1287024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287024		mariaclara	Rectangles (IOI19_rect)	C++17	100 / 100	2367 ms	576272 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first 
#define sc second

int bit[2505];

void update(int x, int val) {
    for(x++; x <= 2500; x += x&-x)
        bit[x] += val;
}

int query(int x) {
    x++;
    int cnt = 0;
    while(x > 0) {
        cnt += bit[x];
        x -= x&-x;
    }
    return cnt;
}

ll count_rectangles(vector<vector<int>> a) {
	int n = sz(a), m = sz(a[0]);
	// primeiro eu calculo os pares uteis
	vector<pii> line[n][m], col[n][m];

	// calculando os pares na linha
	vector<int> r(max(n,m));
	for(int i = 0; i < n; i++) {

		for(int j = 0; j < m; j++) {
			r[j] = j-1;
			// acho o primeiro cara maior ou igual (com indice menor)
			while(r[j] >= 0 and a[i][r[j]] < a[i][j]) r[j] = r[r[j]];
			if(r[j] >= 0 and r[j]+1 < j) line[i][j].pb({r[j], i});
		}

		for(int j = m-1; j >= 0; j--) {
			r[j] = j+1;
			// acho o primeiro cara maior ou igual (com indice maior)
			while(r[j] < m and a[i][r[j]] < a[i][j]) r[j] = r[r[j]];
			if(r[j] < m and j+1 < r[j] and a[i][j] != a[i][r[j]]) line[i][r[j]].pb({j, i});
		}
	}

	// calculando os pares na coluna
	for(int j = 0; j < m; j++) {

		for(int i = 0; i < n; i++) {
			r[i] = i-1;
			// acho o primeiro cara maior ou igual (com indice menor)
			while(r[i] >= 0 and a[r[i]][j] < a[i][j]) r[i] = r[r[i]];
			if(r[i] >= 0 and r[i]+1 < i) col[i][j].pb({r[i], j});
		}

		for(int i = n-1; i >= 0; i--) {
			r[i] = i+1;
			// acho o primeiro cara maior ou igual (com indice maior)
			while(r[i] < n and a[r[i]][j] < a[i][j]) r[i] = r[r[i]];
			if(r[i] < n and i+1 < r[i] and a[i][j] != a[r[i]][j]) col[r[i]][j].pb({i, j});
		}
	}

	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			sort(all(line[i][j]));
			sort(all(col[i][j]));

			for(int k = 0, ptr = 0; i != 0 and k < sz(line[i][j]); k++) {
				while(ptr < sz(line[i-1][j]) and line[i-1][j][ptr].fr < line[i][j][k].fr) ptr++;
				if(ptr >= sz(line[i-1][j])) break;
				if(line[i-1][j][ptr].fr == line[i][j][k].fr) line[i][j][k].sc = line[i-1][j][ptr].sc;
			}

			for(int k = 0, ptr = 0; j != 0 and k < sz(col[i][j]); k++) {
				while(ptr < sz(col[i][j-1]) and col[i][j-1][ptr].fr < col[i][j][k].fr) ptr++;
				if(ptr >= sz(col[i][j-1])) break;
				if(col[i][j-1][ptr].fr == col[i][j][k].fr) col[i][j][k].sc = col[i][j-1][ptr].sc;
			}
		}
	}

	// Toda parte anterior é em O(n*m*log)
	// Parte que calcula a resposta em O(n*m*min(n,m))

	int ans = 0;

	for(int i = 1; i < n; i++) {
		for(int j = 1; j < m; j++) {
			// aqui nos calculamos os retangulos com canto inferior direito (i,j), ou seja:
			// (i,j-1), (i,j-2), ..., (i,j-x) fazem parte da borda do retangulo
			// (i-1,j), (i-2,j), ..., (i-y,j) fazem parte da borda retangulo
            vector<pii> A = col[i][j-1], B = line[i-1][j];
            if(!sz(A) or !sz(B)) continue;

            for(auto &[x,y] : A) x++;
            sort(all(A));

            for(auto &[x,y] : B) x++, swap(x,y);
            sort(all(B));

            for(int i = 0, j = 0; i < sz(A); i++) {
                while(j < sz(B) and B[j].fr <= A[i].fr) 
                    update(B[j].sc, 1), j++;

                ans += query(2499) - query(A[i].sc - 1);

                if(i != sz(A)-1) continue;

                while(j > 0) j--, update(B[j].sc, -1);
            }
		}
	}

	return ans;
}

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 28 / 28