Submission #211331

#	Time	Username	Problem	Language	Result	Execution time	Memory
211331		super_j6	Rectangles (IOI19_rect)	C++14	100 / 100	1157 ms	260576 KiB

rect

#include "rect.h"
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
#define endl '\n'
#define pi pair<int, int>
#define f first
#define s second

const int maxn = 2501;
int n, m;
int bit[maxn];
int a[2][maxn][maxn], lst[2][maxn][maxn], cnt[2][maxn][maxn];
vector<pi> p[2]; 
vector<int> s[2][maxn];

void add(int x, int v){
	for(x++; x < maxn; x += x & -x) bit[x] += v;
}

int qry(int x){
	int ret = 0;
	for(x++; x; x -= x & -x) ret += bit[x];
	return ret;
}

long long count_rectangles(vector<vector<int>> A){
	n = A.size(), m = A[0].size();
	
	for(int i = 0; i < n; i++) s[0][i].push_back(0);
	for(int i = 0; i < m; i++) s[1][i].push_back(0);
	
	long long ret = 0;
	for(int i = 0; i < n - 1; i++)
	for(int j = 0; j < m - 1; j++){
		a[0][i][j] = a[1][j][i] = A[i][j];
		a[0][i][j + 1] = A[i][j + 1];
		a[1][j][i + 1] = A[i + 1][j];
		for(int t = 0; t < 2; t++){
			bool eq = 0;
			p[t].clear();
			while(!s[t][i].empty()){
				int c = s[t][i].back();
				if(c < j && !eq){
					if(lst[t][c][j + 1] != i - 1) cnt[t][c][j + 1] = 0;
					cnt[t][c][j + 1]++, lst[t][c][j + 1] = i;
					p[t].push_back({j - c, cnt[t][c][j + 1]});
					if(t) swap(p[t].back().f, p[t].back().s);
				}
				eq = a[t][i][c] == a[t][i][j + 1];
				if(a[t][i][c] <= a[t][i][j + 1]) s[t][i].pop_back();
				else break;
			}
			s[t][i].push_back(j + 1);
			swap(i, j);
			sort(p[t].begin(), p[t].end(), greater<pi>());
		}
		int it = 0;
		for(pi v : p[0]){
			for(; it < p[1].size() && v.f <= p[1][it].f; it++) add(p[1][it].s, 1);
			ret += qry(v.s);
		}
		for(int jt = 0; jt < it; jt++) add(p[1][jt].s, -1);
	}
	
	return ret;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:63:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(; it < p[1].size() && v.f <= p[1][it].f; it++) add(p[1][it].s, 1);
          ~~~^~~~~~~~~~~~~

• 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