oj.uz

Submission #552022

# Submission time Handle Problem Language Result Execution time Memory
552022 2022-04-22T08:23:32 Z Aldas25 Nuclearia (CEOI15_nuclearia) C++14
30 / 100
 1000 ms 802940 KB 
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define pb push_back
#define s second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef long double ld;
//mt19937 rng(std::chrono::steady_clock().now().time_since_epoch().count());

const int MAXN = 2500100;

int w, h, n, q;
vector<vl> grid;
vector<vl> pref;
vl tmp;

//ll yk[MAXN], yb[MAXN];
//vector<vl> yk[2], yb[2], xk[2], xb[2];
vector<pair<int, ll>> xk[MAXN][2], xb[MAXN][2];
vector<pair<int, ll>> yk[MAXN][2], yb[MAXN][2];

ll d (ll x1, ll y11, ll x2, ll y2) {
    return max(abs(x1-x2), abs(y11-y2));
}

int getmxD (ll a, ll b) {
    return (a/b);
}

void addPlant (ll x, ll y, ll a, ll b) {
    int mxd = getmxD(a, b);

    int istr0 = h+y-x;
    int istr1 = x+y;

    /// x

    int frx = max((ll)1, x-mxd);
    int tox = min((ll)h, x+mxd);

    /// [frx; x]

    xb[frx][0].pb({istr0, a-b*x});
    xk[frx][0].pb({istr0, b});
    xb[frx][1].pb({istr1+1, -a + b*x});
    xk[frx][1].pb({istr1+1, -b});

    xb[x+1][0].pb({istr0, -a+b*x});
    xk[x+1][0].pb({istr0, -b});
    xb[x+1][1].pb({istr1+1, a - b*x});
    xk[x+1][1].pb({istr1+1, b});

    /// (x; tox]

    xb[x+1][1].pb({istr1, a+b*x});
    xk[x+1][1].pb({istr1, -b});
    xb[x+1][0].pb({istr0+1, -a-b*x});
    xk[x+1][0].pb({istr0+1, b});

    xb[tox+1][1].pb({istr1, -a-b*x});
    xk[tox+1][1].pb({istr1, +b});
    xb[tox+1][0].pb({istr0+1, a+b*x});
    xk[tox+1][0].pb({istr0+1, -b});


    /// y

    istr0 = w+x-y;
    int fry = max((ll)1, y-mxd);
    int toy = min((ll)w, y+mxd);
//cout << " istr0 " << istr0 << " istr1 = " << istr1 << " fry = " << fry << " toy=" << toy << endl;
    /// [y-mxd; y)

    yb[fry][0].pb({istr0+1, a-b*y});
    yk[fry][0].pb({istr0+1, b});
    yb[fry][1].pb({istr1, -a+b*y});
    yk[fry][1].pb({istr1, -b});

    yb[y][0].pb({istr0+1, -a+b*y});
    yk[y][0].pb({istr0+1, -b});
    yb[y][1].pb({istr1, a-b*y});
    yk[y][1].pb({istr1, b});

    /// (y; toy]

    yb[y+1][1].pb({istr1+1, a+b*y});
    yk[y+1][1].pb({istr1+1, -b});
    yb[y+1][0].pb({istr0, -a-b*y});
    yk[y+1][0].pb({istr0, b});

    yb[toy+1][1].pb({istr1+1, -a-b*y});
    yk[toy+1][1].pb({istr1+1, b});
    yb[toy+1][0].pb({istr0, a+b*y});
    yk[toy+1][0].pb({istr0, -b});
}

//ll prefb[2][MAXN], prefk[2][MAXN]; /// prefixes for diagonals
//ll sb[2][MAXN], sk[2][MAXN];

ll fen[2][2][MAXN];
void upd (int id1, int id2, int p, ll x) {
    for (int i = p; i < MAXN; i += i&(-i))
        fen[id1][id2][i] += x;
}
ll get (int id1, int id2, int p) {
    ll ret = 0;
    for (int i = p; i > 0; i -= i&(-i))
        ret += fen[id1][id2][i];
    return ret;
}
ll get(int id1, int id2, int fr, int to) {
    return get(id1, id2, to) - get(id1, id2, fr-1);
}

void calcGrid () {
    /// x

    //FOR(i, 0, w+h+5) FOR(k, 0, 1) prefb[k][i]= prefk[k][i] = 0;
    //FOR(i, 0, w+h+5) FOR(id1, 0, 1) FOR(id2, 0, 1) fen[id1][id2][i] = 0;

    FOR(x, 1, h) {
        //cout << " x = " << x << endl;
        //ll sb = 0, sk = 0;
        FOR(k, 0, 1) {
            for (auto p : xb[x][k]) {
                int id = p.f;
                ll val = p.s;
                //prefb[k][id] += val;
                upd(0, k, id, val);
            }
            for (auto p : xk[x][k]) {
                int id = p.f;
                ll val = p.s;
                //prefk[k][id] += val;
                upd(1, k, id, val);
            }
        }

       /* FOR(istr, 0, w+h+5) {
            //cout << "   istr = " << istr << endl;
            FOR(k, 0, 1) {
                sb[k][istr] = sk[k][istr] = 0;
                if (istr > 0) sb[k][istr] += sb[k][istr-1];
                if (istr > 0) sk[k][istr] += sk[k][istr-1];
                sb[k][istr] += prefb[k][istr];
                sk[k][istr] += prefk[k][istr];

               // cout << "     k = " << k << endl;
             //   cout << "       prefk = " << prefk[k][istr] << " prefb = " << prefb[k][istr] << endl;
           //     cout << "       sk = " << sk[k][istr] << " sb = " << sb[k][istr] << endl;
            }
        }*/

        FOR(y, 1, w) {
            int istr0 = h+y-x;
            int istr1 = x+y;
            //ll cur0 = sb[0][istr0] + sk[0][istr0] * x;
            //ll cur1 = sb[1][istr1] + sk[1][istr1] * x;
            ll cur0 = get(0, 0, istr0) + get(1, 0, istr0) * x;
            ll cur1 = get(0, 1, istr1) + get(1, 1, istr1) * x;
         //   cout << "  x = " << x << " y = " << y << " cur0 = " << cur0 << " cur1 = " << cur1 << endl;
            grid[x][y] += cur0 + cur1;
        }
    }

    /// y

    //FOR(i, 0, w+h+5) FOR(k, 0, 1) prefb[k][i]= prefk[k][i] = 0;
    FOR(i, 0, w+h+5) FOR(id1, 0, 1) FOR(id2, 0, 1) fen[id1][id2][i] = 0;

    FOR(y, 1, w) {
       // cout << " y = " << y << endl;
        //ll sb = 0, sk = 0;
        FOR(k, 0, 1) {
            for (auto p : yb[y][k]) {
                int id = p.f;
                ll val = p.s;
                //prefb[k][id] += val;
                upd(0, k, id, val);
            }
            for (auto p : yk[y][k]) {
                int id = p.f;
                ll val = p.s;
                //prefk[k][id] += val;
                upd(1, k, id, val);
            }
        }

        /*FOR(istr, 0, w+h+5) {
            //cout << "   istr = " << istr << endl;
            FOR(k, 0, 1) {
                sb[k][istr] = sk[k][istr] = 0;
                if (istr > 0) sb[k][istr] += sb[k][istr-1];
                if (istr > 0) sk[k][istr] += sk[k][istr-1];
                sb[k][istr] += prefb[k][istr];
                sk[k][istr] += prefk[k][istr];

                //cout << "     k = " << k << endl;
                //cout << "       prefk = " << prefk[k][istr] << " prefb = " << prefb[k][istr] << endl;
                //cout << "       sk = " << sk[k][istr] << " sb = " << sb[k][istr] << endl;
            }
        }*/

        FOR(x, 1, h) {
            int istr0 = w+x-y;
            int istr1 = x+y;
            //ll cur0 = sb[0][istr0] + sk[0][istr0] * y;
            //ll cur1 = sb[1][istr1] + sk[1][istr1] * y;
            ll cur0 = get(0, 0, istr0) + get(1, 0, istr0) * y;
            ll cur1 = get(0, 1, istr1) + get(1, 1, istr1) * y;
           // cout << "  x = " << x << " y = " << y << " cur0 = " << cur0 << " cur1 = " << cur1 << endl;
            grid[x][y] += cur0 + cur1;
        }
    }
}

void calcPref () {
    FOR(i, 1, h) {
        ll pr = 0;
        FOR(j, 1, w) {
            pref[i][j] += pref[i-1][j];
            pr += grid[i][j];
            pref[i][j] += pr;
        }
    }
}

ll sum (int x1, int y11, int x2, int y2) {
    ll ret = pref[x2][y2];
    ret -= pref[x1-1][y2];
    ret -= pref[x2][y11-1];
    ret += pref[x1-1][y11-1];
    return ret;
}

int main()
{
    FAST_IO;

    cin >> w >> h;

    REP(w+1) tmp.pb(0);
    REP(h+1) {
        grid.pb(tmp);
        pref.pb(tmp);
       // sb.pb(tmp);
       // sk.pb(tmp);
        //FOR(k, 0, 1) {
          //  yb[k].pb(tmp);
           // yk[k].pb(tmp);
            //xb[k].pb(tmp);
            //xk[k].pb(tmp);
        //}
    }
    /*tmp.clear();
    REP(2*h+5) tmp.pb(0);
    REP(2*w+5) {
        //grid.pb(tmp);
        //pref.pb(tmp);
        FOR(k, 0, 1) {
            //yb[k].pb(tmp);
            //yk[k].pb(tmp);
            xb[k].pb(tmp);
            xk[k].pb(tmp);
        }
    }*/

    cin >> n;
    REP(n) {
        int x, y;
        ll a, b;
        cin >> x >> y >> a >> b;
        swap(x, y);
        addPlant (x, y, a, b);
    }

    //cout << " asdas" << endl;

    calcGrid();
    calcPref();

    //FOR(i, 1, h) FOR(j, 1, w) cout << " i = " << i << " j = " << j << " grid = " << grid[i][j]<< " pref = " << pref[i][j] << endl;

    /*cout << " grid:" << endl;
    FOR(i, 1, h) {
        FOR(j, 1, w) cout << grid[i][j] << " ";
        cout << endl;
    }
    cout << " pref:" << endl;
    FOR(i, 1, h) {
        FOR(j, 1, w) cout << pref[i][j] << " ";
        cout << endl;
    }*/

    cin >> q;
    REP(q) {
        int x1, y11, x2, y2;
        cin >> x1 >> y11 >> x2 >> y2;
        swap(x1, y11);
        swap(x2, y2);
        ll s = sum(x1, y11, x2, y2);
        ll sz = ((ll)(x2-x1+1)) * ((ll)(y2-y11+1));
        ll ans = (s+(sz/2))/sz;
        cout << ans << "\n";
       // cout <<endl;
    }

    return 0;
}


/*

4 1
2
1 1 5 1
3 1 8 7

4 1
1
3 1 8 7

*/

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 646268 KB Output is correct
2 Correct 299 ms 474736 KB Output is correct
3 Correct 314 ms 473860 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 590 ms 646264 KB Output is correct
2 Correct 401 ms 474740 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 509840 KB Output is correct
2 Correct 369 ms 473932 KB Output is correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 515 ms 523096 KB Output is correct
2 Correct 300 ms 474808 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 747 ms 652148 KB Output is correct
2 Correct 325 ms 476008 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 546608 KB Output is correct
2 Correct 320 ms 474736 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 513440 KB Output is correct
2 Correct 305 ms 474700 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 519060 KB Output is correct
2 Correct 297 ms 474476 KB Output is correct

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1139 ms 802940 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 1113 ms 799924 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 1120 ms 661976 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 1100 ms 666652 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 1123 ms 638268 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 633080 KB Time limit exceeded
2 Halted 0 ms 0 KB -