oj.uz

Submission #328420

# Submission time Handle Problem Language Result Execution time Memory
328420 2020-11-16T13:06:11 Z dolphingarlic Nafta (COI15_nafta) C++14
34 / 100
 1000 ms 20544 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int n, m;
char grid[2001][2001];
bool visited[2001][2001];
int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};
int dp[2001], segtree[8001], lazy[8001];

bool inside(int x, int y) {
    return x && y && x <= n && y <= m && !visited[x][y] && grid[x][y] != '.';
}

tuple<int, int, int> get_oil(int x, int y) {
    tuple<int, int, int> ret = {y, y, grid[x][y] - '0'};
    visited[x][y] = true;
    for (int i = 0; i < 4; i++) if (inside(x + dx[i], y + dy[i])) {
        tuple<int, int, int> pot = get_oil(x + dx[i], y + dy[i]);
        get<0>(ret) = min(get<0>(ret), get<0>(pot));
        get<1>(ret) = max(get<1>(ret), get<1>(pot));
        get<2>(ret) += get<2>(pot);
    }
    return ret;
}

void push_lazy(int node, int l, int r) {
    segtree[node] += lazy[node];
    if (l != r) {
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
    }
    lazy[node] = 0;
}

void build(int node = 1, int l = 0, int r = m) {
    lazy[node] = 0;
    if (l == r) segtree[node] = dp[l];
    else {
        int mid = (l + r) / 2;
        build(node * 2, l, mid);
        build(node * 2 + 1, mid + 1, r);
        segtree[node] = max(segtree[node * 2], segtree[node * 2 + 1]);
    }
}

int query(int pos, int node = 1, int l = 0, int r = m) {
    push_lazy(node, l, r);
    if (l > pos) return 0;
    if (r <= pos) return segtree[node];
    int mid = (l + r) / 2;
    return max(query(pos, node * 2, l, mid), query(pos, node * 2 + 1, mid + 1, r));
}

void update(int pos, int val, int node = 1, int l = 0, int r = m) {
    push_lazy(node, l, r);
    if (l > pos) return;
    if (r <= pos) {
        lazy[node] = val;
        push_lazy(node, l, r);
    } else {
        int mid = (l + r) / 2;
        update(pos, val, node * 2, l, mid);
        update(pos, val, node * 2 + 1, mid + 1, r);
        segtree[node] = max(segtree[node * 2], segtree[node * 2 + 1]);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
        cin >> grid[i][j];
    }
    vector<tuple<int, int, int>> oil;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
        if (inside(i, j)) {
            int l, r, val;
            tie(l, r, val) = get_oil(i, j);
            oil.push_back({l, l, val});
            oil.push_back({r + 1, l, -val});
        }
    }
    sort(oil.begin(), oil.end());

    for (int _ = 1; _ <= m; _++) {
        for (int i = 1, ptr = 0; i <= m; i++) {
            while (get<0>(oil[ptr]) <= i) {
                update(get<1>(oil[ptr]) - 1, get<2>(oil[ptr]));
                ptr++;
            }
            dp[i] = query(i - 1);
        }
        build();
        cout << query(m) << '\n';
    }
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 620 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 4 ms 620 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 620 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 4 ms 620 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 938 ms 1896 KB Output is correct
8 Correct 495 ms 1856 KB Output is correct
9 Correct 71 ms 3692 KB Output is correct
10 Correct 600 ms 1836 KB Output is correct
11 Correct 181 ms 1644 KB Output is correct
12 Correct 69 ms 1644 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 620 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 4 ms 620 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 938 ms 1896 KB Output is correct
8 Correct 495 ms 1856 KB Output is correct
9 Correct 71 ms 3692 KB Output is correct
10 Correct 600 ms 1836 KB Output is correct
11 Correct 181 ms 1644 KB Output is correct
12 Correct 69 ms 1644 KB Output is correct
13 Execution timed out 1097 ms 20544 KB Time limit exceeded
14 Halted 0 ms 0 KB -