Submission #145141

#TimeUsernameProblemLanguageResultExecution timeMemory
145141jacynkaaRectangles (IOI19_rect)C++14
0 / 100
638 ms600536 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 = 2505; vector<int> prawo[MAXN][MAXN]; vector<int> dol[MAXN][MAXN]; vector<pii> R[MAXN][MAXN]; vector<pii> D[MAXN][MAXN]; int n, m; int tab[MAXN][MAXN]; long long ans = 0; void wypelnij1(vector<int> (&P)[MAXN][MAXN]) { rep(i, n) { vector<pii> X; rep(j, m) X.pb({tab[i][j], j}); sort(all(X)); reverse(all(X)); set<pii> S; int j = 0; while (j < X.size()) { int k = j; while (k + 1 < X.size() && X[j].nd == X[k + 1].nd) k++; for (int l = j; l <= k; l++) { // cerr << X[l].nd << " " << X[l].st << endl; S.insert({X[l].nd, X[l].st}); } for (int l = j; l <= k; l++) { auto r = S.find({X[l].nd, X[l].st}); auto q = (r == S.begin()) ? r : next(r, -1); auto s = (next(r, 1) == S.end()) ? r : next(r, 1); // cerr << q->st << " " << r->st << " " << s->st << endl; if (r->st - q->st - 1 > 0) //popraawic!!!! { P[i][q->st].pb(r->st - q->st - 1); //cerr << q->st << " ech1 " << r->st << endl; } if (s->st - r->st - 1 > 0) { P[i][r->st].pb(s->st - r->st - 1); //cerr << s->st << " ech2 " << r->st << endl; } } j = k + 1; } } } void wypelnij2(vector<int> (&zrodlo)[MAXN][MAXN], vector<pii> (&ujscie)[MAXN][MAXN]) { rep(j, m) { vector<pii> X(3e3, {-1, -1}); for (int i = n - 1; i >= 0; i--) for (int a : zrodlo[i][j]) { X[a] = (X[a].st == i + 1) ? mp(i, X[a].nd + 1) : mp(i, 1); ujscie[i][j].pb({a, X[a].nd}); } } } void obroc() { rep(i, n) rep(j, m) if (i > j) swap(tab[i][j], tab[j][i]), swap(D[i][j], D[j][i]), swap(dol[i][j], dol[j][i]); swap(n, m); } void solve(int i, int j) { for (auto A : D[i][j + 1]) for (auto B : R[i + 1][j]) if (B.nd >= A.st && A.nd >= B.st) { // cout << "tuutaj:" << i << " " << j << endl; ans++; } } long long count_rectangles(vector<vector<int>> A) { n = A.size(); m = A[0].size(); rep(i, n) rep(j, m) tab[i][j] = A[i][j]; wypelnij1(prawo); wypelnij2(prawo, R); obroc(); wypelnij1(dol); wypelnij2(dol, D); obroc(); /* rep(i, n) { rep(j, m) { cout << i << " " << j << "::: "; for (auto a : D[i][j]) cout << a.st << " " << a.nd << " "; // cout << a << " /// "; } cout << endl; } cout << "adjsff" << endl; rep(i, n) { rep(j, m) { cout << i << " " << j << "::: "; for (auto a : R[i][j]) cout << a.st << " " << a.nd << " "; // cout << a << " /// "; } cout << endl; } */ rep(i, n - 1) rep(j, m - 1) solve(i, j); return ans; } /* main() { _upgrade; cout << count_rectangles({{4, 8, 7, 5, 6}, {7, 4, 10, 3, 5}, {9, 7, 20, 14, 2}, {9, 14, 7, 3, 6}, {5, 7, 5, 2, 7}, {4, 5, 13, 5, 6}}) << endl; } */

Compilation message (stderr)

rect.cpp: In function 'void wypelnij1(std::vector<int> (&)[2505][2505])':
rect.cpp:41:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (j < X.size())
                ~~^~~~~~~~~~
rect.cpp:45:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (k + 1 < X.size() && X[j].nd == X[k + 1].nd)
                    ~~~~~~^~~~~~~~~~
#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...