Submission #145447

#TimeUsernameProblemLanguageResultExecution timeMemory
145447jacynkaaRectangles (IOI19_rect)C++14
72 / 100
5164 ms907716 KiB
#include <bits/stdc++.h> #include <math.h> #include <chrono> using namespace std; //#pragma GCC optimize("-O3") #define endl "\n" #define mp make_pair #define st first #define nd second #define pii pair<int, int> #define pb push_back #define _upgrade ios_base::sync_with_stdio(0), cout.setf(ios::fixed), cout.precision(10) //cin.tie(0); cout.tie(0); #define REP(i, n) for (int i = 0; i < (n); ++i) #define FWD(i, a, b) for (int i = (a); i < (b); ++i) #define rep(i, n) for (int i = 0; i < (n); ++i) #define fwd(i, a, b) for (int i = (a); i < (b); ++i) #define all(c) (c).begin(), (c).end() #define what(x) cerr << #x << " is " << x << endl; const int MAXN = 2502; //UWAGA vector<int> dol[MAXN][MAXN]; vector<pair<short, short>> R[MAXN][MAXN]; vector<pair<short, short>> D[MAXN][MAXN]; int n, m; int tab[MAXN][MAXN]; long long ans = 0; void wypelnij2prawo() { rep(j, m) { vector<pii> X(3e3, {-1, -1}); for (int i = n - 1; i >= 0; i--) for (int a : dol[i][j]) { X[a] = (X[a].st == i + 1) ? mp(i, X[a].nd + 1) : mp(i, 1); R[i][j].pb({a, X[a].nd}); //glebokosc i ile } } } void wypelnij2dol() { rep(i, n) { vector<pii> X(3e3, {-1, -1}); for (int j = m - 1; j >= 0; j--) { for (int a : dol[i][j]) { X[a] = (X[a].st == j + 1) ? mp(j, X[a].nd + 1) : mp(j, 1); D[i][j].pb({a, X[a].nd}); //glebokosc i ile } dol[i][j].resize(0); dol[i][j].shrink_to_fit(); } } } vector<vector<int>> wypelnij1(vector<int> &Q) { vector<vector<int>> P(Q.size()); stack<pii> S; rep(i, Q.size()) { while (!S.empty() && S.top().st < Q[i]) S.pop(); if (!S.empty() && i - S.top().nd - 1 > 0) P[S.top().nd].pb(i - S.top().nd - 1); S.push(mp(Q[i], i)); } while (!S.empty()) S.pop(); for (int i = Q.size() - 1; i >= 0; i--) { while (!S.empty() && S.top().st < Q[i]) S.pop(); if (!S.empty() && S.top().nd - i - 1 > 0 && S.top().st != Q[i]) P[i].pb(S.top().nd - i - 1); S.push(mp(Q[i], i)); } return P; } const int rozmiar = (1 << 12); short ile[2 * rozmiar]; void dodaj(int x) { x += rozmiar; while (x > 0) { ile[x]++; x /= 2; } } int get(short x) { short p = rozmiar; short q = rozmiar + x; while (p <= q) { if (q % 2 == 0) { ans += ile[q]; q--; } p /= 2; q /= 2; } } void clear() { fill(ile, ile + rozmiar+MAXN, 0); } void solve(int i, int j) { //s cerr << i << " " << j << endl; if (R[i + 1][j].size() * D[i][j + 1].size() <= 1000) { for (auto &A : D[i][j + 1]) for (auto &B : R[i + 1][j]) if (B.nd >= A.st && A.nd >= B.st) ans++; return; } for (auto &B : D[i][j + 1]) swap(B.st, B.nd); sort(all(R[i + 1][j]), greater<pair<short, short>>()); sort(all(D[i][j + 1]), greater<pair<short, short>>()); /* cerr << "obecne tutaj::" << endl; for (auto A : D[i][j + 1]) cerr << A.st << " " << A.nd << endl; cerr << endl; for (auto A : R[i + 1][j]) cerr << A.st << " " << A.nd << endl; cerr << "koniec" << endl; */ int k = 0; int l = 0; while (l != R[i + 1][j].size() || k != D[i][j + 1].size()) { if (l == R[i + 1][j].size()) { dodaj(D[i][j + 1][k].nd); k++; continue; } if (k == D[i][j + 1].size()) { get(R[i + 1][j][l].nd); l++; continue; } if (R[i + 1][j][l].st <= D[i][j + 1][k].st) { dodaj(D[i][j + 1][k].nd); k++; continue; } else { get(R[i + 1][j][l].nd); l++; continue; } } clear(); } long long count_rectangles(vector<vector<int32_t>> A) { n = A.size(); m = A[0].size(); rep(i, n) rep(j, m) tab[i][j] = A[i][j]; rep(i, n) { auto X = wypelnij1(A[i]); rep(j, m) dol[i][j] = X[j]; } wypelnij2prawo(); rep(j, m) { vector<int> Y; rep(i, n) Y.pb(tab[i][j]); auto X = wypelnij1(Y); rep(i, n) dol[i][j] = X[i]; } wypelnij2dol(); /* cerr << "DOL" << endl; rep(i, n) { rep(j, m) { cerr << i << " " << j << ":: "; for (auto a : D[i][j]) cerr << a.st << " " << a.nd << ", "; cerr << endl; // cout << a << " /// "; } cerr << endl; } cerr << "PRAWO" << endl; rep(i, n) { rep(j, m) { cerr << i << " " << j << ":: "; for (auto a : R[i][j]) cerr << a.st << " " << a.nd << ", "; // cout << a << " /// "; cerr << endl; } cerr << endl; } */ rep(i, n - 1) rep(j, m - 1) solve(i, j); return ans; }

Compilation message (stderr)

rect.cpp: In function 'std::vector<std::vector<int> > wypelnij1(std::vector<int>&)':
rect.cpp:15:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i = 0; i < (n); ++i)
                                     ^
rect.cpp:66:5: note: in expansion of macro 'rep'
     rep(i, Q.size())
     ^~~
rect.cpp: In function 'int get(short int)':
rect.cpp:113:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
rect.cpp: In function 'void solve(int, int)':
rect.cpp:146:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (l != R[i + 1][j].size() || k != D[i][j + 1].size())
            ~~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:146:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (l != R[i + 1][j].size() || k != D[i][j + 1].size())
                                       ~~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:149:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (l == R[i + 1][j].size())
             ~~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:155:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (k == D[i][j + 1].size())
             ~~^~~~~~~~~~~~~~~~~~~~~
#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...