이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "rect.h"
#include <bits/stdc++.h>
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
#ifdef CHEISSMART
void dbg() { cerr << "]" << endl; }
template<class H, class ...T> void dbg(H h, T... t) {
cerr << to_string(h);
if(sizeof...(t)) cerr << ", ";
dbg(t...);
}
#define debug(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ <<"]: [", dbg(__VA_ARGS__);
#else
#define debug(...)
#endif
const int INF = 1e9 + 7, N = 3000;
int bit[N];
void add(int pos, int val) {
for(; pos < N; pos += pos & -pos)
bit[pos] += val;
}
int qry(int pos) {
int res = 0;
for(; pos; pos -= pos & -pos)
res += bit[pos];
return res;
}
ll count_rectangles(V<vi> a) {
int n = SZ(a), m = SZ(a[0]);
V<V<map<int, int>>> ver(n, V<map<int, int>>(m));
V<V<map<int, int>>> hor(n, V<map<int, int>>(m));
auto add_hor = [&] (int i, int j, int jj) {
if(jj == j + 1) return;
hor[i][j][jj] = i;
};
auto add_ver = [&] (int i, int j, int ii) {
if(ii == i + 1) return;
ver[i][j][ii] = j;
};
for(int i = 0; i < n; i++) {
vi stk;
for(int j = m - 1; j >= 0; j--) {
while(SZ(stk) && a[i][stk.back()] < a[i][j]) {
add_hor(i, j, stk.back());
stk.pop_back();
}
if(SZ(stk))
add_hor(i, j, stk.back());
if(SZ(stk) && a[i][stk.back()] == a[i][j])
stk.pop_back();
stk.PB(j);
}
}
for(int j = 0; j < m; j++) {
vi stk;
for(int i = n - 1; i >= 0; i--) {
while(SZ(stk) && a[stk.back()][j] < a[i][j]) {
add_ver(i, j, stk.back());
stk.pop_back();
}
if(SZ(stk))
add_ver(i, j, stk.back());
if(SZ(stk) && a[stk.back()][j] == a[i][j])
stk.pop_back();
stk.PB(i);
}
}
for(int i = n - 2; i >= 0; i--) {
for(int j = 0; j < m; j++) {
V<pi> todo;
for(auto[jj, ii]:hor[i][j])
if(hor[i + 1][j].count(jj))
todo.EB(jj, hor[i + 1][j][jj]);
for(auto[jj, ii]:todo)
hor[i][j][jj] = ii;
}
}
for(int j = m - 2; j >= 0; j--) {
for(int i = 0; i < n; i++) {
V<pi> todo;
for(auto[ii, jj]:ver[i][j])
if(ver[i][j + 1].count(ii))
todo.EB(ii, ver[i][j + 1][ii]);
for(auto[ii, jj]:todo)
ver[i][j][ii] = jj;
}
}
int ans = 0;
for(int i = 1; i < n - 1; i++) {
for(int j = 1; j < m - 1; j++) {
V<pi> aux;
for(auto[d, right]:ver[i - 1][j])
aux.EB(right, d);
V<pi> tt;
for(auto[r, down]:hor[i][j - 1])
tt.EB(r, down);
sort(ALL(aux));
reverse(ALL(tt));
vi undo;
for(auto[r, down]:tt) {
while(SZ(aux) && aux.back().F >= r - 1) {
int d = aux.back().S;
add(d, 1);
undo.PB(d);
aux.pop_back();
}
ans += qry(down + 1);
}
for(int d:undo)
add(d, -1);
}
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:90:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
90 | for(auto[jj, ii]:hor[i][j])
| ^
rect.cpp:93:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
93 | for(auto[jj, ii]:todo)
| ^
rect.cpp:100:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
100 | for(auto[ii, jj]:ver[i][j])
| ^
rect.cpp:103:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
103 | for(auto[ii, jj]:todo)
| ^
rect.cpp:111:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
111 | for(auto[d, right]:ver[i - 1][j])
| ^
rect.cpp:114:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
114 | for(auto[r, down]:hor[i][j - 1])
| ^
rect.cpp:119:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
119 | for(auto[r, down]:tt) {
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |