제출 #899738

#제출 시각아이디문제언어결과실행 시간메모리
899738rxlfd314Rectangles (IOI19_rect)C++17
50 / 100
5095 ms208596 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") #include "rect.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using ari2 = array<int, 2>; #define vt vector #define size(x) (int((x).size())) #define all(x) begin(x), end(x) #define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d)) #define FOR(a, b, c) REP(a, b, c, 1) #define ROF(a, b, c) REP(a, b, c, -1) struct BIT { vt<int> fen; BIT(int n) { fen.resize(n); } void upd(int i, int v) { for (; i < size(fen); i += i+1 & -i-1) fen[i] += v; } int qry(int i) { int ret = 0; for (; i >= 0; i -= i+1 & -i-1) ret += fen[i]; return ret; } int qry(int l, int r) { return r < l ? 0 : qry(r) - qry(l-1); } }; ll ST1(vt<vt<int>> A) { const int N = size(A), M = size(A[0]); int psum[N][M], U[N][M], L[N][M], L2[N][M], U2[N][M]; memset(L, 0x3f, sizeof(L)); memset(U, 0x3f, sizeof(U)); memset(L2, 0x3f, sizeof(L2)); memset(U2, 0x3f, sizeof(U2)); ll ans = 0; FOR(i, 1, N-2) FOR(j, 1, M-2) { psum[i][j] = A[i][j] + (i ? psum[i-1][j] : 0) + (j ? psum[i][j-1] : 0) - (i && j ? psum[i-1][j-1] : 0); U[i][j] = A[i][j] < A[i][j+1] ? min(i, U[i-1][j]) : INT_MAX; L[i][j] = A[i][j] < A[i+1][j] ? min(j, L[i][j-1]) : INT_MAX; U2[i][j] = A[i][j] < A[i][j-1] ? min(i, U2[i-1][j]) : INT_MAX; L2[i][j] = A[i][j] < A[i-1][j] ? min(j, L2[i][j-1]) : INT_MAX; ans += L[i][j] <= j && U[i][j] <= i && L2[U[i][j]][j] == L[i][j] && U2[i][L[i][j]] == U[i][j] && L[i][j] && U[i][j] && psum[i][j] - psum[U[i][j]-1][j] - psum[i][L[i][j]-1] + psum[U[i][j]-1][L[i][j]-1] == 0; } return ans; } ll count_rectangles(vt<vt<int>> A) { const int N = size(A), M = size(A[0]); bool sub1 = true; FOR(i, 0, N-1) FOR(j, 0, M-1) sub1 &= A[i][j] < 2; if (sub1) return ST1(A); int X[N][M], Y[N][M]; FOR(i, 0, N-1) { vt<int> sk; FOR(j, 0, M-1) { while (size(sk) && A[i][sk.back()] < A[i][j]) sk.pop_back(); X[i][j] = size(sk) ? sk.back() + 1 : 0; sk.push_back(j); } sk.clear(); ROF(j, M-1, 0) { while (size(sk) && A[i][sk.back()] < A[i][j]) sk.pop_back(); Y[i][j] = size(sk) ? sk.back() - 1 : M - 1; sk.push_back(j); } } #ifdef DEBUG cout << "X:\n"; FOR(i, 0, N-1) FOR(j, 0, M-1) cout << X[i][j] << "\n "[j+1<M]; cout << "Y:\n"; FOR(i, 0, N-1) FOR(j, 0, M-1) cout << Y[i][j] << "\n "[j+1<M]; #endif ll ans = 0; int R[M], L[M], mx[M]; FOR(l, 1, N-2) { memset(R, 0x3f, sizeof(R)); memset(L, 0xc0, sizeof(L)); memset(mx, 0xc0, sizeof(mx)); FOR(r, l, N-2) { FOR(i, 0, M-1) { R[i] = min(R[i], Y[r][i]); } int ord[M]; iota(ord, ord+M, 0); sort(ord, ord+M, [&](const int &a, const int &b) { return R[a] < R[b]; }); BIT fen(M); priority_queue<ari2, vt<ari2>, greater<ari2>> ma; int dead_bef = 0, j = 0, k = 0; bool dead[M] = {}; FOR(i, 0, M-1) { for (; k < M && R[ord[k]] < i-1; k++) if (!dead[ord[k]]) { dead[ord[k]] = true; fen.upd(ord[k], -1); } for (; j < dead_bef; j++) if (!dead[j]) { fen.upd(j, -1); dead[j] = true; } R[i] = min(R[i], Y[r][i]); L[i] = max(L[i], X[r][i]); mx[i] = max(mx[i], A[r][i]); if (i && mx[i-1] < min(A[l-1][i-1], A[r+1][i-1])) { ans += fen.qry(L[i]-1, i-2); #ifdef DEBUG cout << "contribution from " << i-1 << ' ' << l << ' ' << r << ": " << fen.qry(L[i]-1, i-2) << '\n'; #endif } else { dead_bef = i - 1; } ma.push({R[i], i}); fen.upd(i, 1); } } } return ans; }

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

rect.cpp: In member function 'void BIT::upd(int, int)':
rect.cpp:23:33: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   23 |     for (; i < size(fen); i += i+1 & -i-1)
      |                                ~^~
rect.cpp: In member function 'int BIT::qry(int)':
rect.cpp:28:26: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   28 |     for (; i >= 0; i -= i+1 & -i-1)
      |                         ~^~
#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...