제출 #142544

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
142544		lyc	Nuclearia (CEOI15_nuclearia)	C++14	0 / 100	1107 ms	776712 KiB

nuclearia

//#define DEBUG
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int MAXN = 2e5+5;

int W,H,N,Q;
bool flag;
struct Plant { int x, y, a, b; };
struct Data { ll ldmx, ldmy, ldc, rdmx, rdmy, rdc, rmx, rmy, rc, cmx, cmy, cc, v; };

#ifdef DEBUG
    #define DBG(...) __VA_ARGS__
#else
    #define DBG(...)
#endif

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> W >> H;
    cin >> N; Plant plant[N]; FOR(i,0,N-1) { int x,y,a,b; cin >> x >> y >> a >> b; plant[i] = {x,y,a,b}; }

    Data g[W+2][H+2]; memset(g, 0, sizeof g);
    for (Plant p : plant) {
        int r = (p.a+p.b-1)/p.b - 1;
        // i: [1 to r] :: [y-r, y-i-1], [y-i,y+i], [y+i+1,y+r]

        //p.a - (p.y-y)*p.b
        //= y*p.b - p.y*p.b + p.a
        // u
        g[max(1,p.x-r)][max(1,p.y-r)].rmy += p.b;
        g[max(1,p.x-r)][max(1,p.y-r)].rc  += - p.y*p.b + p.a;
        g[min(W,p.x+r)+1][max(1,p.y-r)].rmy -= p.b;
        g[min(W,p.x+r)+1][max(1,p.y-r)].rc  -= - p.y*p.b + p.a;

        //p.a - (y-p.y)*p.b
        //= y*(-p.b) + p.y*p.b + p.a
        // d
        g[max(1,p.x-r)][min(H,p.y+r)+1].rmy -= - p.b;
        g[max(1,p.x-r)][min(H,p.y+r)+1].rc  -= p.y*p.b + p.a;
        g[min(W,p.x+r)+1][min(H,p.y+r)+1].rmy += - p.b;
        g[min(W,p.x+r)+1][min(H,p.y+r)+1].rc  += p.y*p.b + p.a;

        int x,y;
        //p.a - (p.x-x)*p.b
        //= x*p.b - p.x*p.b + p.a
        // ld
        x = p.x-r, y = p.y-r;
        if (x < 1 or y < 1) {
            int z = max(1-x, 1-y);
            int xp = x+z, yp = y+z;

            g[max(1,x)][yp].rmy -= p.b;
            g[max(1,x)][yp].rc  -= - p.y*p.b + p.a;
            g[xp][yp].rmy += p.b;
            g[xp][yp].rc  += - p.y*p.b + p.a;

            g[max(1,x)][yp].rmx += p.b;
            g[max(1,x)][yp].rc  += - p.x*p.b + p.a;
            g[xp][yp].rmx -= p.b;
            g[xp][yp].rc  -= - p.x*p.b + p.a;

            x = xp, y = yp;
        }
        g[x][y].ldmy -= p.b;
        g[x][y].ldc  -= - p.y*p.b + p.a;
        g[p.x][p.y].ldmy += p.b;
        g[p.x][p.y].ldc  += - p.y*p.b + p.a;

        g[x][y].ldmx += p.b;
        g[x][y].ldc  += - p.x*p.b + p.a;
        g[p.x][p.y].ldmx -= p.b;
        g[p.x][p.y].ldc  -= - p.x*p.b + p.a;

        //
        g[p.x][p.y].ldmy += - p.b;
        g[p.x][p.y].ldc  += p.y*p.b + p.a;

        g[p.x][p.y].ldmx -= - p.b;
        g[p.x][p.y].ldc  -= p.x*p.b + p.a;
        x = p.x+r, y = p.y+r;
        if (x > W or y > H) {
            int z = max(x-W, y-H);
            int xp = x-z, yp = y-z;

            g[xp+1][yp].rmy += - p.b;
            g[xp+1][yp].rc  += p.y*p.b + p.a;
            g[min(W,x)+1][yp].rmy -= - p.b;
            g[min(W,x)+1][yp].rc  -= p.y*p.b + p.a;

            g[xp][yp].rmx -= - p.b;
            g[xp][yp].rc  -= p.x*p.b + p.a;
            g[min(W,x)+1][yp].rmx += - p.b;
            g[min(W,x)+1][yp].rc  += p.x*p.b + p.a;

            x = xp, y = yp;
        }
        g[x+1][y+1].ldmy -= - p.b;
        g[x+1][y+1].ldc  -= p.y*p.b + p.a;

        g[x+1][y+1].ldmx += - p.b;
        g[x+1][y+1].ldc  += p.x*p.b + p.a;
        
        // rd
        x = p.x-r, y = p.y+r;
        DBG(cout << "UPDATE " << x << " " << y << " TO " << p.x << " " << p.y << endl;)
        if (x < 1 or y > H) {
            int z = max(1-x, y-H);
            int xp = x+z, yp = y-z;

            DBG(cout << " CONVERT X Y TO P " << xp << " " << yp << endl;)
            g[max(1,x)][yp].rmy += - p.b;
            g[max(1,x)][yp].rc  += p.y*p.b + p.a;
            g[xp][yp].rmy -= - p.b;
            g[xp][yp].rc  -= p.y*p.b + p.a;

            g[max(1,x)][yp].rmx -= p.b;
            g[max(1,x)][yp].rc  -= - p.x*p.b + p.a;
            g[xp][yp].rmx += p.b;
            g[xp][yp].rc  += - p.x*p.b + p.a;

            x = xp, y = yp;
        }
        g[x][y].rdmy += - p.b;
        g[x][y].rdc  += p.y*p.b + p.a;
        g[p.x][p.y].rdmy -= - p.b;
        g[p.x][p.y].rdc  -= p.y*p.b + p.a;

        g[x][y].rdmx -= p.b;
        g[x][y].rdc  -= - p.x*p.b + p.a;
        g[p.x][p.y].rdmx += p.b;
        g[p.x][p.y].rdc  += - p.x*p.b + p.a;

        //
        g[p.x][p.y].rdmy -= p.b;
        g[p.x][p.y].rdc  -= - p.y*p.b + p.a;

        g[p.x][p.y].rdmx += - p.b;
        g[p.x][p.y].rdc  += p.x*p.b + p.a;
        x = p.x+r, y = p.y-r;
        DBG(cout << "UPDATE " << p.x << " " << p.y << " TO " << x << " " << y << endl;)
        if (x > W or y < 1) {
            int z = max(x-W, 1-y);
            int xp = x-z, yp = y+z;

            DBG(cout << " CONVERT X Y TO P " << xp << " " << yp << endl;)
            DBG(cout << " RANGE " << xp+1 << " TO " << min(W,x)+1 << " AT " << yp << endl;)
            g[xp+1][yp].rmy -= p.b;
            g[xp+1][yp].rc  -= - p.y*p.b + p.a;
            g[min(W,x)+1][yp].rmy += p.b;
            g[min(W,x)+1][yp].rc  += - p.y*p.b + p.a;

            g[xp+1][yp].rmx += - p.b;
            g[xp+1][yp].rc  += p.x*p.b + p.a;
            g[min(W,x)+1][yp].rmx -= - p.b;
            g[min(W,x)+1][yp].rc  -= p.x*p.b + p.a;

            x = xp, y = yp;
        }
        DBG(cout << " MAIN " << x+1 << " " << y-1 << endl;)
        g[x+1][y-1].rdmy += p.b;
        g[x+1][y-1].rdc  += - p.y*p.b + p.a;

        g[x+1][y-1].rdmx -= - p.b;
        g[x+1][y-1].rdc  -= p.x*p.b + p.a;
        //break;
    }

    FOR(x,1,W) FOR(y,1,H) {
        g[x][y].rmx += g[x-1][y].rmx;
        g[x][y].rmy += g[x-1][y].rmy;
        g[x][y].rc  += g[x-1][y].rc;

        g[x][y].ldmx += g[x-1][y-1].ldmx;
        g[x][y].ldmy += g[x-1][y-1].ldmy;
        g[x][y].ldc  += g[x-1][y-1].ldc;

        g[x][y].rdmx += g[x-1][y+1].rdmx;
        g[x][y].rdmy += g[x-1][y+1].rdmy;
        g[x][y].rdc  += g[x-1][y+1].rdc;

        g[x][y].cmx = g[x][y-1].cmx + g[x][y].ldmx + g[x][y].rdmx + g[x][y].rmx;
        g[x][y].cmy = g[x][y-1].cmy + g[x][y].ldmy + g[x][y].rdmy + g[x][y].rmy;
        g[x][y].cc  = g[x][y-1].cc  + g[x][y].ldc  + g[x][y].rdc  + g[x][y].rc;

        g[x][y].v = g[x][y].cmx * x + g[x][y].cmy * y + g[x][y].cc;
        g[x][y].v += g[x-1][y].v + g[x][y-1].v - g[x-1][y-1].v;
    }

    DBG(
        cout << "END " << endl;
        //FOR(y,1,H) { FOR(x,1,W) { cout << g[x][y].rmx << ' '; } cout << endl; } cout << endl;
        //FOR(y,1,H) { FOR(x,1,W) { cout << g[x][y].rmy << ' '; } cout << endl; } cout << endl;
        //FOR(y,1,H) { FOR(x,1,W) { cout << g[x][y].rc << ' '; } cout << endl; } cout << endl;
        //FOR(y,1,H) { FOR(x,1,W) { cout << g[x][y].cmx << ' '; } cout << endl; } cout << endl;
        ///FOR(y,1,H) { FOR(x,1,W) { cout << g[x][y].cmy << ' '; } cout << endl; } cout << endl;
        ///FOR(y,1,H) { FOR(x,1,W) { cout << g[x][y].cc << ' '; } cout << endl; } cout << endl;
        cout << "V " << endl;
        FOR(y,1,H) { FOR(x,1,W) { cout << g[x][y].v << ' '; } cout << endl; } cout << endl;
    )

    cin >> Q; FOR(q,0,Q-1) {
        int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2; 
        ll s = g[x2][y2].v - g[x1-1][y2].v + g[x1-1][y1-1].v - g[x2][y1-1].v;

        ll r = (ll)(x2-x1+1)*(y2-y1+1);
        DBG(cout << "S R " << s << " " << r << endl;)
        cout << (ll)round((long double)s/r) << '\n';
    }
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 2
• Subtask 3: 0 / 3
• Subtask 4: 0 / 2
• Subtask 5: 0 / 6
• Subtask 6: 0 / 4
• Subtask 7: 0 / 6
• Subtask 8: 0 / 4
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10
• Subtask 11: 0 / 15
• Subtask 12: 0 / 10
• Subtask 13: 0 / 12
• Subtask 14: 0 / 8