oj.uz

Submission #110168

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

using namespace std;

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

i64 sum[nmax + 1];
i64 ra[nmax + 1];

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

    if (h != 1) {
        i64 s[w+1][h+1];
        memset(s, 0, sizeof(s));

        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];

        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";
        }
    } 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);
            sum[x] += a;
            sum[pfin + 1] -= a - b * (pfin - x);

            ra[x + 1] += -b;
            ra[pfin + 1] -= -b;

            pfin = max(1, x - a / b);
            if (pfin <= x - 1) {
                sum[pfin] += a - b * (x - pfin);
                sum[x] -= a - b;

                ra[pfin + 1] += b;
                ra[x] -= b;
            }
        }

        for (int i = 1; i <= w; ++ i)
            ra[i] += ra[i - 1];

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

        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);
    }

    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 39416 KB Output is correct
2 Correct 461 ms 2980 KB Output is correct
3 Correct 421 ms 2624 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 39416 KB Output is correct
2 Correct 423 ms 3064 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 19976 KB Output is correct
2 Correct 449 ms 2972 KB Output is correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 20940 KB Output is correct
2 Correct 492 ms 3084 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 675 ms 42088 KB Output is correct
2 Correct 485 ms 3064 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 542 ms 18548 KB Output is correct
2 Correct 422 ms 2920 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 22676 KB Output is correct
2 Correct 423 ms 3292 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 872 ms 14612 KB Output is correct
2 Correct 438 ms 2976 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 812 ms 43268 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 878 ms 43776 KB Output is correct

Subtask #11
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 19968 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 1083 ms 19840 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 1077 ms 19968 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 1075 ms 19968 KB Time limit exceeded
2 Halted 0 ms 0 KB -