Submission #1021169

#TimeUsernameProblemLanguageResultExecution timeMemory
1021169nisanduuRectangles (IOI19_rect)C++14
0 / 100
84 ms41948 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; bool check(ll i,ll j,ll n,ll m,ll u,ll d,ll l,ll r,vector<vector<int>>&a){ if(i<=0||j<=0||i>=(n-1)||j>=(m-1)) return false; if(a[i][j]<l&&a[i][j]<r&&a[i][j]<u&&a[i][j]<d) return true; return false; } long long count_rectangles(std::vector<std::vector<int> > a) { ll n = a.size(); ll m = a[0].size(); ll cnt = 0; map<ll,map<ll,ll>> hash; queue<vector<ll>> pq; // Row Col U D L R for(ll i=1;i<n-1;i++){ for(ll j=1;j<m-1;j++){ if(a[i][j]<a[i+1][j]&&a[i][j]<a[i-1][j]&&a[i][j]<a[i][j+1]&&a[i][j]<a[i][j-1]){ vector<ll> vec = {i,j,a[i-1][j],a[i+1][j],a[i][j-1],a[i][j+1]}; pq.push(vec); hash[i][j]=1; } } } vector<ll> dr = {-1,0,1,0}; vector<ll> dc = {0,-1,0,1}; ll ans = 0; while(!pq.empty()){ vector<ll> v = pq.front(); pq.pop(); ans++; for(ll i=0;i<4;i++){ ll nr = v[0]+dr[i]; ll nc = v[1]+dc[i]; if(check(nr,nc,n,m,v[2],v[3],v[4],v[5],a)){ if(!hash[nr][nc]){ hash[nr][nc]=1; vector<ll> nv = v; if(i==0){ nv[2] = a[nr-1][nc]; }else if(i==1){ nv[4] = a[nr][nc-1]; }else if(i==2){ nv[3] = a[nr+1][nc]; }else{ nv[5] = a[nr][nc+1]; } nv[0]=nr; nv[1]=nc; pq.push(nv); } } } } return ans; }

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:16:8: warning: unused variable 'cnt' [-Wunused-variable]
   16 |     ll cnt = 0;
      |        ^~~
#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...