結果
問題 | No.2574 Defect-free Rectangles |
ユーザー |
![]() |
提出日時 | 2023-11-28 14:16:16 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,034 ms / 2,000 ms |
コード長 | 3,019 bytes |
コンパイル時間 | 3,163 ms |
コンパイル使用メモリ | 263,388 KB |
実行使用メモリ | 38,656 KB |
最終ジャッジ日時 | 2024-09-26 12:54:25 |
合計ジャッジ時間 | 8,733 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <bits/stdc++.h>using namespace std;#pragma GCC target("avx2")#pragma GCC optimize("Ofast")#pragma GCC optimize("unroll-loops")template<typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }template<typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }#define rep(i, n) for (int i = 0; i < (long long)(n); i++)#define rep2(i, m ,n) for (int i = (m); i < (long long)(n); i++)#define REP(i, n) for (long long i = 1; i < (long long)(n); i++)typedef long long ll;#define updiv(N,X) (N + X - 1) / X#define l(n) n.begin(),n.end()#define YesNo(Q) Q==1?cout<<"Yes":cout<<"No"using P = pair<int, int>;const int MOD = 998244353LL;template <int D> struct fast_set {static_assert(1 <= D && D <= 6);using U = uint64_t;int n;std::array<std::vector<U>, D> a;fast_set(int n_ = 0) : n(n_) {assert(0 <= n && n <= int64_t(1) << (6*D));int m = n ? n : 1;for (int d = 0; d < D; d++) {m = (m + 63) >> 6;a[d].assign(m, 0);}}bool empty() const {return !a[D-1][0];}bool contains(int i) const {return (a[0][i >> 6] >> (i & 63)) & 1;}void insert(int i) {for (int d = 0; d < D; d++) {int q = i >> 6, r = i & 63;a[d][q] |= U(1) << r;i = q;}}void erase(int i) {for (int d = 0; d < D; d++) {int q = i >> 6, r = i & 63;if ((a[d][q] &= ~(U(1) << r))) break;i = q;}}int next(int i) const {for (int d = 0; d < D; d++) {int q = i >> 6, r = i & 63;if (q >= int(a[d].size())) break;U upper = a[d][q] >> r;if (upper) {i += __builtin_ctzll(upper);for (int e = d-1; e >= 0; e--) {i = i << 6 | __builtin_ctzll(a[e][i]);}return i;}i = q+1;}return n;}int prev(int i) const {for (int d = 0; d < D; d++) {if (i < 0) break;int q = i >> 6, r = i & 63;U lower = a[d][q] << (63-r);if (lower) {i -= __builtin_clzll(lower);for (int e = d-1; e >= 0; e--) {i = i << 6 | (63 - __builtin_clzll(a[e][i]));}return i;}i = q-1;}return -1;}};ll solve(vector<int> &w){fast_set<2> st(w.size());vector<pair<ll,ll>> v(w.size());rep(i,w.size()){v[i] = pair(w[i],i);}sort(l(v));int n = w.size();ll ans = 0;rep(i,n){auto t = st.next(v[i].second);auto k = st.prev(v[i].second);ans += (v[i].second-(ll)(k)) * ((ll)(t)-v[i].second) * v[i].first;st.insert(v[i].second);}return ans;}int main(){ll h,w,n;cin>>h>>w>>n;vector<vector<int>> v(h,vector<int>(w,0));rep(i,n){int a,b;cin>>a>>b;a--;b--;v[a][b] = 1;}// otp(v);//vector<vector<ll>> t(h,vector<ll>(w,0));rep(i,w){ll now = 0;rep(j,h){now++;if(v[h-j-1][i]==1){now = 0;}v[h-j-1][i] = now;}}// otp(v);ll ans = 0;rep(i,h){// rep(j,h){cout << w[j] << " ";}cout<<endl;ans += solve(v[i]);// cout << solve(w).val() << endl;}// vector<ll> y={2,1,3,4,5};//cout << solve(y) << endl;//cout << solveg(y) << endl;cout << ans << endl;}