제출 #402314

#제출 시각아이디문제언어결과실행 시간메모리
402314b00n0rpRectangles (IOI19_rect)C++17
59 / 100
3118 ms1048580 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define vi vector<int> #define pb push_back #define REP(i,n) for(int i = 0; i < n; i++) #define FOR(i,a,b) for(int i = a; i < b; i++) #define FORD(i,a,b) for(int i = a; i >= b; i --) #define pii pair<int,int> #define F first #define S second #define all(v) v.begin(),v.end() #define SZ(v) (int)v.size() const ll MX = 2505; ll ans = 0; int n,m; int gl[MX][MX],gr[MX][MX],gu[MX][MX],gd[MX][MX]; pii rows[MX][MX],cols[MX][MX]; vector<pair<ll,int> > row_map,col_map; vector<pair<ll,ll> > quer_row,quer_col; bitset<MX*MX*6> b1,b2; vi gg[MX][MX]; int compvar(const void *one, const void *two) { int a = *((int*)one); int b = *((int*)two); if (a<b) return -1; if (a == b) return 0; return 1; } void check_rectangle(int x1,int y1,int x2,int y2,int q){ quer_row.pb({(y1-1)*MX*MX+(y2+1)*MX+x1,q*MX+x2}); quer_col.pb({(x1-1)*MX*MX+(x2+1)*MX+y1,q*MX+y2}); } ll count_rectangles(vector<vi> a){ n = a.size(); m = a[0].size(); if(n <= 2 or m <= 2) return 0; FORD(i,n-1,0){ stack<int> st; REP(j,m){ gl[i][j] = gr[i][j] = gu[i][j] = gd[i][j] = -1; } REP(j,m){ while(st.size() and a[i][st.top()] <= a[i][j]){ gr[i][st.top()] = j; st.pop(); } st.push(j); } while(!st.empty()) st.pop(); FORD(j,m-1,0){ while(st.size() and a[i][st.top()] <= a[i][j]){ gl[i][st.top()] = j; st.pop(); } st.push(j); } REP(j,m){ if(gr[i][j] != -1 and gr[i][j] != j+1){ ll val = j*MX*MX+gr[i][j]*MX+i; if(rows[j][gr[i][j]].F == i+1){ rows[j][gr[i][j]].F--; } else{ rows[j][gr[i][j]] = {i,i}; } row_map.pb({val,rows[j][gr[i][j]].S}); } if(gl[i][j] != -1 and gl[i][j] != j-1 and gr[i][gl[i][j]] != j){ ll val = gl[i][j]*MX*MX+j*MX+i; if(rows[gl[i][j]][j].F == i+1){ rows[gl[i][j]][j].F--; } else{ rows[gl[i][j]][j] = {i,i}; } row_map.pb({val,rows[gl[i][j]][j].S}); } } } FORD(j,m-1,0){ stack<int> st; REP(i,n){ while(st.size() and a[st.top()][j] <= a[i][j]){ gd[st.top()][j] = i; st.pop(); } st.push(i); } while(!st.empty()) st.pop(); FORD(i,n-1,0){ while(st.size() and a[st.top()][j] <= a[i][j]){ gu[st.top()][j] = i; st.pop(); } st.push(i); } REP(i,n){ if(gd[i][j] != -1 and gd[i][j] != i+1){ ll val = i*MX*MX+gd[i][j]*MX+j; if(cols[i][gd[i][j]].F == j+1){ cols[i][gd[i][j]].F--; } else{ cols[i][gd[i][j]] = {j,j}; } col_map.pb({val,cols[i][gd[i][j]].S}); } if(gu[i][j] != -1 and gu[i][j] != i-1 and gd[gu[i][j]][j] != i){ ll val = gu[i][j]*MX*MX+i*MX+j; if(cols[gu[i][j]][i].F == j+1){ cols[gu[i][j]][i].F--; } else{ cols[gu[i][j]][i] = {j,j}; } col_map.pb({val,cols[gu[i][j]][i].S}); } } } vector<ll> bruh; FOR(i,1,n-1){ FOR(j,1,m-1){ // topleft if(gr[i][j-1] != -1 and gd[i-1][j] != -1){ gg[i][j].pb((gd[i-1][j]-1)*MX+gr[i][j-1]-1); } // topright if(gl[i][j+1] != -1 and gd[i-1][j] != -1){ gg[i][(gl[i][j+1]+1)].pb((gd[i-1][j]-1)*MX+j); } // bottomleft if(gr[i][j-1] != -1 and gu[i+1][j] != -1){ gg[(gu[i+1][j]+1)][j].pb((i)*MX+gr[i][j-1]-1); } // bottomright if(gl[i][j+1] != -1 and gu[i+1][j] != -1){ gg[(gu[i+1][j]+1)][(gl[i][j+1]+1)].pb((i)*MX+j); } // clockwise if(gr[i][j-1] != -1 and gd[i-1][gr[i][j-1]-1] != -1){ gg[i][j].pb((gd[i-1][gr[i][j-1]-1]-1)*MX+gr[i][j-1]-1); } // anti-clockwise if(gl[i][j+1] != -1 and gd[i-1][gl[i][j+1]+1] != -1){ gg[i][(gl[i][j+1]+1)].pb((gd[i-1][gl[i][j+1]+1]-1)*MX+j); } } } ll last = -1; int q = 0; FOR(i,1,n-1){ FOR(j,1,m-1){ if(SZ(gg[i][j]) > 1){ sort(all(gg[i][j])); } for(auto x:gg[i][j]){ ll val = i*MX*MX*MX+j*MX*MX+x; if(val == last) continue; last = val; check_rectangle(i,j,x/MX,x%MX,q); q++; } } } sort(all(quer_col)); sort(all(quer_row)); sort(all(col_map)); sort(all(row_map)); int cur = 0; for(auto x:col_map){ while(cur < q and quer_col[cur].F < x.F) cur++; while(cur < q and quer_col[cur].F == x.F){ if(quer_col[cur].S%MX <= x.S) b1[quer_col[cur].S/MX] = 1; cur++; } } cur = 0; for(auto x:row_map){ while(cur < q and quer_row[cur].F < x.F) cur++; while(cur < q and quer_row[cur].F == x.F){ if(quer_row[cur].S%MX <= x.S) b2[quer_row[cur].S/MX] = 1; cur++; } } REP(i,q){ if(b1[i] and b2[i]) ans++; } // cout << ((double)clock() / CLOCKS_PER_SEC) << "\n"; return ans; }
#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...