oj.uz

Submission #948958

# Submission time Handle Problem Language Result Execution time Memory
948958 2024-03-18T17:28:28 Z fskarica Nuclearia (CEOI15_nuclearia) C++14
30 / 100
 1000 ms 550444 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fi first
#define se second
#define pii pair<ll, ll>

ll n, m;
ll x, y, a, b;
ll sirina, x2, y2, a2;
ll q, p;
vector <vector<ll>> kvadrat;
vector <vector<ll>> trokut;
vector <vector<ll>> trokut2;
vector <ll> bla;
ll zbr, sol, cnt;

bool granice(int x, int y) {
    if (1 <= x && x <= n && 1 <= y && y <= m) return true;
    return false;
}

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

    cin >> n >> m;

    vector<vector<ll>> mat(n + 2, vector<ll>(m + 2));
    vector<vector<ll>> kvadrat(n + 2, vector<ll>(m + 2));
    vector<vector<ll>> trokut(n + 2, vector<ll>(m + 2));
    vector<vector<ll>> trokut2(n + 2, vector<ll>(m + 2));

    cin >> p;
    for (int i = 0; i < p; i++) {
        cin >> x >> y >> a >> b;

        x2 = x;
        y2 = y;
        a2 = a;

        mat[x][y] += a;

        sirina = 1;
        while (a > 0 && granice(x, 1)) {
            trokut[x][max(1ll, y)] += a;
            trokut[x][max(1ll, min(m + 1, y + sirina))] -= a;

            x--;
            y--;
            sirina += 2;
            a -= b;
        }

        x = x2;
        y = y2;
        a = a2;
        sirina = 1;
        while (a > 0 && granice(x, 1)) {
            trokut[x][max(1ll, y)] += a;
            trokut[x][max(1ll, min(m + 1, y + sirina))] -= a;

            x++;
            y--;
            sirina += 2;
            a -= b;
        }

        x = x2;
        y = y2;
        a = a2;
        sirina = 1;
        while (a > 0 && granice(1, y)) {
            trokut2[max(1ll, min(n + 1, x + 1))][y] += a;
            trokut2[max(1ll, min(n + 1, x + sirina - 1))][y] -= a;

            x--;
            y++;
            sirina += 2;
            a -= b;
        }

        x = x2;
        y = y2;
        a = a2;
        sirina = 1;
        while (a > 0 && granice(1, y)) {
            trokut2[max(1ll, min(n + 1, x + 1))][y] += a;
            trokut2[max(1ll, min(n + 1, x + sirina - 1))][y] -= a;

            x--;
            y--;
            sirina += 2;
            a -= b;
        }
    }

    for (int i = 1; i <= n; i++) {
        zbr = 0;

        for (int j = 1; j <= m; j++) {
            zbr += trokut[i][j];
            mat[i][j] += zbr;
        }
    }

    for (int j = 1; j <= m; j++) {
        zbr = 0;

        for (int i = 1; i <= n; i++) {
            zbr += trokut2[i][j];
            mat[i][j] += zbr;
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            kvadrat[i][j] = kvadrat[i - 1][j] + kvadrat[i][j - 1] - kvadrat[i - 1][j - 1] + mat[i][j];
        }
    }

    cin >> q;
    while (q--) {
        cin >> x >> y >> x2 >> y2;

        sol = kvadrat[x2][y2] - kvadrat[x2][y - 1] - kvadrat[x - 1][y2] + kvadrat[x - 1][y - 1];
        cnt = ((x2 - x + 1) * (y2 - y + 1));

        if (sol % cnt >= (cnt + 1) / 2) sol = sol / ((x2 - x + 1) * (y2 - y + 1)) + 1;
        else sol = sol / ((x2 - x + 1) * (y2 - y + 1));

        cout << sol << "\n";
    }

    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 908 ms 548272 KB Output is correct
2 Correct 56 ms 4664 KB Output is correct
3 Correct 45 ms 3892 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 868 ms 548544 KB Output is correct
2 Correct 47 ms 2644 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 79696 KB Output is correct
2 Correct 47 ms 2736 KB Output is correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 87416 KB Output is correct
2 Correct 48 ms 2668 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 671 ms 550444 KB Output is correct
2 Correct 54 ms 3152 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 694 ms 221940 KB Output is correct
2 Correct 51 ms 2816 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 81492 KB Output is correct
2 Correct 51 ms 2932 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 143880 KB Output is correct
2 Correct 49 ms 2728 KB Output is correct

Subtask #9
0 / 15.0

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

Subtask #10
0 / 10.0

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

Subtask #11
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1027 ms 79964 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 1032 ms 79192 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 1026 ms 80560 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 1053 ms 79616 KB Time limit exceeded
2 Halted 0 ms 0 KB -