Submission #766789

#TimeUsernameProblemLanguageResultExecution timeMemory
766789khshgRectangles (IOI19_rect)C++14
0 / 100
1668 ms1048576 KiB
#include <cstdio> #include <unistd.h> #include <cassert> #include <string> #include<bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using str = string; using pi = pair<int, int>; using pl = pair<ll, ll>; using pd = pair<ld, ld>; #define mp make_pair #define ff first #define ss second #define ar array template<class T> using V = vector<T>; using vi = V<int>; using vb = V<bool>; using vl = V<ll>; using vd = V<ld>; using vs = V<str>; using vpi = V<pi>; using vpl = V<pl>; using vpd = V<pd>; #define sz(x) (int)((x).size()) #define bg(x) begin(x) #define all(x) bg(x), end(x) #define rall(x) (x).rbegin(), (x).rend() #define sor(x) sort(all(x)) #define rsz resize #define ins insert #define pb push_back #define eb emplace_back #define ft front() #define bk back() #define lb lower_bound #define ub upper_bound #define FOR(i, a, b) for(int i = (a); i < (b); ++i) #define F0R(i, a) FOR(i, 0, a) #define ROF(i, a, b) for(int i = (b) - 1; i >= (a); --i) #define R0F(i, a) ROF(i, 0, a) #define rep(a) F0R(_, a) #define trav(a, x) for(auto& a : x) template<class T> bool ckmin(T& a, const T& b) { return (b < a ? a = b, 1 : 0); } template<class T> bool ckmax(T& a, const T& b) { return (b > a ? a = b, 1 : 0); } const int dir[] = {0, -1, 0, 1, 0}; ll count_rectangles(V<vi> a) { ll ans = 0; int N = sz(a); int M = sz(a.bk); F0R(i, N) { F0R(j, M) { if(a[i][j] == 1) continue; queue<pi> q; q.push({i, j}); vpi is; while(sz(q)) { pi cur = q.ft; q.pop(); a[cur.ff][cur.ss] = 0; is.pb(cur); F0R(i, 4) { cur.ff += dir[i]; cur.ss += dir[i + 1]; if(min(cur.ff, cur.ss) >= 0 && cur.ff < N && cur.ss < M && a[cur.ff][cur.ss] == 0) { q.push(cur); } cur.ff -= dir[i]; cur.ss -= dir[i + 1]; } } sor(is); bool f = (is[0].ff <= is.bk.ff && is[0].ss <= is.bk.ss && (is.bk.ff - is[0].ff + 1) * (is.bk.ss - is[0].ss + 1) == sz(is)); trav(u, is) { f &= (u.ff >= is[0].ff && u.ff <= is.bk.ff && u.ss >= is[0].ss && u.ss <= is.bk.ss); } ans += f; } } return ans; } /* using namespace std; class InputReader { private: static const int SIZE = 4096; int inputFileDescriptor; char buf[SIZE]; int curChar; int numChars; public: inline InputReader(int _inputFileDescriptor): inputFileDescriptor(_inputFileDescriptor), curChar(0), numChars(0) { } inline void close() { ::close(inputFileDescriptor); } inline char read() { assert(numChars != -1); if (curChar >= numChars) { curChar = 0; numChars = ::read(inputFileDescriptor, buf, SIZE); if (numChars == -1) return -1; } return buf[curChar++]; } inline int readInt() { int c = eatWhite(); int sgn = 1; if (c == '-') { sgn = -1; c = read(); } int res = 0; do { assert(c >= '0' && c <= '9'); res *= 10; res += c - '0'; c = read(); } while (!isSpaceChar(c)); return res * sgn; } inline string readString() { char c = eatWhite(); string res; do { res += c; c = read(); } while (!isSpaceChar(c)); return res; } inline string readLine() { string res; while (true) { char c = read(); if (c == '\n' || c == '\r' || c == -1) break; res += c; } return res; } inline char eatWhite() { char c = read(); while (isSpaceChar(c)) c = read(); return c; } static inline bool isSpaceChar(char c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } }; int main() { InputReader inputReader(STDIN_FILENO); int n, m; n = inputReader.readInt(); m = inputReader.readInt(); vector<vector<int>> a(n, vector<int>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { a[i][j] = inputReader.readInt(); } } inputReader.close(); long long result = count_rectangles(a); printf("%lld\n", result); fclose(stdout); return 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...