Submission #1204504

#TimeUsernameProblemLanguageResultExecution timeMemory
1204504countlessRectangles (IOI19_rect)C++20
18 / 100
5099 ms332056 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; const ll MOD = 998244353; const ll INF = 1e18; const ld EPS = 1e-12; #define endl "\n" #define sp <<" "<< #define REP(i, a, b) for(ll i = a; i < b; i++) #define dbg(x) cout << #x << " = " << x << endl #define mp make_pair #define pb push_back #define fi first #define se second #define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) ((ll)(x).size()) struct custom_hash { static uint64_t splitmix64(uint64_t x) { // http://xorshift.di.unimi.it/splitmix64.c x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; template <typename Key, typename Value> using hash_map = unordered_map<Key, Value, custom_hash>; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // uniform_int_distribution<int>(a, b)(rng); // shuffle(all(a), rng); // d, u, r, l int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; // giving up and turning in a brute force ll count_rectangles(vector<vector<int>> a) { ll n = a.size(), m = a[0].size(); ll ans = 0, curr; // assert(n <= 30 and m <= 30); auto in = [&](int x, int y) -> bool { return (0 < x and x < n-1 and 0 < y and y < m-1); }; map<pair<pair<int, int>, pair<int, int>>, bool> vis; auto checkRect = [&](int x, int y, int xx, int yy) -> int { if (!in(x,y) or !in(xx, yy)) return 0; if (x > xx) swap(x, xx); if (y > yy) swap(y, yy); if (vis[{{x, y}, {xx, yy}}]) return 0; vis[{{x, y}, {xx, yy}}] = true; REP(i, x, xx+1) { REP(j, y, yy+1) { int val = a[i][j]; if (val >= a[i][y-1] or val >= a[i][yy+1] or val >= a[x-1][j] or val >= a[xx+1][j]) { return 0; } } } return 1; }; REP(i, 0, n*m) { int x = i / m, y = i % m; REP(j, i, n*m) { int xx = j / m, yy = j % m; ans += checkRect(x, y, xx, yy); } } 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...