oj.uz

Submission #110160

# Submission time Handle Problem Language Result Execution time Memory
110160 2019-05-09T17:20:14 Z naoai Nuclearia (CEOI15_nuclearia) C++14
26 / 100
 1000 ms 153628 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long i64;
const int nmax = 25e5;

i64 **s;

i64 sum[nmax + 1];

struct aintnod {
    i64 s, r;
} aint[4 * nmax + 1];

void update (int nod, int x, int y, int st, int dr, i64 a, i64 b) {
    if (st <= x && y <= dr) {
        aint[nod].s += a + (x - st) * b;
        aint[nod].r += b;
        return ;
    }

    int mij = (x + y) / 2;
    if (st <= mij)
        update(2 * nod, x, mij, st, dr, a, b);
    if (mij < dr)
        update(2 * nod + 1, mij + 1, y, st, dr, a, b);
}

void build (int nod, int x, int y) {
    if (x == y) {
        sum[x] = aint[nod].s;
        return ;
    }

    int mij = (x + y) / 2;

    update(2 * nod, x, mij, x, mij, aint[nod].s, aint[nod].r);
    update(2 * nod + 1, mij + 1, y, mij + 1, y, aint[nod].s + aint[nod].r * (mij + 1 - x), aint[nod].r);

    build(2 * nod, x, mij);
    build(2 * nod + 1, mij + 1, y);
}

int main () {
    int w, h, n;
    cin >> w >> h >> n;

    if (h != 1) {
        s = new i64*[w + 1];
        for (int i = 0; i <= w; ++ i)
            s[i] = new i64[h + 1]();

        for (int i = 0; i <= w; ++ i)
            for (int j = 0; j <= h; ++ j)
                assert(s[i][j] == 0);

        for (int i = 1; i <= n; ++ i) {
            int x, y, a, b;
            cin >> x >> y >> a >> b;

            for (int j = 1; j <= w; ++ j)
                for (int k = 1; k <= h; ++ k) {
                    int c = max(0LL, a - 1LL * b * max(abs(x - j), abs(y - k)));
                    s[j][k] += c;
                }
        }

        for (int i = 1; i <= w; ++ i)
            for (int j = 1; j <= h; ++ j)
                s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

    } else if (h == 1) {
        for (int i = 1; i <= n; ++ i) {
            int x, y, a, b;
            cin >> x >> y >> a >> b;

            int pfin = min(w, x + a / b);
            update(1, 1, w, x, pfin, a, -b);

            pfin = max(1, x - a / b);
            if (pfin <= x - 1)
                update(1, 1, w, pfin, x - 1, a - b * (x - pfin), b);
        }

        build(1, 1, w);
        for (int i = 1; i <= w; ++ i)
            sum[i] += sum[i - 1];

        int q;
        cin >> q;
        for (int i = 1; i <= q; ++ i) {
            int a, b, x, y;
            cin >> a >> b >> x >> y;

            i64 total = sum[x] - sum[a - 1];
            i64 arie = (x - a + 1);
            i64 r = total / arie;
            if (total % arie >= (arie + 1) / 2) ++ r;

            cout << r << "\n";
        }
        exit(0);
    }

    int q;
    cin >> q;
    for (int i = 1; i <= q; ++ i) {
        int a, b, x, y;
        cin >> a >> b >> x >> y;

        i64 total = s[x][y] - s[a - 1][y] - s[x][b - 1] + s[a - 1][b - 1];
        i64 arie = (x - a + 1) * (y - b + 1);
        i64 r = total / arie;
        if (total % arie >= (arie + 1) / 2) ++ r;

        cout << r << "\n";
    }
    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 151416 KB Output is correct
2 Correct 476 ms 2692 KB Output is correct
3 Correct 431 ms 2480 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 151192 KB Output is correct
2 Correct 477 ms 2816 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 20088 KB Output is correct
2 Correct 427 ms 3192 KB Output is correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 21096 KB Output is correct
2 Correct 500 ms 2936 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 679 ms 153628 KB Output is correct
2 Correct 443 ms 2980 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 575 ms 43572 KB Output is correct
2 Correct 489 ms 2732 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 810 ms 22588 KB Output is correct
2 Correct 468 ms 3296 KB Output is correct

Subtask #8
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1030 ms 22384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 152356 KB Time limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 152628 KB Time limit exceeded

Subtask #11
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 20096 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 19968 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1052 ms 20480 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 19968 KB Time limit exceeded
2 Halted 0 ms 0 KB -