제출 #310065

#제출 시각아이디문제언어결과실행 시간메모리
310065fivefourthreeoneRectangles (IOI19_rect)C++17
컴파일 에러
0 ms0 KiB
#pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #include <bits/stdc++.h> using namespace std; using ll = long long; const int mxN = 2501; int n, m; int BIT[mxN][mxN]; vector<vector<int>> arr; vector<int> atrow[mxN][mxN]; vector<pair<int, int>> atcol[mxN]; vector<int> len[mxN]; vector<int> ch[mxN]; void upd(int num, int pos, int del) { pos++; while(pos < n) { BIT[num][pos]+=del; pos += pos&-pos; } } int sum(int num, int pos, int del) { pos++; while(pos) { BIT[num][pos]+=del; pos -= pos&-pos; } } ll count_rectangles(vector<vector<int>> A) { arr = A; n = A.size(); m = A[0].size(); for(int i = 1; i < n-1; ++i) { vector<int> stk; for(int j = 0; j < m; ++j) { while(stk.size() && arr[i][stk.back()] < arr[i][j])stk.pop_back(); if(stk.size() && j - stk.back() > 1) { atcol[i].emplace_back(stk.back(), j); } stk.push_back(j); } stk.clear(); for(int j = m-1; j >= 0; --j) { while(stk.size() && arr[i][stk.back()] < arr[i][j])stk.pop_back(); if(stk.size() && stk.back() - j > 1) { atcol[i].emplace_back(j, stk.back()); } stk.push_back(j); } sort(atcol[i].begin(), atcol[i].end()); atcol[i].resize(unique(atcol[i].begin(), atcol[i].end()) - atcol[i].begin()); } for(int j = 1; j < m-1; ++j) { vector<int> stk; vector<pair<int, int>> ex; for(int i = 0; i < n; ++i) { while(stk.size() && arr[stk.back()][j] < arr[i][j])stk.pop_back(); if(stk.size() && i - stk.back() > 1) { ex.emplace_back(stk.back(), i); } stk.push_back(i); } stk.clear(); for(int i = n-1; i >= 0; --i) { while(stk.size() && arr[stk.back()][j] < arr[i][j])stk.pop_back(); if(stk.size() && stk.back() - i > 1) { ex.emplace_back(i, stk.back()); } stk.push_back(i); } sort(ex.begin(), ex.end()); ex.resize(unique(ex.begin(), ex.end()) - ex.begin()); for(auto p: ex) { atrow[p.first][p.second].push_back(j); } } for(int j = m-1; j > 1; --j) { len[j].resize(atcol[j].size()); for(int i = 0; i < atcol[j].size(); ++i) { int above = lower_bound(atcol[j+1].begin(), atcol[j+1].end(), atcol[j][i]) - atcol[j+1].begin(); if(above==atcol[j+1].size() || atcol[j+1][above]!=atcol[j][i]) { len[j][i] = 1; }else { len[j][i] = len[j+1][above] + 1; } } } ll res = 0; for(int i = 1; j < m-1; ++i) { for(int j = i; j < m-1; ++j) { ch[j].clear(); } for(int j = 0; j < atcol[i].size(); ++j) { upd(atcol[i][j].first, atcol[i][j].second, 1); ch[i + len[i][j] - 1].push_back(j); } for(int j = i; j < m-1; ++j) { int prv = 1; for(int k = 0; k < atrow[i+1][j-1].size(); ++k) { if(k && atrow[i+1][j-1][k-1]==atrow[i+1][j-1][k]-1)prv++; else prv = 1; res += sum(atrow[i+1][j-1][k] - prv, atrow[i+1][j-1][k] + 1); } for(int k: ch[j]) { upd(atcol[i][k].first, atcol[i][k].second, -1); } } } return res; }

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

rect.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
rect.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
rect.cpp: In function 'int sum(int, int, int)':
rect.cpp:29:1: warning: no return statement in function returning non-void [-Wreturn-type]
   29 | }
      | ^
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:80:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(int i = 0; i < atcol[j].size(); ++i) {
      |                        ~~^~~~~~~~~~~~~~~~~
rect.cpp:82:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             if(above==atcol[j+1].size() || atcol[j+1][above]!=atcol[j][i]) {
      |                ~~~~~^~~~~~~~~~~~~~~~~~~
rect.cpp:90:20: error: 'j' was not declared in this scope
   90 |     for(int i = 1; j < m-1; ++i) {
      |                    ^
rect.cpp:94:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for(int j = 0; j < atcol[i].size(); ++j) {
      |                        ~~^~~~~~~~~~~~~~~~~
rect.cpp:100:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             for(int k = 0; k < atrow[i+1][j-1].size(); ++k) {
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:103:76: error: too few arguments to function 'int sum(int, int, int)'
  103 |                 res += sum(atrow[i+1][j-1][k] - prv, atrow[i+1][j-1][k] + 1);
      |                                                                            ^
rect.cpp:23:5: note: declared here
   23 | int sum(int num, int pos, int del) {
      |     ^~~