제출 #621263

#제출 시각아이디문제언어결과실행 시간메모리
621263cheissmartRectangles (IOI19_rect)C++14
72 / 100
1866 ms1048576 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, N = 3000; int bit[N]; void add(int pos, int val) { for(; pos < N; pos += pos & -pos) bit[pos] += val; } int qry(int pos) { int res = 0; for(; pos; pos -= pos & -pos) res += bit[pos]; return res; } 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; } } ll ans = 0; for(int i = 1; i < n - 1; i++) { for(int j = 1; j < m - 1; j++) { V<pi> aux; for(auto[d, right]:ver[i - 1][j]) aux.EB(right, d); V<pi> tt; for(auto[r, down]:hor[i][j - 1]) tt.EB(r, down); sort(ALL(aux)); reverse(ALL(tt)); vi undo; for(auto[r, down]:tt) { while(SZ(aux) && aux.back().F >= r - 1) { int d = aux.back().S; add(d, 1); undo.PB(d); aux.pop_back(); } ans += qry(down + 1); } for(int d:undo) add(d, -1); } } return ans; }

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

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