Submission #82294

#	Time	Username	Problem	Language	Result	Execution time	Memory
82294		Milki	Strah (COCI18_strah)	C++14	110 / 110	745 ms	84524 KiB

strah

#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)

typedef long long ll;
typedef pair<int, int> point;

const int MAXN = 2e3 + 5, INF = 1e9, off = 1 << 11;

int n, m;
char c[MAXN][MAXN];
int down[MAXN][MAXN];

struct Tournament{
    point t[2 * off];

    point merge(point a, point b){
        if(a.first > b.first) swap(a, b);
        if(a.first == b.first) return point(a.first, min(a.second, b.second));
        return a;
    }

    void add(int x, int val){
        t[x + off] = point(val, x);
    }

    void build(){
        for(int i = off - 1; i > 0; --i)
            t[i] = merge(t[i * 2], t[i * 2 + 1]);
    }

    point get(int x, int lo, int hi, int a, int b){
        if(hi <= a || lo >= b) return point(INF, -1);
        if(lo >= a && hi <= b) return t[x];

        int mid = (lo + hi) >> 1;
        point X = get(x * 2, lo, mid, a, b);
        point Y = get(x * 2 + 1, mid, hi, a, b);
        return merge(X, Y);
    }
} T[MAXN];

ll sol;

ll calc(ll x, ll y){
    return ((y * (y + 1)) / 2) * (x * (x + 1) * (x + 2) / 6);
}

void solve(int l, int r, int curr, int last){
    if(l > r) return;
    point x = T[curr].get(1, 0, off, l, r + 1);
    ll add = calc(r - l + 1, last);
    sol += calc(r - l + 1, x.first) - add;

    if(l == r) return;
    solve(l, x.second - 1, curr, x.first);
    solve(x.second + 1, r, curr, x.first);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> n >> m;
    REP(i, n)
        REP(j, m)
            cin >> c[i][j];

    for(int i = n - 1; i >= 0; --i)
        REP(j, m){
            if(c[i][j] == '#')
                down[i][j] = 0;
            else
                down[i][j] = down[i + 1][j] + 1;
            T[i].add(j, down[i][j]);
        }
    REP(i, n)
        T[i].build();

    REP(i, n){
        solve(0, m - 1, i, 0);
    }

    cout << sol;
}

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