제출 #678285

#제출 시각아이디문제언어결과실행 시간메모리
678285someoneRectangles (IOI19_rect)C++14
100 / 100
3142 ms841612 KiB
#include <bits/stdc++.h> using namespace std; struct Req { bool isUpd; int x, y; }; const int N = 2500 + 42, M = 1 << 12; vector<int> val; vector<pair<int, int>> fin[N][N][2]; int n, m, pre[N][N], nb[N][N], sum[2*M]; inline int add(int l, int r, int i) { if(pre[l][r] != i+1) nb[l][r] = 0; pre[l][r] = i; return ++nb[l][r]; } void upd(int i, int v) { i += M; while(i) { sum[i] += v; i >>= 1; } } int getVal(int i) { i += M; int ans = sum[i]; while(i) { if(i & 1) ans += sum[i-1]; i >>= 1; } return ans; } long long count_rectangles(vector<vector<int>> a) { n = (int)a.size(); m = (int)a[0].size(); for(int i = n-2; i > 0; i--) { vector<int> maxi; for(int j = 0; j < m; j++) { while(!maxi.empty() && a[i][maxi.back()] < a[i][j]) maxi.pop_back(); if(!maxi.empty() && a[i][maxi.back()] != a[i][j] && maxi.back() < j-1) fin[i][maxi.back()+1][0].push_back({j-1, add(maxi.back()+1, j-1, i)-1}); maxi.push_back(j); } maxi.clear(); for(int j = m-1; j > -1; j--) { while(!maxi.empty() && a[i][maxi.back()] < a[i][j]) maxi.pop_back(); if(!maxi.empty() && j+1 < maxi.back()) fin[i][j+1][0].push_back({maxi.back()-1, add(j+1, maxi.back()-1, i)-1}); maxi.push_back(j); } } for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) nb[i][j] = pre[i][j] = 0; for(int j = m-2; j > 0; j--) { vector<int> maxi; for(int i = 0; i < n; i++) { while(!maxi.empty() && a[maxi.back()][j] < a[i][j]) maxi.pop_back(); if(!maxi.empty() && a[maxi.back()][j] != a[i][j] && maxi.back() < i-1) fin[maxi.back()+1][j][1].push_back({i-1, add(maxi.back()+1, i-1, j)-1}); maxi.push_back(i); } maxi.clear(); for(int i = n-1; i > -1; i--) { while(!maxi.empty() && a[maxi.back()][j] < a[i][j]) maxi.pop_back(); if(!maxi.empty() && i+1 < maxi.back()) fin[i+1][j][1].push_back({maxi.back()-1, add(i+1, maxi.back()-1, j)-1}); maxi.push_back(i); } } int ans = 0; for(int i = 1; i < n-1; i++) { for(int j = 1; j < m-1; j++) { vector<Req> req; for(auto pii : fin[i][j][0]) req.push_back({true, pii.first - j, pii.second}); for(auto pii : fin[i][j][1]) req.push_back({false, pii.second, pii.first - i}); sort(req.begin(), req.end(), [](Req a, Req b) { if(a.y == b.y) return a.isUpd && !b.isUpd; return a.y > b.y; }); for(Req q : req) { if(q.isUpd) upd(q.x, 1); else ans += getVal(q.x); } for(Req q : req) if(q.isUpd) upd(q.x, -1); } } 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...