제출 #417670

#제출 시각아이디문제언어결과실행 시간메모리
417670usachevd0Rectangles (IOI19_rect)C++17
15 / 100
5036 ms46268 KiB
#pragma gcc optimize("Ofast") #pragma gcc optimize("O3") #pragma gcc target("avx,avx2,fma,sse,sse2,sse3,popcnt") #include <bits/stdc++.h> #ifndef LOCAL #include "rect.h" #endif using namespace std; #define fi first #define se second #define mp make_pair #define pb push_back #define all(a) (a).begin(), (a).end() #define Time (clock() * 1.0 / CLOCKS_PER_SEC) using ll = long long; using ull = unsigned long long; using pii = pair<int, int>; using pil = pair<int, ll>; using pli = pair<ll, int>; using pll = pair<ll, ll>; using ld = long double; template<typename T1, typename T2> bool chkmin(T1& x, T2 y) { return y < x ? (x = y, true) : false; } template<typename T1, typename T2> bool chkmax(T1& x, T2 y) { return y > x ? (x = y, true) : false; } void debug_out() { cerr << endl; } template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); } template<typename T> void mdebug_out(T* a, int n) { for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n) #else #define debug(...) 1337 #define mdebug(a, n) 1337 #endif template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) { for (auto& x : v) stream << x << ' '; return stream; } template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) { return stream << p.first << ' ' << p.second; } const int INF32 = 1e9; const int maxN = 2e2 + 5; bool badc[maxN]; int a[maxN][maxN]; int L[maxN], R[maxN]; int stk[maxN][maxN], sz[maxN]; namespace fnw { const int N = 2e2 + 5; int f[N][N]; void add(int i0, int j0, int delta) { for (int i = i0 + 1; i < N; i += i & -i) for (int j = j0 + 1; j < N; j += j & -j) f[i][j] += delta; } int gt(int i0, int j0) { int res = 0; for (int i = i0 + 1; i >= 1; i -= i & -i) for (int j = j0 + 1; j >= 1; j -= j & -j) res += f[i][j]; return res; } } ll count_rectangles(vector<vector<int>> _a) { int n = _a.size(), m = _a[0].size(); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) a[i][j] = _a[i][j]; if (min(n, m) < 3) return 0; ll ans = 0; for (int r1 = 1; r1 < n - 1; ++r1) { for (int r2 = r1; r2 < n - 1; ++r2) { badc[0] = badc[m - 1] = 1; for (int c = 1; c < m - 1; ++c) { int mx = -INF32; for (int i = r1; i <= r2; ++i) chkmax(mx, a[i][c]); badc[c] = mx >= min(a[r1 - 1][c], a[r2 + 1][c]); } // count L for (int r = r1; r <= r2; ++r) { sz[r] = 0; } for (int c = 0; c < m; ++c) { L[c] = 0; for (int r = r1; r <= r2; ++r) { while (sz[r] && a[r][stk[r][sz[r] - 1]] < a[r][c]) { --sz[r]; } if (sz[r]) chkmax(L[c], stk[r][sz[r] - 1]); stk[r][sz[r]++] = c; } } // count R for (int r = r1; r <= r2; ++r) { sz[r] = 0; } for (int c = m - 1; c >= 0; --c) { R[c] = m; for (int r = r1; r <= r2; ++r) { while (sz[r] && a[r][stk[r][sz[r] - 1]] < a[r][c]) { --sz[r]; } if (sz[r]) chkmin(R[c], stk[r][sz[r] - 1]); stk[r][sz[r]++] = c; } } int b = m - 1; for (int c = m - 2; c >= 0; --c) { ans += fnw::gt(min(b, R[c]), c); // for (int d = c + 2; d <= min(b, R[c]); ++d) { // ans += L[d] <= c; // } if (badc[c]) { b = c; } // add c + 1 fnw::add(c + 1, L[c + 1], +1); } for (int c = 1; c < m; ++c) fnw::add(c, L[c], -1); } } return ans; } #ifdef LOCAL int main() { #ifdef LOCAL freopen("in", "r", stdin); #endif // InputReader inputReader(STDIN_FILENO); int n, m; cin >> n >> m; // n = inputReader.readInt(); // m = inputReader.readInt(); vector<vector<int>> a(n, vector<int>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> a[i][j]; // a[i][j] = inputReader.readInt(); } } // inputReader.close(); long long result = count_rectangles(a); printf("%lld\n", result); fclose(stdout); return 0; } #endif

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

rect.cpp:1: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    1 | #pragma gcc optimize("Ofast")
      | 
rect.cpp:2: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    2 | #pragma gcc optimize("O3")
      | 
rect.cpp:3: warning: ignoring '#pragma gcc target' [-Wunknown-pragmas]
    3 | #pragma gcc target("avx,avx2,fma,sse,sse2,sse3,popcnt")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...