제출 #857646

#제출 시각아이디문제언어결과실행 시간메모리
857646serifefedartarStrah (COCI18_strah)C++17
0 / 110
1045 ms34624 KiB
#include <bits/stdc++.h> using namespace std; #define fast ios::sync_with_stdio(0);cin.tie(0); #define s second #define f first typedef long long ll; const ll MOD = 1e9 + 7; const ll LOGN = 18; const ll INF = 1e15; const ll MAXN = 2010; vector<int> occ[2005]; int N, M; string grid[MAXN]; int emp[MAXN][MAXN], sg[4*MAXN], lazy[4*MAXN]; ll total = 0, ans = 0; void push(int k, int a, int b) { if (lazy[k] != -1) { sg[k] = lazy[k]; if (a != b) { lazy[2*k] = lazy[k]; lazy[2*k+1] = lazy[k]; } lazy[k] = -1; } } void update(int k, int a, int b, int q_l, int q_r, int new_val) { push(k, a, b); if (q_r < a || q_l > b) return ; if (q_l <= a && b <= q_r) { lazy[k] = new_val; push(k, a, b); return ; } update(2*k, a, (a+b)/2, q_l, q_r, new_val); update(2*k+1, (a+b)/2+1, b, q_l, q_r, new_val); sg[k] = max(sg[2*k], sg[2*k+1]); } ll calc(ll x) { return (x * x * x + 3 * x * x + 2 * x) / 6; } int get(int k, int a, int b, int pos) { push(k, a, b); if (b < pos || a > pos) return 0; if (a == b) return sg[k]; return get(2*k, a, (a+b)/2, pos) + get(2*k+1, (a+b)/2+1, b, pos); } int query(int k, int a, int b, int val) { push(k, a, b); if (a == b) { if (sg[k] >= val) return a; return N+1; } push(2*k, a, (a+b)/2); if (sg[2*k] < val) return query(2*k+1, (a+b)/2 + 1, b, val); return query(2*k, a, (a+b)/2, val); } void split(int pos) { int Q = get(1, 0, N, pos); int l = query(1, 0, N, Q); int r = query(1, 0, N, Q + 1) - 1; ans -= calc(r - l); ans += calc(pos - l - 1); ans += calc(r - pos); update(1, 0, N, pos, r, pos); } int main() { fast cin >> N >> M; for (int i = 1; i <= N; i++) cin >> grid[i]; for (int j = M; j >= 1; j--) { for (int i = 1; i <= N; i++) { if (grid[i][j-1]) emp[i][j] = emp[i][j+1] + 1; } } for (int j = 1; j <= M; j++) { memset(sg, 0, sizeof(sg)); memset(lazy, -1, sizeof(lazy)); ans = calc(N); for (int i = 1; i <= N; i++) { if (emp[i][j] == 0) split(i); else occ[emp[i][j]].push_back(i); } for (ll q = 1; q <= 2000; q++) { total += ans * q; while (occ[q].size()) { split(occ[q].back()); occ[q].pop_back(); } } } cout << total << "\n"; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...