oj.uz

답안 #552644

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
552644 2022-04-23T13:25:53 Z Aldas25 Nuclearia (CEOI15_nuclearia) C++14
67 / 100
 1000 ms 643748 KB 
#pragma GCC target ("avx2")
#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 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);
}
 
vector<pair<int, pll>> x0[MAXN], x1[MAXN];
vector<pair<int, pll>> yy0[MAXN], yy1[MAXN];
 
void addPlant (ll x, ll y, ll a, ll b) {
    int mxd = getmxD(a, b);
 
    int istr0, istr1;
 
    /// x
 
    istr0 = h+y-x;
    istr1 = x+y;
    int frx = max(1ll, x-mxd);
    int tox = min((ll)h, x+mxd);
 
    ///  [frx; x], istr0
 
    if (x != (frx-1)) {
        x0[x].pb({istr0, {b, a-b*x}});
        x0[frx-1].pb({istr0, {-b, -a+b*x}});
    }
 
    ///  [frx; x], istr1
 
    if (frx != (x+1)) {
        x1[frx].pb({istr1+1, {-b, -a+b*x}});
        x1[x+1].pb({istr1+1, {b, a-b*x}});
    }
 
    ///  (x; tox], istr0
 
    if (tox != x) {
        x0[tox].pb({istr0+1, {+b, -a-b*x}});
        x0[x].pb({istr0+1, {-b, +a+b*x}});
    }
 
    ///  (x; tox], istr1
 
    if ((x+1) != (tox+1)) {
        x1[x+1].pb({istr1, {-b, a+b*x}});
        x1[tox+1].pb({istr1, {b, -a-b*x}});
    }
 
    /// y
 
    istr0 = w+x-y;
    istr1 = x+y;
    int fry = max(1ll, y-mxd);
    int toy = min((ll)w, y+mxd);
 
    ///   [y-mxd; y), istr0
 
    if ((y-1) != (fry-1)) {
        yy0[y-1].pb({istr0+1, {b, a-b*y}});
        yy0[fry-1].pb({istr0+1, {-b, -a+b*y}});
    }
 
    ///   [y-mxd; y), istr1
 
    if (fry != y) {
        yy1[fry].pb({istr1, {-b, -a+b*y}});
        yy1[y].pb({istr1, {b, a-b*y}});
    }
 
    ///   (y; y+mxd], istr0
 
    if (toy != y) {
        yy0[toy].pb({istr0, {b, -a-b*y}});
        yy0[y].pb({istr0, {-b, a+b*y}});
    }
 
    ///   (y; y+mxd], istr1
 
    if ((y+1) != (toy+1)) {
        yy1[y+1].pb({istr1+1, {-b, a+b*y}});
        yy1[toy+1].pb({istr1+1, {b, -a-b*y}});
    }
}
 
ll prefk[MAXN], prefb[MAXN];
ll sk[MAXN], sb[MAXN];
 
void calcGrid () {
    /// x, istr0
    ///  (x=h -> x=1,  y=1->y=w)
 
    FOR(i, 0, h+w+5) sk[i] = sb[i] = prefk[i] = prefb[i] = 0;
 
    for (int x = h; x > 0; x--) {
 
        int fr = h+1-x;
        int to = h+w-x;
 
       // cout << "X = " << x << " fr = " << fr << endl;
 
       // if (fr-2 >= 0) sk[fr-1] += sk[fr-2];
       // if (fr-2 >= 0) sb[fr-1] += sb[fr-2];
 
        for (auto p : x0[x]) {
            int id = p.f;
            ll k = p.s.f;
            ll b = p.s.s;
            if (id < fr) {
                sk[fr-1] += k;
                sb[fr-1] += b;
            }
            prefb[id]+=b;
            prefk[id]+=k;
        }
 
        FOR(istr, fr, to) {
            sk[istr] = sk[istr-1] + prefk[istr];
            sb[istr] = sb[istr-1] + prefb[istr];
        }
 
        FOR(y, 1, w) {
            int istr = h+y-x;
            ll cur = sk[istr] * x + sb[istr];
           // cout << " (x, istr0) x = " << x <<  " y = " << y << " cur = " << cur << endl;
            grid[x][y] += cur;
        }
    }
 
    /// x, istr1
    ///  (x=1 -> x=h,  y=1->y=w)
 
    FOR(i, 0, h+w+5) sk[i] = sb[i] = prefk[i] = prefb[i] = 0;
 
    for (int x = 1; x <= h; x++) {
 
        int fr = x+1;
        int to = x+w;
 
       // cout << "X = " << x << " fr = " << fr << endl;
 
       // if (fr-2 >= 0) sk[fr-1] += sk[fr-2];
       // if (fr-2 >= 0) sb[fr-1] += sb[fr-2];
 
        for (auto p : x1[x]) {
                //cout <<"      is " << endl;
            int id = p.f;
            ll k = p.s.f;
            ll b = p.s.s;
            if (id < fr) {
                sk[fr-1] += k;
                sb[fr-1] += b;
            }
            prefb[id]+=b;
            prefk[id]+=k;
        }
 
        FOR(istr, fr, to) {
            sk[istr] = sk[istr-1] + prefk[istr];
            sb[istr] = sb[istr-1] + prefb[istr];
           // cout << "   istr=" << istr << " sk = " << sk[istr] << " sb = " << sb[istr] << endl;
        }
 
        FOR(y, 1, w) {
            int istr = x+y;
            ll cur = sk[istr] * x + sb[istr];
           // cout << " (x, istr1) x = " << x <<  " y = " << y << " cur = " << cur << endl;
            grid[x][y] += cur;
        }
    }
 
    /// y, istr0
    ///  (y=w -> y=1,  x=1->x=h)
 
    FOR(i, 0, h+w+5) sk[i] = sb[i] = prefk[i] = prefb[i] = 0;
 
    for (int y = w; y > 0; y--) {
 
        int fr = w+1-y;
        int to = w+h-y;
 
       // cout << "X = " << x << " fr = " << fr << endl;
 
       // if (fr-2 >= 0) sk[fr-1] += sk[fr-2];
       // if (fr-2 >= 0) sb[fr-1] += sb[fr-2];
 
        for (auto p : yy0[y]) {
            int id = p.f;
            ll k = p.s.f;
            ll b = p.s.s;
            if (id < fr) {
                sk[fr-1] += k;
                sb[fr-1] += b;
            }
            prefb[id]+=b;
            prefk[id]+=k;
        }
 
        FOR(istr, fr, to) {
            sk[istr] = sk[istr-1] + prefk[istr];
            sb[istr] = sb[istr-1] + prefb[istr];
        }
 
        FOR(x, 1, h) {
            int istr = w+x-y;
            ll cur = sk[istr] * y + sb[istr];
           // cout << " (x, istr0) x = " << x <<  " y = " << y << " cur = " << cur << endl;
            grid[x][y] += cur;
        }
    }
 
 
    /// y, istr1
    ///  (y=1 -> y=w,  x=1->x=h)
 
    FOR(i, 0, h+w+5) sk[i] = sb[i] = prefk[i] = prefb[i] = 0;
 
    for (int y = 1; y <= w; y++) {
 
        int fr = y+1;
        int to = y+h;
 
       // cout << "X = " << x << " fr = " << fr << endl;
 
       // if (fr-2 >= 0) sk[fr-1] += sk[fr-2];
       // if (fr-2 >= 0) sb[fr-1] += sb[fr-2];
 
        for (auto p : yy1[y]) {
                //cout <<"      is " << endl;
            int id = p.f;
            ll k = p.s.f;
            ll b = p.s.s;
            if (id < fr) {
                sk[fr-1] += k;
                sb[fr-1] += b;
            }
            prefb[id]+=b;
            prefk[id]+=k;
        }
 
        FOR(istr, fr, to) {
            sk[istr] = sk[istr-1] + prefk[istr];
            sb[istr] = sb[istr-1] + prefb[istr];
           // cout << "   istr=" << istr << " sk = " << sk[istr] << " sb = " << sb[istr] << endl;
        }
 
        FOR(x, 1, h) {
            int istr = x+y;
            ll cur = sk[istr] * y + sb[istr];
           // cout << " (x, istr1) x = " << x <<  " y = " << y << " cur = " << cur << endl;
            grid[x][y] += cur;
        }
    }
}
 
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);
    }
 
    cin >> n;
    REP(n) {
        int x, y;
        ll a, b;
        cin >> y >> x >> a >> b;
        //swap(x, y);
        addPlant (x, y, a, b);
    }
 
    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 >> y11 >> x1 >> y2 >> x2;
       // 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
grid:
0 1 8 1
 
4 1
1
1 1 5 1
grid:
5 4 3 2
 
1 4
1
1 3 8 7
grid:
0
1
8
1
 
1 4
1
1 1 5 1
grid:
5
4
3
2
 
4 3
1
3 2 4 2
grid:
0 2 2 2
0 2 4 2
0 2 2 2
 
4 3
1
1 1 7 3
grid:
7 4 1 0
4 4 1 0
1 1 1 0
 
*/

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 334 ms 411428 KB Output is correct
2 Correct 188 ms 237972 KB Output is correct
3 Correct 188 ms 237476 KB Output is correct

Subtask #2
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 287 ms 411480 KB Output is correct
2 Correct 185 ms 238060 KB Output is correct

Subtask #3
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 199 ms 274700 KB Output is correct
2 Correct 181 ms 237944 KB Output is correct

Subtask #4
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 244 ms 288044 KB Output is correct
2 Correct 200 ms 237908 KB Output is correct

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 378 ms 413996 KB Output is correct
2 Correct 195 ms 238496 KB Output is correct

Subtask #6
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 280 ms 308596 KB Output is correct
2 Correct 183 ms 238024 KB Output is correct

Subtask #7
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 332 ms 277740 KB Output is correct
2 Correct 183 ms 238628 KB Output is correct

Subtask #8
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 284 ms 281076 KB Output is correct
2 Correct 193 ms 238036 KB Output is correct

Subtask #9
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1096 ms 487432 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1095 ms 485780 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 476 ms 388264 KB Output is correct
2 Correct 498 ms 389668 KB Output is correct

Subtask #12
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 495 ms 389656 KB Output is correct
2 Correct 489 ms 386872 KB Output is correct

Subtask #13
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 557 ms 369500 KB Output is correct
2 Correct 496 ms 365936 KB Output is correct

Subtask #14
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 506 ms 367368 KB Output is correct
2 Execution timed out 1061 ms 643748 KB Time limit exceeded
3 Halted 0 ms 0 KB -