Submission #1143040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143040		Perl32	Bob (COCI14_bob)	C++20	120 / 120	178 ms	524 KiB

bob

//I wrote this code 4 u <3
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

template<typename T> using normal_queue = priority_queue<T, vector<T>, greater<T>>;

struct Info {
    int pref = 0, suf = 0;
    bool all = 0;
    ll ans = 0;

    Info() = default;
    Info(int v) {
        ans = pref = suf = all = v;
    }
};

Info operator+(const Info& a, const Info& b) {
    Info res;
    res.all = a.all & b.all;
    res.ans = a.ans + b.ans + a.suf * b.pref;
    if (a.all) res.pref = a.pref + b.pref;
    else res.pref = a.pref;
    if (b.all) res.suf = b.suf + a.suf;
    else res.suf = b.suf;
    return res;
}

struct ST {
    vector<Info> t;
    int sz;

    void pull(int x) {
        t[x] = t[x << 1] + t[x << 1 | 1];
    }

    ST(int n) {
        sz = 1;
        while (sz < n) sz <<= 1;
        t.resize(sz << 1);
    }

    void upd(int i, Info v) {
        i += sz;
        t[i] = v;
        i >>= 1;
        while (i) {
            pull(i);
            i >>= 1;
        }
    }

    ll get() { return t[1].ans; }

    void dbg() {
        for (int i = 1; i < (sz << 1); ++i) cout << t[i].ans << ' ';
        cout << '\n';
    }
};

signed main(int32_t argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    ST tt(m);
    ll ans = 0ll;
    vector<int> pre(m, -1), cur(m), lvl(m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> cur[j];
            if (pre[j] == cur[j]) lvl[j]++;
            else lvl[j] = 1;
        }
        for (int l = 0; l < m;) {
            vector<int> srt;
            normal_queue<pair<int, int>> pq;
            auto add = [&](int id) {
                tt.upd(id, Info(1));
                srt.push_back(lvl[id]);
                pq.push({lvl[id], id});
            };
            int r = l + 1;
            add(l);
            while (r < m && cur[r] == cur[r - 1]) add(r++);
            sort(srt.begin(), srt.end());
            srt.resize(unique(srt.begin(), srt.end()) - srt.begin());
            srt.push_back(srt.back() + 1);
            int lst = 1;
            for (int j = 0; j < (int) srt.size(); ++j) {
                while (!pq.empty() && pq.top().first < srt[j]) {
                    auto id = pq.top().second; pq.pop();
                    tt.upd(id, Info(0));
                }
                if (j + 1 < (int) srt.size()) ans += (srt[j] - lst + 1) * tt.get();
                lst = srt[j] + 1;
            }
            l = r;
        }
        swap(pre, cur);
    }
    cout << ans;
}

/*

 */

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12