Submission #918563

#	Time	Username	Problem	Language	Result	Execution time	Memory
918563		xynex	Rectangles (IOI19_rect)	C++17	0 / 100	140 ms	189732 KiB

rect

/**
  * Author: Tenjin
  * Created: 27.04.2022 18:58
  * Why am I so stupid? :c
  * Slishkom slab
**/

#include <bits/stdc++.h>

// #pragma GCC optimize("inline")
// #pragma GCC optimize("-fgcse,-fgcse-lm")
// #pragma GCC optimize("-ftree-pre,-ftree-vrp")
// #pragma GCC optimize("-ffast-math")
// #pragma GCC optimize("-fipa-sra")
// #pragma GCC optimize("-fpeephole2")
// #pragma GCC optimize("-fsched-spec")
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")

using namespace std;

#define ll long long
#define pr pair
#define vt vector
#define ff first
#define ss second
#define sz(a) (int)a.size()
#define pb push_back
#define pf push_front
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

template<typename T> T get_rand(T l, T r) {
  random_device rd;
  mt19937 gen(rd());
  return uniform_int_distribution<T>(l, r)(gen);
}

template<class A> void read(vt<A>& v);
template<class A, size_t S> void read(array<A, S>& a);
template<class T> void read(T& x) { cin >> x; }
void read(double& d) { string t; read(t); d = stod(t); }
void read(long double& d) { string t; read(t); d = stold(t); }
template<class H, class... T> void read(H& h, T&... t) { read(h); read(t...); }
template<class A> void read(vt<A>& x) { for (auto& a : x) read(a); }
template<class A, size_t S> void read(array<A, S>& x) { for (auto& a : x) read(a); }

string to_string(char c) { return string(1, c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return string(s); }
string to_string(string s) { return s; }
string to_string(vt<bool> v) { string res; for (int i = 0; i < sz(v); ++i) res += char('0' + v[i]); return res; }
template<size_t S> string to_string(bitset<S> b) { string res; for (int i = 0; i < S; ++i) res += char('0' + b[i]); return res; }
template<class T> string to_string(T v) { bool f = 1; string res; for (auto x : v) { if (!f) res += ' '; f = 0; res += to_string(x); } return res; }

template<class A> void write(A x) { cout << to_string(x); }
template<class H, class... T> void write(const H& h, const T&... t) { write(h); write(t...); }

void print() { write("\n"); }
template<class H, class... T> void print(const H& h, const T&... t) { write(h); if (sizeof...(t)) write(' '); print(t...); }

void freop(string s) {
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}

const int MOD = 1e9 + 7;
const ll INF = 1e14;
const int M = 4e5 + 5;
const double long pi = acos(-1);
const double long eps = 1e-12;
const int sq = 700;

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
/* ll vs int*/

const int N = 1e6 + 5;

/*
6 5
4 8 17 5 6
17 4 10 13 5
29 7 10 14 2
9 14 27 3 6
5 7 5 2 7
4 5 13 5 6


6 5
4 8 7 5 6
9 4 10 3 5
7 4 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6

6 5
4 8 9 5 6
8 4 7 9 5
9 7 4 8 2
9 8 8 3 6
5 27 5 2 7
4 5 13 5 6


30 13
2314857 2951714 2551799 1262649 877317 2582030 1583139 3582015 1970170 2496877 252584 1959948 809239
1363336 486953 3562759 2227001 1996347 1994014 2317663 3232136 648728 2110306 2235717 2759784 2530855
258050 2824581 1243255 3198783 565865 231889 3727287 818081 2547404 3225075 3106983 1408265 2995366
1583118 3603184 3629350 727853 1632409 2090115 1933387 83572 2600107 3982487 2531332 427817 3615973
3440551 482330 832180 2483232 1194814 1255098 3085141 3601105 2004042 2837153 2452976 2727248 874027
1258869 875364 1785054 825988 2603807 616044 1136447 2155243 2614282 71407 1427398 536403 3683916
1342075 3590476 2175341 451150 616801 2691611 3044834 1464107 2158164 1823214 2852005 3843741 3348365
3275922 56468 169199 1391242 3905121 2188314 2243511 542710 891329 1856147 1366638 3533582 2388423
414756 228308 1784355 2073402 285249 2482853 950126 2479306 3261135 2401265 1132321 2475699 3500210
3639115 932461 412166 3184319 2485044 3895091 2327009 850550 583679 1610883 1517452 756022 1390820
2087853 1101237 515757 1513050 2877836 2764525 2414358 1468916 2674305 2446104 295599 841409 3215968
3119789 2516751 1471712 2600507 1997824 1353835 3994432 2006376 1507633 1140685 2177209 2927071 3424545
1674397 2008442 3544943 2924176 935153 2249156 3802239 1864176 1019795 1979123 1766617 694370 1733081
3151503 2112818 3513114 3136472 1994096 3379937 3919391 2547259 2798496 1308083 3156335 3855647 1504459
1023261 3017057 2016620 1439369 14943 1514149 1117474 1422903 1921583 2637168 1213085 185921 774705
932281 1562426 2076680 2283504 608334 3233863 1378085 2061191 1317930 3481445 2062302 1298203 2405802
2744660 2002176 1689886 947679 682094 2670377 1742765 2807882 2301713 2735402 1556615 2514209 1582309
1972102 1431422 2324079 2151483 2611035 2163733 709144 2889064 2205017 2880931 52320 1498527 2933993
1209767 439593 3020508 3721396 1036704 142701 3927559 1608169 1743546 1625063 46581 2017411 808968
263329 3136612 293841 2117846 1207981 247502 2293469 2198968 2702265 1642631 637723 3263373 3860851
240802 1587995 1427863 188743 2698756 1850992 49687 1404055 830973 560046 1793635 882126 1947220
1902879 1925306 2563972 2903664 525375 2264944 2140527 1162814 1977719 1265162 1808117 2896293 956308
2481424 719088 1064586 496976 720141 3125893 2276444 1741080 881467 2570549 3588324 2535402 1767516
546865 2422130 2000584 2534743 3820322 3836881 936460 905455 2021753 279793 2611693 3353033 2670364
542176 1788941 1454467 3488899 3166602 806200 349711 2467429 3374884 2852311 1490036 223291 1904067
2283572 3167542 1022001 2893598 2541467 1310733 311674 3751564 762621 971844 1004691 2594274 3728923
3161793 2034612 614776 3670183 2325816 1707268 3862740 2715886 3833150 1644459 358172 2247126 3008803
2310628 2838931 3439134 526672 3878034 3828531 678835 1270375 1931564 574357 2934272 3603169 2515791
213795 737446 3581205 1683399 3125307 140091 3694357 3619274 1694258 356442 2055920 3991030 445263
2124254 193277 3567661 3047095 2066338 1717492 1375193 2159796 1294986 1069001 1972558 1182016 1628337
*/
vt<int> tot[701][701], tot1[701][701];
ll count_rectangles(vt<vt<int>> a) {
  int n = sz(a);
  int m = sz(a[0]);
  vt<vt<int>> L(n, vt<int> (m, -1)), R(n, vt<int> (m, -1));
  vt<vt<int>> L1(n, vt<int> (m, -1)), R1(n, vt<int> (m, -1));
  for(int i = 0; i < n; ++i) {
    vt<pr<int, int> > st;
    for(int j = 0; j < m; ++j) {
      while(!st.empty() && st.back().ff <= a[i][j]) st.pop_back();
      if(!st.empty()) L[i][j] = st.back().ss;
      else L[i][j] = -1;
      st.push_back({a[i][j], j});
    }
    st.clear();
    for(int j = m - 1; j >= 0; --j) {
      while(!st.empty() && st.back().ff <= a[i][j]) st.pop_back();
      if(!st.empty()) R[i][j] = st.back().ss;
      else R[i][j] = m;
      st.push_back({a[i][j], j});
    }
    for(int j = 0; j < m; ++j) {
      if(L[i][j] == -1) continue;
      tot[L[i][j]][R[i][j]].pb(i);
    }
  }
  for(int i = 0; i < m; ++i) {
    vt<pr<int, int> > st;
    for(int j = 0; j < n; ++j) {
      while(!st.empty() && st.back().ff <= a[j][i]) st.pop_back();
      if(!st.empty()) L1[j][i] = st.back().ss;
      else L1[j][i] = -1;
      st.push_back({a[j][i], j});
    }
    st.clear();
    for(int j = n - 1; j >= 0; --j) {
      while(!st.empty() && st.back().ff <= a[j][i]) st.pop_back();
      if(!st.empty()) R1[j][i] = st.back().ss;
      else R1[j][i] = n;
      st.push_back({a[j][i], j});
    }
    for(int j = 0; j < n; ++j) {
      if(L1[j][i] == -1) continue;
      tot1[L1[j][i]][R1[j][i]].pb(i);
    }
  }
  vt<pr<int, int>> ord;
  set<pr<pr<int, int>, pr<int, int>>> have;
  for(int i = 0; i < n; ++i) {
    for(int j = 0; j < m; ++j) {
      if(L[i][j] != -1 && R[i][j] < m && L1[i][j] != -1 && R1[i][j] < n && !have.count({{L[i][j], R[i][j]}, {L1[i][j], R1[i][j]}})) {
        ord.pb({i, j});
        have.insert({{L[i][j], R[i][j]}, {L1[i][j], R1[i][j]}});
      }
    }
  }
  int ans = 0;
  for(auto cur : ord) {
    int i = cur.ff, j = cur.ss;
    bool ok = 1;
    int l = 0, r = sz(tot1[L1[i][j]][R1[i][j]]) - 1;
    while((r - l) >= 0) {
      int mid = (r + l) >> 1;
      if(tot1[L1[i][j]][R1[i][j]][mid] < R[i][j]) l = mid + 1;
      else r = mid - 1;
    }
    if(l) l--;
    if(tot1[L1[i][j]][R1[i][j]][l] != R[i][j] - 1) ok = 0;
    int l1 = 0, r1 = sz(tot1[L1[i][j]][R1[i][j]]) - 1;
    while((r1 - l1) >= 0) {
      int mid = (r1 + l1) >> 1;
      if(tot1[L1[i][j]][R1[i][j]][mid] > L[i][j]) r1 = mid - 1;
      else l1 = mid + 1;
    }
    if(r1 < sz(tot1[L1[i][j]][R1[i][j]]) - 1) r1++;
    if(tot1[L1[i][j]][R1[i][j]][r1] != L[i][j] + 1) ok = 0;
    if((l - r1 + 1) != (R[i][j] - L[i][j] - 1)) ok = 0;
   // print(tot1[L1[i][j]][R1[i][j]][r1], tot1[L1[i][j]][R1[i][j]][l], r1, l);
    l = 0, r = sz(tot[L[i][j]][R[i][j]]) - 1;
    while((r - l) >= 0) {
      int mid = (r + l) >> 1;
      if(tot[L[i][j]][R[i][j]][mid] < R1[i][j]) l = mid + 1;
      else r = mid - 1;
    }
    if(l) l--;
    if(tot[L[i][j]][R[i][j]][l] != R1[i][j] - 1) ok = 0;
    l1 = 0, r1 = sz(tot[L[i][j]][R[i][j]]) - 1;
    while((r1 - l1) >= 0) {
      int mid = (r1 + l1) >> 1;
      if(tot[L[i][j]][R[i][j]][mid] > L1[i][j]) r1 = mid - 1;
      else l1 = mid + 1;
    }
    if(r1 < sz(tot[L[i][j]][R[i][j]]) - 1) r1++;
    if(tot[L[i][j]][R[i][j]][r1] != L1[i][j] + 1) ok = 0;
    if((l - r1 + 1) != (R1[i][j] - L1[i][j] - 1)) ok = 0;
    /*for(int l = L1[i][j] + 1; l < R1[i][j]; ++l) {
      //print(tot[l][L[i][j]][R[i][j]]);
      if(!tot[l][L[i][j]][R[i][j]]) ok = 0;
    }*/
     //print(i, j, L[i][j], R[i][j], L1[i][j], R1[i][j], ok);
    ans += ok;
  }
  return ans;
}

/*
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  //freop("");
  int t = 1;
  //read(t);
  for (int i = 1; i <= t; ++i) {
    //write("Case #" + to_string(i) + ": ");
    solve();
  }
  return 0;
}*/

Compilation message (stderr)

rect.cpp: In function 'void freop(std::string)':
rect.cpp:64:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   freopen((s + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:65:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |   freopen((s + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28