Submission #583801

#TimeUsernameProblemLanguageResultExecution timeMemory
583801LucppRectangles (IOI19_rect)C++17
72 / 100
5105 ms947756 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; #define sz(x) ((int)(x).size()) typedef long long ll; vector<vector<int>> fen; void add(bool b, int i, int x){ for(i++; i < sz(fen[0]); i+=i&-i) fen[b][i] += x; } int qry(bool b, int i){ int ans = 0; for(i++; i > 0; i-=i&-i) ans += fen[b][i]; return ans; } int qry(bool b, int i, int j){ if(i > 0) return qry(b, j)-qry(b, i-1); else return qry(b, j); } long long count_rectangles(vector<vector<int>> a) { int n = sz(a), m = sz(a[0]); vector<vector<short>> r1(n, vector<short>(m, -1)), r2(n, vector<short>(m, -1)); for(int i = 1; i < n-1; i++){ stack<pair<int, int>> st({{a[i][0], 0}}); for(int j = 1; j < m; j++){ while(!st.empty() && a[i][j] > st.top().first){ auto [h, k] = st.top(); st.pop(); r2[i][k] = j-1; } if(!st.empty()) { if(st.top().first > a[i][j]) r1[i][j] = st.top().second+1; else r1[i][j] = r1[i][st.top().second]; } st.emplace(a[i][j], j); } } vector<vector<short>> c1(n, vector<short>(m, -1)), c2(n, vector<short>(m, -1)); for(int j = 1; j < m-1; j++){ stack<pair<int, int>> st({{a[0][j], 0}}); for(int i = 1; i < n; i++){ while(!st.empty() && a[i][j] > st.top().first){ auto [h, k] = st.top(); st.pop(); c2[k][j] = i-1; } if(!st.empty()){ if(st.top().first > a[i][j]) c1[i][j] = st.top().second+1; else c1[i][j] = c1[st.top().second][j]; } st.emplace(a[i][j], i); } } a.clear(); a.shrink_to_fit(); int mx = max(n, m); fen.resize(2, vector<int>(mx+1)); vector<bool> valid; vector<vector<tuple<bool, short, short, int>>> queries(mx*mx); unordered_set<ll> noDupl; int q = 0; int ans = 0; for(int i = 1; i < n-1; i++){ for(int j = 1; j < m-1; j++){ // cerr << "\n" << i << " " << j << " " << r1[i][j] << " " << r2[i][j] << " " << c1[i][j] << " " << c2[i][j] << "\n"; if(r1[i][j] != -1 && r2[i][j] != -1 && c1[i][j] != -1 && c2[i][j] != -1){ int x = c1[i][j]*mx + c2[i][j], y = r1[i][j]*mx + r2[i][j]; queries[x].emplace_back(0, j, 0, -1); queries[y].emplace_back(1, i, 0, -1); ll t = (ll)x*mx*mx+y; if(noDupl.count(t)) continue; noDupl.insert(t); valid.push_back(true); queries[x].emplace_back(0, r1[i][j], r2[i][j], q); queries[y].emplace_back(1, c1[i][j], c2[i][j], q); q++; } } } vector<vector<bool>> used(2, vector<bool>(mx)); vector<pair<bool, short>> undo; vector<tuple<bool, short, short, int>> qries; for(int id = 1; id < mx*mx; id++){ for(auto [b, i, j, ind] : queries[id]){ if(ind == -1){ if(!used[b][i]) add(b, i, 1), undo.emplace_back(b, i); used[b][i] = true; } else qries.emplace_back(b, i, j, ind); } for(auto [b, i, j, ind] : qries){ if(!valid[ind] || qry(b, i, j) != j-i+1) valid[ind] = false; } for(auto [b, i] : undo){ add(b, i, -1); used[b][i] = false; } qries.clear(); undo.clear(); } for(bool b : valid) ans += b; 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...