제출 #1190141

#제출 시각아이디문제언어결과실행 시간메모리
1190141alexddRectangles (IOI19_rect)C++20
100 / 100
2162 ms889192 KiB
#pragma GCC optimize("O3,unroll-loops") #include "rect.h" #include<iostream> #include<cassert> #include<algorithm> using namespace std; int n,m; vector<pair<int,int>> get_bune(const vector<int>&v) { vector<pair<int,int>> bune; vector<int> dq; for(int i=0;i<v.size();i++) { while(!dq.empty() && v[i] > v[dq.back()]) { if(dq.back()+1 <= i-1) bune.push_back({dq.back()+1,i-1}); dq.pop_back(); } if(!dq.empty() && dq.back()+1 <= i-1) bune.push_back({dq.back()+1,i-1}); if(!dq.empty() && v[dq.back()] == v[i]) dq.pop_back(); dq.push_back(i); } return bune; } vector<pair<int,int>> bune_pe_rand[2505]; vector<int> coloane_bune[2505][2505]; vector<int> randuri_bune[2505][2505],primu[2505][2505]; int poz_rbune[2505][2505]; int aib[2505][10005]; int sizaib[2505]; int cntscos[2505][2505]; void baga(int x, int y) { x++; y++; int aux=0; for(int i=x;i>0;i-=(i&(-i))) { aib[i][sizaib[i]++] = y; } } void init() { for(int i=1;i<=m;i++) { sort(aib[i],aib[i]+sizaib[i]); reverse(aib[i],aib[i]+sizaib[i]); } } void scoate(int x, int y)//------------------------------------------------------ { x++; y++; for(int i=x;i>0;i-=(i&(-i))) cntscos[i][y]++; } void scoate_tot() { for(int i=1;i<=m;i++) { for(int j=0;j<sizaib[i];j++) cntscos[i][aib[i][j]]=0; sizaib[i]=0; } } int debagat[1000000],cntdeb; int qry(int x, int y) { x++; y++; int aux=0; for(int i=x;i<=m;i+=(i&(-i))) { if(sizaib[i]==0 || aib[i][sizaib[i]-1] > y)continue; cntdeb=0; for(int j=sizaib[i]-1;j>=0 && aib[i][j]<=y;j--) { if(cntscos[i][aib[i][j]] > 0) { cntscos[i][aib[i][j]]--; sizaib[i]--; } else { debagat[cntdeb++] = aib[i][j]; aux++; } } for(int j=0;j<cntdeb;j++) aib[i][sizaib[i]-1-j] = debagat[j]; } return aux; } vector<pair<int,int>> scoase[2505]; long long count_rectangles(std::vector<std::vector<int>> a) { n = a.size(); m = a[0].size(); long long rez=0; for(int i=1;i+1<a.size();i++) { bune_pe_rand[i] = get_bune(a[i]); for(auto [x,y]:bune_pe_rand[i]) randuri_bune[x][y].push_back(i); } for(int x=1;x+1<m;x++) { for(int y=x;y+1<m;y++) { if(randuri_bune[x][y].empty()) continue; primu[x][y].resize(randuri_bune[x][y].size() + 2); int ult = a.size(); if(randuri_bune[x][y].back() != (int)a.size() - 2) ult = randuri_bune[x][y].back() + 1; primu[x][y][randuri_bune[x][y].size()] = ult; for(int i=randuri_bune[x][y].size()-1;i>0;i--) { if(randuri_bune[x][y][i] != randuri_bune[x][y][i-1] + 1) ult = randuri_bune[x][y][i-1] + 1; primu[x][y][i] = ult; } } } for(int i=1;i+1<m;i++) { vector<int> aux; for(int j=0;j<a.size();j++) aux.push_back(a[j][i]); vector<pair<int,int>> bune = get_bune(aux); for(auto [x,y]:bune) coloane_bune[x][y].push_back(i); } for(int sus=1;sus+1<a.size();sus++) { for(int jos=sus;jos<=a.size();jos++) scoase[jos].clear(); for(auto [x,y]:bune_pe_rand[sus]) { baga(x,y); while(randuri_bune[x][y][poz_rbune[x][y]] < sus) poz_rbune[x][y]++; scoase[primu[x][y][poz_rbune[x][y]+1]].push_back({x,y}); } init(); for(int jos=sus;jos+1<a.size();jos++) { //for(int i=0;i<scoase[jos].size();i++) upd(scoase[jos][i].first,scoase[jos][i].second,-1); for(auto [x,y]:scoase[jos]) scoate(x,y); //for(pair<int,int> x:scoase[jos]) upd(x.first,x.second,-1); if(!coloane_bune[sus][jos].empty()) { int ult=0; for(int i=0;i+1<coloane_bune[sus][jos].size();i++) { if(coloane_bune[sus][jos][i] + 1 != coloane_bune[sus][jos][i+1]) { rez += qry(coloane_bune[sus][jos][ult],coloane_bune[sus][jos][i]); ult = i+1; } } rez += qry(coloane_bune[sus][jos][ult],coloane_bune[sus][jos][coloane_bune[sus][jos].size() - 1]); } } scoate_tot(); } assert(rez <= 4*n*m); return rez; } /* ne fixam linia de sus apoi mergem cu linia de jos in jos, o sa avem la inceput O(N) perechi de coloane candidate cand adaugam o linie in jos o sa dezactivam niste perechi de coloane trebuie sa verificam pt fiecare (sus,jos) care coloane sunt bune asta o sa fie O(N^2), pt ca fiecare coloana o sa apara in O(N) (sus,jos)-uri facem un dsu in care tinem si candidatii de perechi de coloane si cam asta e tot sper */
#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...