| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 154191 |
2019-09-18T19:11:17 Z |
wilwxk |
Rectangles (IOI19_rect) |
C++14 |
|
5000 ms |
166716 KB |
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct cara {
int h, i, j;
int xl, xr, yl, yr;
bool operator<(cara _) const {
return h<_.h;
}
};
const int MAXN=2502;
const int INF=1e9+9;
vector<vector<int> > v;
vector<cara> lista;
int table[MAXN][MAXN][4];
int n, m, respf;
void histogrami() {
stack<pair<int, int> > st;
for(int i=0; i<n; i++) {
while(st.size()) st.pop(); st.push({INF, -1});
for(int j=0; j<m; j++) {
while(st.top().first<=v[i][j]) st.pop();
int cur=i*m+j;
lista[cur].xl=st.top().second+1;
st.push({v[i][j], j});
}
while(st.size()) st.pop(); st.push({INF, m});
for(int j=m-1; j>=0; j--) {
while(st.top().first<=v[i][j]) st.pop();
int cur=i*m+j;
lista[cur].xr=st.top().second-1;
st.push({v[i][j], j});
}
}
}
void histogramj() {
stack<pair<int, int> > st;
for(int j=0; j<m; j++) {
while(st.size()) st.pop(); st.push({INF, -1});
for(int i=0; i<n; i++) {
while(st.top().first<=v[i][j]) st.pop();
int cur=i*m+j;
lista[cur].yl=st.top().second+1;
st.push({v[i][j], i});
}
while(st.size()) st.pop(); st.push({INF, m});
for(int i=n-1; i>=0; i--) {
while(st.top().first<=v[i][j]) st.pop();
int cur=i*m+j;
lista[cur].yr=st.top().second-1;
st.push({v[i][j], i});
}
}
}
void upd() {
}
void quy() {
}
int query(int xl, int xr, int yl, int yr, int k) {
int resp=table[xl][yl][k];
for(int i=yl; i<=yr; i++) {
for(int j=xl; j<=xr; j++) {
if(k==0||k==2) resp=min(resp, table[i][j][k]);
else resp=max(resp, table[i][j][k]);
}
}
// printf("query %d %d %d %d %d >> %d\n", xl, xr, yl, yr, k, resp);
return resp;
}
void ativa(int ind) {
auto cur=lista[ind];
table[cur.i][cur.j][0]=cur.xl;
table[cur.i][cur.j][1]=cur.xr;
table[cur.i][cur.j][2]=cur.yl;
table[cur.i][cur.j][3]=cur.yr;
}
ll count_rectangles(vector< vector<int> > A) {
v=A; n=A.size(); m=A[0].size();
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
cara cur;
cur.h=v[i][j];
cur.i=i;
cur.j=j;
lista.push_back(cur);
}
}
histogrami();
histogramj();
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
table[i][j][0]=-1;
table[i][j][1]=INF;
table[i][j][2]=-1;
table[i][j][3]=INF;
}
}
// for(auto cur : lista) printf("(%d, %d): %d %d // %d %d\n", cur.i, cur.j, cur.xl, cur.xr, cur.yl, cur.yr);
sort(lista.begin(), lista.end());
for(int i=0; i<lista.size(); i++) {
// int mxl, mxr, myl, myr; //0, 1, 2, 3
ativa(i);
auto cur=lista[i];
if(query(cur.xl, cur.xr, cur.yl, cur.yr, 0)<cur.xl) continue;
if(query(cur.xl, cur.xr, cur.yl, cur.yr, 1)>cur.xr) continue;
if(query(cur.xl, cur.xr, cur.yl, cur.yr, 2)<cur.yl) continue;
if(query(cur.xl, cur.xr, cur.yl, cur.yr, 3)>cur.yr) continue;
respf++;
}
return respf;
}
Compilation message
rect.cpp: In function 'void histogrami()':
rect.cpp:24:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
while(st.size()) st.pop(); st.push({INF, -1});
^~~~~
rect.cpp:24:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
while(st.size()) st.pop(); st.push({INF, -1});
^~
rect.cpp:31:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
while(st.size()) st.pop(); st.push({INF, m});
^~~~~
rect.cpp:31:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
while(st.size()) st.pop(); st.push({INF, m});
^~
rect.cpp: In function 'void histogramj()':
rect.cpp:43:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
while(st.size()) st.pop(); st.push({INF, -1});
^~~~~
rect.cpp:43:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
while(st.size()) st.pop(); st.push({INF, -1});
^~
rect.cpp:50:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
while(st.size()) st.pop(); st.push({INF, m});
^~~~~
rect.cpp:50:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
while(st.size()) st.pop(); st.push({INF, m});
^~
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:111:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<lista.size(); i++) {
~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5082 ms |
1184 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Execution timed out |
5070 ms |
166716 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
