제출 #956971

#제출 시각아이디문제언어결과실행 시간메모리
956971MackerRectangles (IOI19_rect)C++17
컴파일 에러
0 ms0 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; #define ff first #define ss second #define all(v) v.begin(), v.end() #define FOR(i, n) for (int i = 0; i < n; i++) struct node{ int on = 0, mxx, mnx, mxy, mny; }; vector<vector<node>> st; int lenx = 1, leny = 1; node zero({1, 0, INT_MAX/2, 0, INT_MAX/2}); vector<int> get_last_big(vector<int> v){ int n = v.size(); vector<int> res(n, -1); stack<pii> s; s.push({INT_MAX/2, -1}); FOR(i, n){ int a = v[i]; while(a >= s.top().ff) s.pop(); res[i] = s.top().ss; s.push({a, i}); } return res; } node comb(node a, node b){ node res; res.on = min(a.on, b.on); res.mnx = min(a.mnx, b.mnx); res.mny = min(a.mny, b.mny); res.mxx = max(a.mxx, b.mxx); res.mxy = max(a.mxy, b.mxy); return res; } void updy(int y, node val, int i, int j = 1, int s = 0, int e = leny){ if(y < s || y >= e) return; if(y == s && s + 1 == e) { if(i >= lenx) st[i][j] = val; else st[i][j] = comb(st[i * 2][j], st[i * 2 + 1][j]); return; } updy(y, val, i, j * 2, s, (s + e) / 2); updy(y, val, i, j * 2 + 1, (s + e) / 2, e); st[i][j] = comb(st[i][j * 2], st[i][j * 2 + 1]); } void updx(int x, int y, node val, int i = 1, int s = 0, int e = lenx){ if(x < s || x >= e) return; if(x == s && s + 1 == e) {updy(y, val, i); return;} updx(x, y, val, i * 2, s, (s + e) / 2); updx(x, y, val, i * 2 + 1, (s + e) / 2, e); updy(y, val, i); } node qryy(int l, int r, int i, int j = 1, int s = 0, int e = leny){ if(l >= e || r <= s) return zero; if(l <= s && e <= r) return st[i][j]; return comb(qryy(l, r, i, j * 2, s, (s + e) / 2), qryy(l, r, i, j * 2 + 1, (s + e) / 2, e)); } node qryx(int xl, int xr, int yl, int yr, int i = 1, int s = 0, int e = lenx){ if(xl >= e || xr <= s) return zero; if(xl <= s && e <= xr) return qryy(yl, yr, i); return comb(qryx(xl, xr, yl, yr, i * 2, s, (s + e) / 2), qryx(xl, xr, yl, yr, i * 2 + 1, (s + e) / 2, e)); } long long count_rectangles_2(vector<vector<signed>> v) { int n = v.size(); int m = v[0].size(); st.assign(n, vector<node>(m)); FOR(i, n){ vector<int> cur; vector<int> res; FOR(j, m){ cur.push_back(v[i][j]); } res = get_last_big(cur); FOR(j, m){ st[i][j].mnx = res[j]; } reverse(all(cur)); res = get_last_big(cur); reverse(all(res)); FOR(j, m){ st[i][j].mxx = m - res[j] - 1; } } FOR(j, m){ vector<int> cur; vector<int> res; FOR(i, n){ cur.push_back(v[i][j]); } res = get_last_big(cur); FOR(i, n){ st[i][j].mny = res[i]; } reverse(all(cur)); res = get_last_big(cur); reverse(all(res)); FOR(i, n){ st[i][j].mxy = n - res[i] - 1; } } vector<vector<pii>> ord(7000005); FOR(i, n) FOR(j, m){ ord[v[i][j]].push_back({i, j}); } ll res = 0; for (auto o : ord) { for (auto [x, y] : o) { st[x][y].on = true; int mxx, mnx, mxy, mny; mxx = st[x][y].mxx; mnx = st[x][y].mnx; mxy = st[x][y].mxy; mny = st[x][y].mny; if(mxx >= m || mxy >= n || mnx < 0 || mny < 0) continue; bool f = 0; for (int i = mny + 1; i < mxy; i++){ for (int j = mnx + 1; j < mxx; j++) { if(!st[i][j].on) {f = 1; break;} if(st[i][j].mnx < mnx) {f = 1; break;} if(st[i][j].mny < mny) {f = 1; break;} if(st[i][j].mxx > mxx) {f = 1; break;} if(st[i][j].mxy > mxy) {f = 1; break;} } if(f) break; } if(!f) res++; } } return res; } long long count_rectangles(vector<vector<signed>> v) {

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

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:156:54: error: expected '}' at end of input
  156 | long long count_rectangles(vector<vector<signed>> v) {
      |                                                      ^
rect.cpp:156:54: warning: no return statement in function returning non-void [-Wreturn-type]