oj.uz

Submission #1022262

# Submission time Handle Problem Language Result Execution time Memory
1022262 2024-07-13T11:43:37 Z vjudge1 Nuclearia (CEOI15_nuclearia) C++17
30 / 100
 1000 ms 61152 KB 
#include <iostream>
//#include <bits/stdc++.h>
#include <iomanip>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<ll> vi;
typedef vector<bool> vb;
const ll mm = 1000000007;
const int maxn = 2e5 + 1;

ll near(ll a, ll b) {
    double a1 = a, b1 = b;
    double d = a1 / b1;
    if (d - floor(d) < 0.5) {
        return floor(d);
    }
    else return ceil(d);
}


int main() {                           
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    ll w, h; cin >> w >> h;            //radimo sucaj h=1
    vector<vi> p(h, vi(w));
    ll n; cin >> n;
    ll xn, yn, a, b;
    for (int i = 0; i < n; i++) {
        cin >> xn >> yn >> a >> b;
        --yn, --xn;
        //box
        //p[yn][xn] = 1;
        ll maxd = (a / b);
        //cout << "maxd: " << maxd << endl;
        ll dis, xc = xn - maxd, yc = yn - maxd;
        for (xc; xc <= xn + maxd; xc++) {
            //cout << "xc: " << xc << endl;
            if (xc < 0) xc=-1;
            else if (xc > w - 1) xc = xn + maxd + 1;
            else {
                for (yc; yc <= yn + maxd; yc++) {
                    //cout << "yc: " << yc << endl;
                    if (yc < 0) yc=-1;
                    else if (yc > h - 1) yc = yn + maxd + 1;
                    else {
                        dis = max(abs(xc - xn), abs(yc - yn));
                        ll k = a - b * dis;
                        if (k < 0) k = 0;
                        p[yc][xc] += k;
                    }
                }
                yc = yn - maxd;
            }
        }
        /*
        cout << "tabelaa:" << endl;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cout << p[i][j] << " ";
            }
            cout << endl;
        }
        cout << endl;
        */
    }

    vector<vi> dp(h, vi(w));

    dp[0][0] = p[0][0];

    for (int j = 1; j < w; j++) {
        dp[0][j] = p[0][j] + dp[0][j - 1];
    }

    for (int i = 1; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (j == 0) {
                dp[i][j] = p[i][j] + dp[i - 1][j];
            }
            else {
                dp[i][j] = p[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
            }
        }
    }

    /*
    cout << "dp tabelaa:" << endl;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }*/



    ll q; cin >> q;
    while (q--) {
        ll x1, x2, y1, y2; cin >> x1 >> y1 >> x2 >> y2;
        x1--; x2--; y1--; y2--;
        ll A = (y2 - y1 + 1) * (x2 - x1 + 1);
        ll S = 0;
        S += dp[y2][x2];
        if (x1 > 0 and y1 > 0) {
            S -= dp[y2][x1 - 1];
            S -= dp[y1 - 1][x2];
            S += dp[y1 - 1][x1 - 1];
        }
        else if (x1 == 0 and y1 == 0) {

        }
        else if (x1 == 0) {
            S -= dp[y1 - 1][x2];
        }
        else if (y1 == 0) {
            S -= dp[y2][x1 - 1];
        }

        //cout << "SiA: " << S << " i " << A << endl;
        cout << near(S, A) << endl;


    }


    return 0;

}

Compilation message

nuclearia.cpp: In function 'int main()':
nuclearia.cpp:46:14: warning: statement has no effect [-Wunused-value]
   46 |         for (xc; xc <= xn + maxd; xc++) {
      |              ^~
nuclearia.cpp:51:22: warning: statement has no effect [-Wunused-value]
   51 |                 for (yc; yc <= yn + maxd; yc++) {
      |                      ^~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 580 ms 58924 KB Output is correct
2 Correct 235 ms 2644 KB Output is correct
3 Correct 248 ms 2516 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 522 ms 59104 KB Output is correct
2 Correct 243 ms 2900 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 39504 KB Output is correct
2 Correct 234 ms 2640 KB Output is correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 49224 KB Output is correct
2 Correct 246 ms 2648 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 61152 KB Output is correct
2 Correct 239 ms 2896 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 783 ms 26208 KB Output is correct
2 Correct 252 ms 2640 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 42324 KB Output is correct
2 Correct 242 ms 2896 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 597 ms 22276 KB Output is correct
2 Correct 281 ms 2844 KB Output is correct

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 39512 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 1095 ms 39512 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 1064 ms 20060 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 1078 ms 20036 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 1062 ms 20572 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 1037 ms 20060 KB Time limit exceeded
2 Halted 0 ms 0 KB -