제출 #899474

#제출 시각아이디문제언어결과실행 시간메모리
899474rxlfd314Rectangles (IOI19_rect)C++17
37 / 100
5084 ms45140 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 count_rectangles(vt<vt<int>> A) { const int N = size(A), M = size(A[0]); 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) { BIT fen(M); priority_queue<ari2, vt<ari2>, greater<ari2>> ma; int dead_bef = 0, j = 0; bool dead[M] = {}; FOR(i, 0, M-1) { while (size(ma)) { auto [a, b] = ma.top(); if (a >= i-1 && !dead[b]) break; ma.pop(); if (!dead[b]) { dead[b] = true; fen.upd(b, -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...