제출 #780917

#제출 시각아이디문제언어결과실행 시간메모리
7809171binRectangles (IOI19_rect)C++14
10 / 100
241 ms81776 KiB
#include <bits/stdc++.h> #include "rect.h" using namespace std; #define all(v) v.begin(), v.end() typedef long long ll; const int NMAX = 3005; ll n, m, ans; stack<int> st[NMAX]; pair<int, int> p[NMAX][NMAX]; ll count_rectangles(vector<vector<int>> a) { n = a.size(); m = a[0].size(); for(int i = 0; i < m; i++){ st[i].emplace(0); for(int j = 0; j < m; j++) p[i][j] = {-2, -2}; } for(int i = 0; i + 1 < n; i++){ stack<pair<int, vector<int>>> s; for(int j = 0; j < m; j++){ vector<int> cur; int init = 0; auto merge = [&](vector<int> & v){ if(!init) init = 1, cur = v; else{ vector<int> tmp; int j = 0; for(int i = 0; i < cur.size(); i++){ while(j < v.size() && v[j] < cur[i]) j++; if(j < v.size() && v[j] == cur[i]) tmp.emplace_back(cur[i]); } swap(cur, tmp); } }; while(s.size() && a[i][s.top().first] <= a[i][j]){ auto[x, v] = s.top(); s.pop(); merge(v); if(s.size() && a[i][x] < a[i][j]){ if(p[x + 1][j - 1].second != i - 1) p[x + 1][j - 1].first = i; p[x + 1][j - 1].second = i; int up = p[x + 1][j - 1].first; ans += cur.end() - lower_bound(all(cur), up); } } vector<int> v; while(st[j].size() && a[st[j].top()][j] <= a[i + 1][j]){ int y = st[j].top(); st[j].pop(); if(st[j].size() && a[y][j] < a[i + 1][j]) v.emplace_back(st[j].top() + 1); } st[j].emplace(i + 1); reverse(all(v)); merge(v); s.emplace(j, cur); } } return ans; } /* int main(void){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector<vector<int>> v(n, vector<int>(m)); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> v[i][j]; cout << count_rectangles(v); return 0; } */

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

rect.cpp: In lambda function:
rect.cpp:30:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |                     for(int i = 0; i < cur.size(); i++){
      |                                    ~~^~~~~~~~~~~~
rect.cpp:31:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |                         while(j < v.size() && v[j] < cur[i]) j++;
      |                               ~~^~~~~~~~~~
rect.cpp:32:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |                         if(j < v.size() && v[j] == cur[i]) tmp.emplace_back(cur[i]);
      |                            ~~^~~~~~~~~~
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:39:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |                 auto[x, v] = s.top(); s.pop();
      |                     ^
#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...