Submission #694972

#TimeUsernameProblemLanguageResultExecution timeMemory
694972Nhoksocqt1Bob (COCI14_bob)C++17
120 / 120
605 ms17816 KiB
#include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #define fi first #define se second typedef long long ll; typedef pair<int, int> ii; template<class X, class Y> inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);} template<class X, class Y> inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int Random(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); } int readInt() { bool minus = false; int result = 0; char ch; ch = getchar(); while(true) { if(ch == '-') break; if(ch >= '0' && ch <= '9') break; ch = getchar(); } if(ch == '-') minus = true; else result = ch - '0'; while(true) { ch = getchar(); if (ch < '0' || ch > '9') break; result = result * 10 + (ch - '0'); } if(minus) return -result; else return result; } const int MAXN = 1003; vector<int> adj1[MAXN], adj2[MAXN], tmp1[MAXN], tmp2[MAXN]; int val[MAXN][MAXN], it1[MAXN], it2[MAXN], row, col; inline int C2(int n) { return n * (n + 1) / 2; } void process() { cin >> row >> col; for (int i = 1; i <= row; ++i) { for (int j = 1; j <= col; ++j) { cin >> val[i][j]; if(i > 1 && val[i][j] != val[i - 1][j]) adj1[i].push_back(j); if(j > 1 && val[i][j] != val[i][j - 1]) adj2[i].push_back(j); } } ll res(0); for (int l = 1; l <= col; ++l) { for (int r = l; r <= col; ++r) tmp1[r].clear(), tmp2[r].clear(); for (int i = 1; i <= row; ++i) { while(it1[i] < int(adj1[i].size()) && adj1[i][it1[i]] < l) ++it1[i]; if(it1[i] < int(adj1[i].size())) tmp1[adj1[i][it1[i]]].push_back(i); } for (int i = 1; i <= row; ++i) { while(it2[i] < int(adj2[i].size()) && adj2[i][it2[i]] <= l) ++it2[i]; if(it2[i] < int(adj2[i].size())) tmp2[adj2[i][it2[i]]].push_back(i); } set<ii> line; set<int> sz; int cnt = C2(row); line.insert(ii(row, 1)); sz.insert(row); for (int r = l; r <= col; ++r) { for (int jt = 0; jt < int(tmp1[r].size()); ++jt) { int x(tmp1[r][jt]); auto it = line.lower_bound(ii(x, 1)); if(it == line.end() || it->se >= x) continue; ii tmp = *it; line.erase(it); sz.erase(tmp.fi - tmp.se + 1); cnt -= C2(tmp.fi - tmp.se + 1); line.insert(ii(tmp.fi, x)); line.insert(ii(x - 1, tmp.se)); sz.insert(tmp.fi - x + 1); sz.insert(x - tmp.se); cnt += C2(x - tmp.se) + C2(tmp.fi - x + 1); } for (int jt = 0; jt < int(tmp2[r].size()); ++jt) { int x(tmp2[r][jt]); auto it = line.lower_bound(ii(x, 1)); if(it == line.end() || it->se > x) continue; ii tmp = *it; line.erase(it); sz.erase(tmp.fi - tmp.se + 1); cnt -= C2(tmp.fi - tmp.se + 1); if(tmp.se < x) { line.insert({x - 1, tmp.se}); sz.insert(x - tmp.se); cnt += C2(x - tmp.se); } if(tmp.fi > x) { line.insert({tmp.fi, x + 1}); sz.insert(tmp.fi - x); cnt += C2(tmp.fi - x); } } res += cnt; } } cout << res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("bob.inp", "r", stdin); // freopen("bob.out", "w", stdout); process(); return 0; }

Compilation message (stderr)

bob.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
bob.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      |
#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...