제출 #621260

#제출 시각아이디문제언어결과실행 시간메모리
621260cheissmartRectangles (IOI19_rect)C++14
72 / 100
5053 ms976884 KiB
#include "rect.h" #include <bits/stdc++.h> #define IO_OP ios::sync_with_stdio(0), cin.tie(0) #define F first #define S second #define V vector #define PB push_back #define EB emplace_back #define MP make_pair #define SZ(v) int((v).size()) #define ALL(v) (v).begin(), (v).end() using namespace std; typedef long long ll; typedef pair<int, int> pi; typedef V<int> vi; #ifdef CHEISSMART void dbg() { cerr << "]" << endl; } template<class H, class ...T> void dbg(H h, T... t) { cerr << to_string(h); if(sizeof...(t)) cerr << ", "; dbg(t...); } #define debug(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ <<"]: [", dbg(__VA_ARGS__); #else #define debug(...) #endif const int INF = 1e9 + 7; ll count_rectangles(V<vi> a) { int n = SZ(a), m = SZ(a[0]); V<V<map<int, int>>> ver(n, V<map<int, int>>(m)); V<V<map<int, int>>> hor(n, V<map<int, int>>(m)); auto add_hor = [&] (int i, int j, int jj) { if(jj == j + 1) return; hor[i][j][jj] = i; }; auto add_ver = [&] (int i, int j, int ii) { if(ii == i + 1) return; ver[i][j][ii] = j; }; for(int i = 0; i < n; i++) { vi stk; for(int j = m - 1; j >= 0; j--) { while(SZ(stk) && a[i][stk.back()] < a[i][j]) { add_hor(i, j, stk.back()); stk.pop_back(); } if(SZ(stk)) add_hor(i, j, stk.back()); if(SZ(stk) && a[i][stk.back()] == a[i][j]) stk.pop_back(); stk.PB(j); } } for(int j = 0; j < m; j++) { vi stk; for(int i = n - 1; i >= 0; i--) { while(SZ(stk) && a[stk.back()][j] < a[i][j]) { add_ver(i, j, stk.back()); stk.pop_back(); } if(SZ(stk)) add_ver(i, j, stk.back()); if(SZ(stk) && a[stk.back()][j] == a[i][j]) stk.pop_back(); stk.PB(i); } } for(int i = n - 2; i >= 0; i--) { for(int j = 0; j < m; j++) { V<pi> todo; for(auto[jj, ii]:hor[i][j]) if(hor[i + 1][j].count(jj)) todo.EB(jj, hor[i + 1][j][jj]); for(auto[jj, ii]:todo) hor[i][j][jj] = ii; } } for(int j = m - 2; j >= 0; j--) { for(int i = 0; i < n; i++) { V<pi> todo; for(auto[ii, jj]:ver[i][j]) if(ver[i][j + 1].count(ii)) todo.EB(ii, ver[i][j + 1][ii]); for(auto[ii, jj]:todo) ver[i][j][ii] = jj; } } int ans = 0; for(int i = 1; i < n - 1; i++) { for(int j = 1; j < m - 1; j++) { for(auto[r, down]:hor[i][j - 1]) { for(auto[d, right]:ver[i - 1][j]) { if(right >= r - 1 && down >= d - 1) { debug(i, j, r, down, d, right); ans++; } } } } } return ans; }

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

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:77:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |    for(auto[jj, ii]:hor[i][j])
      |            ^
rect.cpp:80:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |    for(auto[jj, ii]:todo)
      |            ^
rect.cpp:87:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   87 |    for(auto[ii, jj]:ver[i][j])
      |            ^
rect.cpp:90:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   90 |    for(auto[ii, jj]:todo)
      |            ^
rect.cpp:97:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   97 |    for(auto[r, down]:hor[i][j - 1]) {
      |            ^
rect.cpp:98:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |     for(auto[d, right]:ver[i - 1][j]) {
      |             ^
#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...