Submission #1064928

#TimeUsernameProblemLanguageResultExecution timeMemory
1064928jerzykRectangles (IOI19_rect)C++17
72 / 100
1494 ms1048576 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> using namespace __gnu_pbds; using namespace std; #define pb push_back #define st first #define nd second typedef long long ll; typedef long double ld; const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL; const int II = 2 * 1000 * 1000 * 1000; const ll M = 1000LL * 1000LL * 1000LL + 7LL; const int N = 1<<12; int drz[2 * N]; int tab[N][N]; vector<int> intr[N][N]; vector<pair<int, int>> que[N][N]; bool czy[N]; long long answer = 0; void Add(int v, int x) { v += N; while(v > 0) {drz[v] += x; v /= 2;} } int Query(int a, int b) { a += N - 1; b += N + 1; int ans = 0; while(a / 2 != b / 2) { if(a % 2 == 0) ans += drz[a + 1]; if(b % 2 == 1) ans += drz[b - 1]; a /= 2; b /= 2; } return ans; } void CntR(int n, int m) { for(int i = 1; i <= n; ++i) { vector<pair<int, int>> kol; for(int j = m; j >= 1; --j) { while((int)kol.size() > 0 && kol.back().st <= tab[i][j]) kol.pop_back(); int xd = tab[i][j]; //cerr << "R: " << i << " " << j << "\n"; for(int k = kol.size() - 1; k >= 0 && tab[i][j - 1] > xd; --k) { intr[i][j].pb(kol[k].nd - 1); //cerr << kol[k].nd - 1 << " "; xd = max(xd, kol[k].st); } //cout << "\n"; kol.pb(make_pair(tab[i][j], j)); } } for(int j = 1; j <= m; ++j) { vector<pair<int, int>> akt; for(int i = j; i <= m; ++i) akt.pb(make_pair(i, 1)); for(int i = 1; i <= n; ++i) { vector<pair<int, int>> nxt; int k = 0; //cerr << "DP: " << i << " " << j << "\n"; for(int l = 0; l < (int)intr[i][j].size(); ++l) { while(k < (int)akt.size() && akt[k].st < intr[i][j][l]) ++k; if(k < (int)akt.size() && akt[k].st == intr[i][j][l]) { nxt.pb(akt[k]); ++k; }else nxt.pb(make_pair(intr[i][j][l], i)); que[i][intr[i][j][l]].pb(make_pair(j, i - nxt.back().nd + 1)); //cerr << nxt.back().st << " " << nxt.back().nd << "\n"; } akt = nxt; intr[i][j].clear(); } } } void CntL(int n, int m) { for(int j = 1; j <= m; ++j) { vector<pair<int, int>> kol; for(int i = 1; i <= n; ++i) { while((int)kol.size() > 0 && kol.back().st <= tab[i][j]) kol.pop_back(); int xd = tab[i][j]; //cerr << "U: " << i << " " << j << "\n"; for(int k = kol.size() - 1; k >= 0 && tab[i + 1][j] > xd; --k) { intr[i][j].pb(kol[k].nd + 1); //cerr << kol[k].nd + 1 << "\n"; xd = max(xd, kol[k].st); } sort(intr[i][j].begin(), intr[i][j].end()); kol.pb(make_pair(tab[i][j], i)); } } for(int i = 1; i <= n; ++i) { vector<pair<int, int>> akt; for(int j = i; j <= n; ++j) akt.pb(make_pair(j, 1)); for(int j = 1; j <= m; ++j) { vector<pair<int, int>> nxt; int k = 0; //cerr << "DP: " << i << " " << j << "\n"; for(int l = 0; l < (int)intr[i][j].size(); ++l) { while(k < (int)akt.size() && akt[k].st < intr[i][j][l]) ++k; if(k < (int)akt.size() && akt[k].st == intr[i][j][l]) { nxt.pb(make_pair(akt[k].nd, akt[k].st)); ++k; }else nxt.pb(make_pair(j, intr[i][j][l])); //cerr << nxt.back().nd << " " << nxt.back().st << "\n"; } akt = nxt; sort(akt.begin(), akt.end()); int lim = akt.size(); k = -1; //cout << "QUE: " << i << " " << j << "\n"; for(int l = 0; l < (int)que[i][j].size(); ++l) { while(k < lim - 1 && akt[k + 1].st <= que[i][j][l].st) { ++k; Add(i - akt[k].nd + 1, 1); } answer += (ll)Query(1, que[i][j][l].nd); //for(int r = 0; r < lim; ++r) //if(akt[r].st <= que[i][j][l].st && i - akt[r].nd + 1 <= que[i][j][l].nd) //++answer; } for(k = k; k >= 0; --k) Add(i - akt[k].nd + 1, -1); for(int l = 0; l < (int)akt.size(); ++l) swap(akt[l].st, akt[l].nd); sort(akt.begin(), akt.end()); intr[i][j].clear(); } } } long long count_rectangles(vector<vector<int>> xd) { int n = xd.size(), m = xd[0].size(); for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) tab[i][j] = xd[i - 1][j - 1]; CntR(n, m); CntL(n, m); return answer; }
#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...