| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1063028 |
2024-08-17T13:29:52 Z |
Ahmed57 |
Rectangles (IOI19_rect) |
C++17 |
|
3 ms |
860 KB |
#include "bits/stdc++.h"
using namespace std;
int seg[800001];
void build(int p,int l,int r){
if(l==r){
seg[p] = 0;
return ;
}
int md = (l+r)/2;
build(p*2,l,md);
build(p*2+1,md+1,r);
seg[p] = min(seg[p*2],seg[p*2+1]);
}
void update(int p,int l,int r,int idx,int val){
if(l==r){
seg[p]=max(seg[p],val);
return ;
}
int md = (l+r)/2;
if(idx<=md)update(p*2,l,md,idx,val);
else update(p*2+1,md+1,r,idx,val);
seg[p] = min(seg[p*2],seg[p*2+1]);
}
int query(int p,int l,int r,int lq,int rq){
if(r<lq||l>rq||lq>rq)return 1e9;
if(l>=lq&&r<=rq)return seg[p];
int md = (l+r)/2;
return min(query(p*2,l,md,lq,rq),query(p*2+1,md+1,r,lq,rq));
}
long long count_rectangles(vector<vector<int>> a){
int n = a.size();
int m = a[0].size();
vector<pair<int,int>> rngr[n+1],rngc[m+1];
for(int i = 0;i<n;i++){
stack<int> st;
for(int j = 0;j<m;j++){
while(!st.empty()&&a[i][st.top()]<a[i][j]){
if(st.top()+1<=j-1){
rngr[i].push_back({st.top(),j});
}
st.pop();
}
if(st.size()){
if(st.top()+1<=j-1){
rngr[i].push_back({st.top(),j});
}
}
st.push(j);
}
sort(rngr[i].begin(),rngr[i].end());
}
for(int j = 0;j<m;j++){
stack<int> st;
for(int i = 0;i<n;i++){
while(!st.empty()&&a[st.top()][j]<a[i][j]){
if(st.top()+1<=i-1){
rngc[j].push_back({st.top(),i});
}
st.pop();
}
if(st.size()){
if(st.top()+1<=i-1){
rngc[j].push_back({st.top(),i});
}
}
st.push(i);
}
sort(rngc[j].begin(),rngc[j].end());
}
vector<int> rows[n+1];
vector<pair<int,int>> cols[n+1];
for(int i = n-1;i>=0;i--){
for(int j = 0;j<rngr[i].size();j++){
int it = lower_bound(rngr[i+1].begin(),rngr[i+1].end(),make_pair(rngr[i][j].first,rngr[i][j].second))-rngr[i+1].begin();
if(it<rngr[i+1].size()&&rngr[i+1][it]==rngr[i][j]){
rows[i].push_back(rows[i+1][it]);
}else{
rows[i].push_back(i);
}
}
}
// for(int i = 0;i<n;i++){
// for(auto j:rngr[i]){
// cout<<j.first<<" "<<j.second<<endl;
// }
// cout<<"---------------------"<<endl;
// }
long long all = 0;
int col[m] = {0};
for(int i = 0;i<n;i++){
int idx = (int)(rngr[i].size())-1;
vector<pair<int,int>> lol[m];
for(int j = 0;j<m;j++){
while(col[j]<rngc[j].size()&&rngc[j][col[j]].first<i){
lol[j].push_back({rngc[j][col[j]].second,0});
col[j]++;
}
sort(lol[j].begin(),lol[j].end());
}
vector<array<int,3>> rng[m+1];
for(int j = 0;j<m;j++){
for(int e = 0;e<lol[j].size();e++){
if(lol[j][e].second)continue;
int st = j;
while(1){
if(st==m){
st--;
break;
}
int it = lower_bound(lol[st].begin(),lol[st].end(),make_pair(lol[j][e].first,0))-lol[st].begin();
if(it<lol[st].size()&&lol[st][it].first==lol[j][e].first){
lol[st][it].second = 1;
st++;
}else{
st--;
break;
}
}
rng[st].push_back({st,lol[j][e].first,1});
if(j)rng[j-1].push_back({st,lol[j][e].first,0});
}
}
reverse(rngr[i].begin(),rngr[i].end());
int cur = m-1;
multiset<pair<int,int>> s;
for(auto j:rngr[i]){
int la = rows[i][idx--];
//cout<<j.first<<" "<<j.second<<" "<<la<<" "<<i<<endl;
while(cur>j.first){
for(auto e:rng[cur]){
if(e[2]==1)s.insert({e[0],e[1]});
else s.erase(s.lower_bound(make_pair(e[0],e[1])));
}
cur--;
}
if(s.empty())continue;
auto it = s.end();
it--;
while((*it).first>=j.second-1){
if((*it).second-1<=la){
all++;
}
if(it==s.begin())break;
it--;
}
}
}
return all;
}
// signed main(){
// cout<<count_rectangles({{4, 8, 7, 5, 6},
// {7, 4, 10, 3, 5},
// {9, 7, 20, 14, 2},
// {9, 14, 7, 3, 6},
// {5, 7, 5, 2, 7},
// {4, 5, 13, 5, 6}});
// }
Compilation message
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:73:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(int j = 0;j<rngr[i].size();j++){
| ~^~~~~~~~~~~~~~~
rect.cpp:75:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | if(it<rngr[i+1].size()&&rngr[i+1][it]==rngr[i][j]){
| ~~^~~~~~~~~~~~~~~~~
rect.cpp:94:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | while(col[j]<rngc[j].size()&&rngc[j][col[j]].first<i){
| ~~~~~~^~~~~~~~~~~~~~~
rect.cpp:102:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for(int e = 0;e<lol[j].size();e++){
| ~^~~~~~~~~~~~~~
rect.cpp:111:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | if(it<lol[st].size()&&lol[st][it].first==lol[j][e].first){
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
860 KB |
Output is correct |
| 2 |
Correct |
2 ms |
860 KB |
Output is correct |
| 3 |
Correct |
1 ms |
708 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
3 ms |
860 KB |
Output is correct |
| 6 |
Correct |
2 ms |
856 KB |
Output is correct |
| 7 |
Correct |
2 ms |
860 KB |
Output is correct |
| 8 |
Correct |
2 ms |
860 KB |
Output is correct |
| 9 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
