oj.uz

Submission #47682

# Submission time Handle Problem Language Result Execution time Memory
47682 2018-05-06T09:16:23 Z maksim_gaponov Cultivation (JOI17_cultivation) C++14
5 / 100
 2000 ms 748 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void openFiles() {
#ifdef KEK
	assert(freopen("input.txt", "r", stdin));
	assert(freopen("output.txt", "w", stdout));
#endif
}

void IOoptimize() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

struct Action {
    int time;
    int l, r;
    int type;
    int id;
};

bool operator< (const Action &a1, const Action &a2) {
    if (a1.time == a2.time)
        return a1.id < a2.id;
    return a1.time < a2.time;
}

struct Segment {
    int val;
    int cnt;
    int add;

    Segment() {}

    Segment(int val, int cnt, int add) : val(val), cnt(cnt), add(add) {}
};

const int MAXN = 300;
const int MAX = 40;
int x[MAXN], y[MAXN];
Segment t[5 * MAX];

Segment merge(const Segment &s1, const Segment &s2) {
    if (s1.val < s2.val)
        return s1;
    if (s2.val < s1.val)
        return s2;
    Segment s3;
    s3.add = 0;
    s3.val = s1.val;
    s3.cnt = s1.cnt + s2.cnt;
    return s3;
}

void push(int x, int l, int r) {
    t[x].val += t[x].add;
    if (r - l > 1) {
        t[2 * x + 1].add += t[x].add;
        t[2 * x + 2].add += t[x].add;
    }
    t[x].add = 0;
}

void update(int x, int l, int r, int ql, int qr, int val) {
    push(x, l, r);
    if (l >= qr || r <= ql)
        return;
    if (ql <= l && r <= qr) {
        t[x].add += val;
        push(x, l, r);
        return;
    }
    int c = (l + r) / 2;
    update(2 * x + 1, l, c, ql, qr, val);
    update(2 * x + 2, c, r, ql, qr, val);
    t[x] = merge(t[2 * x + 1], t[2 * x + 2]);
}

Segment query(int x, int l, int r, int ql, int qr) {
    push(x, l, r);
    if (l >= qr || r <= ql)
        return Segment(INT_MAX, 0, 0);
    if (ql <= l && r <= qr)
        return t[x];
    int c = (l + r) / 2;
    return merge(
                 query(2 * x + 1, l, c, ql, qr),
                 query(2 * x + 2, c, r, ql, qr)
                 );
}

int main() {
	openFiles();
	IOoptimize();
    int r, c;
    cin >> r >> c;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
        x[i]--;
        y[i]--;
    }
    int ans = INT_MAX;
    int cnt[4];
    for (cnt[0] = 0; cnt[0] <= MAX; cnt[0]++)
    for (cnt[1] = 0; cnt[1] <= MAX; cnt[1]++)
    for (cnt[2] = 0; cnt[2] <= MAX; cnt[2]++)
    for (cnt[3] = 0; cnt[3] <= MAX; cnt[3]++) {
        int new_ans = cnt[0] + cnt[1] + cnt[2] + cnt[3];
        if (ans <= new_ans)
            continue;
        vector<Action> v;
        for (int i = 0; i < n; i++) {
            Action act;
            act.id = i;
            act.time = max(y[i] - cnt[1], 0);
            act.l = max(x[i] - cnt[0], 0);
            act.r = min(x[i] + cnt[2], r - 1);
            act.type = 1;
            v.push_back(act);
            act.time = min(y[i] + cnt[3] + 1, c);
            act.type = -1;
            v.push_back(act);
        }
        sort(v.begin(), v.end());
        for (int i = 0; i < 5 * MAX; i++) {
            t[i].val = 0;
            t[i].cnt = 1;
            t[i].add = 0;
        }
        int last = 0;
        int sq = 0;
        for (auto act : v) {
            //cout << act.time << " " << act.l << " " << act.r << " " << act.type << "\n";
            int active_count = 0;
            Segment seg = query(0, 0, r, 0, r);
            if (seg.val == 0) {
                active_count = r - seg.cnt;
            }
            else {
                active_count = r;
            }
            sq += active_count * (act.time - last);
            last = act.time;
            update(0, 0, r, act.l, act.r + 1, act.type);
        }
        //cout << sq << "\n";
        //cout << "--/--\n";
        if (sq == r * c)
            ans = new_ans;
    }
    cout << ans;
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 376 KB Output is correct
2 Correct 48 ms 492 KB Output is correct
3 Correct 14 ms 492 KB Output is correct
4 Correct 13 ms 492 KB Output is correct
5 Correct 16 ms 492 KB Output is correct
6 Correct 118 ms 492 KB Output is correct
7 Correct 17 ms 492 KB Output is correct
8 Correct 17 ms 492 KB Output is correct
9 Correct 123 ms 492 KB Output is correct
10 Correct 60 ms 492 KB Output is correct
11 Correct 12 ms 520 KB Output is correct
12 Correct 12 ms 632 KB Output is correct
13 Correct 17 ms 632 KB Output is correct
14 Correct 56 ms 672 KB Output is correct
15 Correct 60 ms 672 KB Output is correct
16 Correct 115 ms 672 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 376 KB Output is correct
2 Correct 48 ms 492 KB Output is correct
3 Correct 14 ms 492 KB Output is correct
4 Correct 13 ms 492 KB Output is correct
5 Correct 16 ms 492 KB Output is correct
6 Correct 118 ms 492 KB Output is correct
7 Correct 17 ms 492 KB Output is correct
8 Correct 17 ms 492 KB Output is correct
9 Correct 123 ms 492 KB Output is correct
10 Correct 60 ms 492 KB Output is correct
11 Correct 12 ms 520 KB Output is correct
12 Correct 12 ms 632 KB Output is correct
13 Correct 17 ms 632 KB Output is correct
14 Correct 56 ms 672 KB Output is correct
15 Correct 60 ms 672 KB Output is correct
16 Correct 115 ms 672 KB Output is correct
17 Correct 50 ms 672 KB Output is correct
18 Correct 202 ms 720 KB Output is correct
19 Execution timed out 2074 ms 720 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 376 KB Output is correct
2 Correct 48 ms 492 KB Output is correct
3 Correct 14 ms 492 KB Output is correct
4 Correct 13 ms 492 KB Output is correct
5 Correct 16 ms 492 KB Output is correct
6 Correct 118 ms 492 KB Output is correct
7 Correct 17 ms 492 KB Output is correct
8 Correct 17 ms 492 KB Output is correct
9 Correct 123 ms 492 KB Output is correct
10 Correct 60 ms 492 KB Output is correct
11 Correct 12 ms 520 KB Output is correct
12 Correct 12 ms 632 KB Output is correct
13 Correct 17 ms 632 KB Output is correct
14 Correct 56 ms 672 KB Output is correct
15 Correct 60 ms 672 KB Output is correct
16 Correct 115 ms 672 KB Output is correct
17 Correct 50 ms 672 KB Output is correct
18 Correct 202 ms 720 KB Output is correct
19 Execution timed out 2074 ms 720 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 376 KB Output is correct
2 Correct 48 ms 492 KB Output is correct
3 Correct 14 ms 492 KB Output is correct
4 Correct 13 ms 492 KB Output is correct
5 Correct 16 ms 492 KB Output is correct
6 Correct 118 ms 492 KB Output is correct
7 Correct 17 ms 492 KB Output is correct
8 Correct 17 ms 492 KB Output is correct
9 Correct 123 ms 492 KB Output is correct
10 Correct 60 ms 492 KB Output is correct
11 Correct 12 ms 520 KB Output is correct
12 Correct 12 ms 632 KB Output is correct
13 Correct 17 ms 632 KB Output is correct
14 Correct 56 ms 672 KB Output is correct
15 Correct 60 ms 672 KB Output is correct
16 Correct 115 ms 672 KB Output is correct
17 Correct 50 ms 672 KB Output is correct
18 Correct 202 ms 720 KB Output is correct
19 Execution timed out 2074 ms 720 KB Time limit exceeded
20 Halted 0 ms 0 KB -