제출 #1069800

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1069800		Gromp15	Rectangles (IOI19_rect)	C++17	100 / 100	2355 ms	832084 KiB

rect

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include "rect.h"
#define ll long long
#define ar array
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
 
using namespace std;

template<typename T> struct fenwick {
    int n; vector<T> bit;
    fenwick(int a) : n(a), bit(a+1) {}
    T sum(int pos) {
        T s = 0;
        for (; pos; s += bit[pos], pos -= pos&-pos);
        return s;
    }
    T query(int l, int r) {
        return sum(r+1) - sum(l);
    }
    void update(int pos, T x) {
        pos++;
        for (; pos <= n; bit[pos] += x, pos += pos&-pos);
    }
};
 
const int nax = 2505;
short u[nax][nax], d[nax][nax], l[nax][nax], r[nax][nax], st[nax], idx[nax], idx2[nax];
vector<ar<short, 2>> who[nax][nax], who2[nax][nax];
fenwick<int> fw(nax);
 
long long count_rectangles(std::vector<std::vector<int>> a) {
	int n = sz(a), m = sz(a[0]);
	for (int i = 0, tp = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			while (tp && a[i][j] >= a[i][st[tp]]) tp--;
			l[i][j] = tp ? st[tp] : m + 1;
			st[++tp] = j;
		}
		tp = 0;
		for (int j = m-1; j >= 0; j--) {
			while (tp && a[i][j] >= a[i][st[tp]]) tp--;
			r[i][j] = tp ? st[tp] : -2;
			st[++tp] = j;
		}
	}
	for (int i = 0, tp = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			while (tp && a[j][i] >= a[st[tp]][i]) tp--;
			u[j][i] = tp ? st[tp] : n + 1;
			st[++tp] = j;
		}
		tp = 0;
		for (int j = n-1; j >= 0; j--) {
			while (tp && a[j][i] >= a[st[tp]][i]) tp--;
			d[j][i] = tp ? st[tp] : -2;
			st[++tp] = j;
		}
	}
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { 
		int L = l[i][j] + 1, R = r[i][j] - 1;
		if (L <= R) who[i][L].push_back({R, 0});
		int U = u[i][j] + 1, D = d[i][j] - 1;
		if (U <= D) who2[U][j].push_back({D, 0});
	}
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
		sort(all(who[i][j]));
		sort(all(who2[i][j]));
		who[i][j].erase(unique(all(who[i][j])), who[i][j].end());
		who2[i][j].erase(unique(all(who2[i][j])), who2[i][j].end());
	}
	for (int i = n-1; i >= 0; i--) {
		for (int j = m-1; j >= 0; j--) {
			for (int k = 0; k < sz(who[i][j]); k++) {
				int r = who[i][j][k][0];
				if (i+1 < n) {
					auto it = lower_bound(all(who[i+1][j]), ar<short, 2>{r, 0});
					if (it != who[i+1][j].end() && (*it)[0] == r) who[i][j][k][1] = (*it)[1];
					else who[i][j][k][1] = i;
				}
				else who[i][j][k][1] = i;
			}
			for (int k = 0; k < sz(who2[i][j]); k++) {
				int d = who2[i][j][k][0];
				if (j+1 < m) {
					auto it = lower_bound(all(who2[i][j+1]), ar<short, 2>{d, 0});
					if (it != who2[i][j+1].end() && (*it)[0] == d) who2[i][j][k][1] = (*it)[1];
					else who2[i][j][k][1] = j;
				}
				else who2[i][j][k][1] = j;
			}
		}
	}
	ll ans = 0;
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
		iota(idx, idx + sz(who[i][j]), 0);
		sort(idx, idx + sz(who[i][j]), [&](int x, int y) { return who[i][j][x][0] < who[i][j][y][0]; });
		iota(idx2, idx2 + sz(who2[i][j]), 0);
		sort(idx2, idx2 + sz(who2[i][j]), [&](int x, int y) { return who2[i][j][x][1] < who2[i][j][y][1]; });
		int t = 0;
		for (int k = 0; k < sz(who2[i][j]); k++) {
			while (t < sz(who[i][j]) && who[i][j][idx[t]][0] <= who2[i][j][idx2[k]][1]) {
				fw.update(who[i][j][idx[t++]][1], 1);
			}
			ans += fw.query(who2[i][j][idx2[k]][0], nax-1);
		}
		for (int k = 0; k < t; k++) fw.update(who[i][j][idx[k]][1], -1);
	}
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:67:36: warning: narrowing conversion of 'R' from 'int' to 'short int' [-Wnarrowing]
   67 |   if (L <= R) who[i][L].push_back({R, 0});
      |                                    ^
rect.cpp:69:37: warning: narrowing conversion of 'D' from 'int' to 'short int' [-Wnarrowing]
   69 |   if (U <= D) who2[U][j].push_back({D, 0});
      |                                     ^
rect.cpp:82:59: warning: narrowing conversion of 'r' from 'int' to 'short int' [-Wnarrowing]
   82 |      auto it = lower_bound(all(who[i+1][j]), ar<short, 2>{r, 0});
      |                                                           ^
rect.cpp:91:60: warning: narrowing conversion of 'd' from 'int' to 'short int' [-Wnarrowing]
   91 |      auto it = lower_bound(all(who2[i][j+1]), ar<short, 2>{d, 0});
      |                                                            ^

• 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