제출 #417738

#제출 시각아이디문제언어결과실행 시간메모리
417738usachevd0Rectangles (IOI19_rect)C++17
27 / 100
5035 ms49876 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 = 7e2 + 5; bool badc[maxN]; int a[maxN][maxN]; int L[maxN], R[maxN], B[maxN]; int curPtr[maxN]; int mxc[maxN]; 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 c = 0; c < m; ++c) { mxc[c] = -INF32; L[c] = 0; R[c] = m; } for (int r2 = r1; r2 < n - 1; ++r2) { badc[0] = badc[m - 1] = 1; for (int c = 1; c < m - 1; ++c) { chkmax(mxc[c], a[r2][c]); badc[c] = mxc[c] >= min(a[r1 - 1][c], a[r2 + 1][c]); } // count L int last = 0; curPtr[0] = 0; for (int c = 1; c < m; ++c) { while (last && a[r2][last] < a[r2][c]) last = curPtr[last]; chkmax(L[c], last); curPtr[c] = last; last = c; } // count L last = m; curPtr[m] = m; for (int c = m - 1; c >= 0; --c) { while (last < m && a[r2][last] < a[r2][c]) last = curPtr[last]; chkmin(R[c], last); curPtr[c] = last; last = c; } int b = m - 1; for (int c = m - 1; c >= 0; --c) { B[c] = b; if (badc[c]) b = c; } for (int c = 0; c < m; ++c) { int l = L[c], r = R[c]; ans += r < m && r <= B[c] && r >= c + 2 && L[r] < c; ans += c <= B[l] && c <= R[l] && c >= l + 2; } } } 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(); auto oldTime = Time; long long result = count_rectangles(a); debug(Time - oldTime); 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...