Submission #1047505

#TimeUsernameProblemLanguageResultExecution timeMemory
1047505fuad27Rectangles (IOI19_rect)C++17
72 / 100
5068 ms941116 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") #pragma GCC optimize("avx2") const int N = 2510; int n,m; vector<pair<int,int>> gdr[N]; vector<pair<int,int>> gdc[N]; struct Side { int r1, r2, c1, c2; }; vector<pair<short,short>> hsides[N][N]; vector<pair<short,short>> vsides[N][N]; int fen[N]; void upd(int at, int add) { at++; while(at) { fen[at]+=add; at-=at&(-at); } } int qry(int at) { at++; int sum=0; while(at<N) { sum+=fen[at]; at+=at&(-at); } return sum; } vector<int> stk; long long count_rectangles(std::vector<std::vector<int> > a) { n = a.size(); m = a[0].size(); for(int i = 0;i<n;i++) { stk.clear(); for(int j = 0;j<m;j++) { while(stk.size() and a[i][stk.back()] < a[i][j]){ stk.pop_back(); } if(stk.size()) { gdr[i].push_back({stk.back(), j}); } stk.push_back(j); } stk.clear(); for(int j = m-1;j>=0;j--) { while(stk.size() and a[i][stk.back()] < a[i][j])stk.pop_back(); if(stk.size()) { if(a[i][j] != a[i][stk.back()]) gdr[i].push_back({j, stk.back()}); } stk.push_back(j); } sort(gdr[i].begin(), gdr[i].end()); } for(int i = 0;i<m;i++) { stk.clear(); for(int j = 0;j<n;j++) { while(stk.size() and a[stk.back()][i] < a[j][i]){ stk.pop_back(); } if(stk.size()) { gdc[i].push_back({stk.back(), j}); } stk.push_back(j); } stk.clear(); for(int j = n-1;j>=0;j--) { while(stk.size() and a[stk.back()][i] < a[j][i])stk.pop_back(); if(stk.size()) { gdc[i].push_back({j, stk.back()}); } stk.push_back(j); } sort(gdc[i].begin(), gdc[i].end()); gdc[i].erase(unique(gdc[i].begin(), gdc[i].end()), gdc[i].end()); } Side seg; for(int i = 0;i<n;i++) { for(auto pr:gdr[i]) { if(pr.first +1 == pr.second)continue; if(i!=n-1 and (*lower_bound(gdr[i+1].begin(), gdr[i+1].end(), pr)) == pr)continue; seg.r1 = pr.first; seg.r2 = pr.second; seg.c2 = i; for(int j = i;j>=0;j--){ auto it = (lower_bound(gdr[j].begin(), gdr[j].end(), pr)); if(it == gdr[j].end())break; if((*it)!=pr)break; seg.c1=j; } seg.c1--; seg.c2++; seg.c1=max(seg.c1, 0); seg.c2=min(seg.c2, n-1); for(int j = seg.c1;j<=seg.c2;j++) { hsides[j][seg.r2].push_back(pair<int,int>(seg.c1, seg.r1)); } } } for(int i = 0;i<m;i++) { for(auto pr:gdc[i]) { if(pr.first +1 == pr.second)continue; if(i!=m-1 and (*lower_bound(gdc[i+1].begin(), gdc[i+1].end(), pr)) == pr)continue; seg.r1 = pr.first; seg.r2 = pr.second; seg.c2 = i; for(int j = i;j>=0;j--){ auto it = (lower_bound(gdc[j].begin(), gdc[j].end(), pr)); if(it == gdc[j].end())break; if((*it)!=pr)break; seg.c1=j; } seg.c1--; seg.c2++; seg.c1=max(seg.c1, 0); seg.c2=min(seg.c2, m-1); for(int j = seg.c1;j<=seg.c2;j++) { vsides[seg.r2][j].push_back(pair<int,int>(seg.r1, seg.c1)); } } } long long ans=0; for(int i = 0;i<n;i++) { for(int j = 0;j<m;j++) { int tmp=0; sort(vsides[i][j].begin(), vsides[i][j].end()); sort(hsides[i][j].begin(), hsides[i][j].end()); int p1 = 0; for(auto k:vsides[i][j]) { while(p1 < (int)hsides[i][j].size() and hsides[i][j][p1].first <= k.first) { upd(hsides[i][j][p1++].second, 1); } ans+=qry(k.second); } while(p1 < (int)hsides[i][j].size()) { upd(hsides[i][j][p1++].second, 1); } for(auto k:hsides[i][j]) { upd(k.second, -1); } } } return ans; }

Compilation message (stderr)

rect.cpp:5:28: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
    5 | #pragma GCC optimize("avx2")
      |                            ^
rect.cpp:19:25: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   19 | void upd(int at, int add) {
      |                         ^
rect.cpp:26:15: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   26 | int qry(int at) {
      |               ^
rect.cpp:37:60: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   37 | long long count_rectangles(std::vector<std::vector<int> > a) {
      |                                                            ^
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:135:8: warning: unused variable 'tmp' [-Wunused-variable]
  135 |    int tmp=0;
      |        ^~~
rect.cpp:99:10: warning: 'seg.Side::c1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   99 |    seg.c1--;
      |    ~~~~~~^~
#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...