Submission #1190058

#TimeUsernameProblemLanguageResultExecution timeMemory
1190058alexddRectangles (IOI19_rect)C++20
100 / 100
2549 ms866676 KiB
#pragma GCC optimize("O3,unroll-loops") #include "rect.h" #include<iostream> #include<algorithm> using namespace std; vector<pair<int,int>> get_bune(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); } //sort(bune.begin(),bune.end()); 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][2505],m; int qry(int x, int y) { x++; y++; int aux=0; for(int i=x;i<=m;i+=(i&(-i))) for(int j=y;j>0;j-=(j&(-j))) aux += aib[i][j]; return aux; } void upd(int x, int y, int newv) { x++; y++; for(int i=x;i>0;i-=(i&(-i))) for(int j=y;j<=m;j+=(j&(-j))) aib[i][j] += newv; } vector<pair<int,int>> scoase[2505]; long long count_rectangles(std::vector<std::vector<int>> a) { 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]) { upd(x,y,+1); 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}); } 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]) upd(x,y,-1); //for(pair<int,int> x:scoase[jos]) upd(x.first,x.second,-1); /*int ult=0; for(int i=0;i<coloane_bune[sus][jos].size();i++) { if(i == (int)coloane_bune[sus][jos].size() - 1 || coloane_bune[sus][jos][i] + 1 != coloane_bune[sus][jos][i+1]) { int le = coloane_bune[sus][jos][ult], ri = coloane_bune[sus][jos][i]; rez += qry(le,ri); ult = i+1; } }*/ if(!coloane_bune[sus][jos].empty()) { int ult = coloane_bune[sus][jos][0]; int prec = ult-1; for(int x:coloane_bune[sus][jos]) { if(x != prec+1) { rez += qry(ult,prec); ult = x; } prec = x; } rez += qry(ult,prec); } } for(auto [x,y]:scoase[a.size()]) upd(x,y,-1); } 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...