Submission #142787

#	Time	Username	Problem	Language	Result	Execution time	Memory
142787		lyc	Nuclearia (CEOI15_nuclearia)	C++14	100 / 100	759 ms	110872 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)

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

const int MAXN = 2e5+5;
const int MAXWH = 2500100;

int W,H,N,Q;
struct Plant { int x, y, a, b; };
struct NUCLEARIA {
    ll data[MAXWH];
    inline ll& operator() (int x, int y) { return data[(y*W) + x]; }
} nuclearia, posDiag, negDiag, row, col;

inline void addSquare(int sx, int sy, int ex, int ey, ll c) {
    sx = max(0, sx);
    sy = max(0, sy);
    nuclearia(sx  , sy  ) += c;
    if (ex+1 <= W-1) nuclearia(ex+1, sy  ) -= c;
    if (ey+1 <= H-1) nuclearia(sx  , ey+1) -= c;
    if (ex+1 <= W-1 and ey+1 <= H-1) nuclearia(ex+1, ey+1) += c;
}

inline void addCol(int x, int sy, int ey, ll m) {
    assert(x >= 0 and x < W and sy >= 0 and ey < H);
    col(x,sy) += m;
    if (ey+1 <= H-1) col(x,ey+1) -= m;
}

inline void addRow(int y, int sx, int ex, ll m) {
    assert(y >= 0 and y < H and sx >= 0 and ex < W);
    row(sx,y) += m;
    if (ex+1 <= W-1) row(ex+1,y) -= m;
}

inline void addNegDiag(int sx, int sy, int ex, int ey, ll m) {
    DBG(cout << "ADD NEG " << sx << " " << sy << " TO " << ex << " " << ey << " BY " << m << endl;)
    if (sx < 0 and sy < 0) {
        int out = min(0-sx, 0-sy);
        nuclearia(0,0) += (ll) out * m;
        sx += out, sy += out;
    }
    if (sx < 0) {
        int out = 0-sx;
        addCol(0,sy,sy+out-1,m);
        sx += out, sy += out;
    }
    if (sy < 0) {
        int out = 0-sy;
        addRow(0,sx,sx+out-1,m);
        sx += out, sy += out;
    }

    negDiag(sx, sy) += m;
    if (ex+1 <= W-1 and ey+1 <= H-1) negDiag(ex+1, ey+1) -= m;
}

inline void addPosDiag(int sx, int sy, int ex, int ey, ll m) {
    DBG(cout << "ADD POS " << sx << " " << sy << " TO " << ex << " " << ey << " BY " << m << endl;)
    if (sy >= H) {
        int out = sy-(H-1);
        sx += out, sy -= out;
    }
    if (sx < 0) {
        int out = 0-sx;
        addCol(0,sy-out+1,sy,m);
        sx += out, sy -= out;
    }

    if (ex >= W) {
        int out = ex-(W-1);
        ex -= out, ey += out;
    }
    if (ey < 0) {
        int out = 0-ey;
        addRow(0,ex-out+1,ex,m);
        ex -= out, ey += out;
    }

    posDiag(sx, sy) += m;
    if (ex+1 <= W-1 and ey-1 >= 0) posDiag(ex+1, max(0,ey-1)) -= m;
}

inline void summariseDiags() {
    FOR(x,1,W-1) FOR(y,0,H-1) {
        if (y-1 >= 0) negDiag(x,y) += negDiag(x-1,y-1);
        if (y+1 <= H-1) posDiag(x,y) += posDiag(x-1,y+1);
    }

    //DBG(cout << "NEG DIAG " << endl; FOR(y,1,H) { FOR(x,1,W) { cout << negDiag(x,y) << ' '; } cout << endl; });
    //DBG(cout << "POS DIAG " << endl; FOR(y,1,H) { FOR(x,1,W) { cout << posDiag(x,y) << ' '; } cout << endl; });
}

inline void addDiags() {
    FOR(x,0,W-1) FOR(y,0,H-1) {
        nuclearia(x,y) += negDiag(x,y) + posDiag(x,y);
    }
}

inline void summariseLines() {
    FOR(x,0,W-1) FOR(y,0,H-1) {
        if (x-1 >= 0) row(x,y) += row(x-1,y);
        if (y-1 >= 0) col(x,y) += col(x,y-1);
    }
    
    //DBG(cout << "ROW " << endl; FOR(y,1,H) { FOR(x,1,W) { cout << row(x,y) << ' '; } cout << endl; });
    //DBG(cout << "COL " << endl; FOR(y,1,H) { FOR(x,1,W) { cout << col(x,y) << ' '; } cout << endl; });
}

inline void addLines() {
    FOR(x,0,W-1) FOR(y,0,H-1) {
        nuclearia(x,y) += row(x,y) + col(x,y);
    }
}

inline void summarise() {
    FOR(x,0,W-1) FOR(y,0,H-1) {
        //col(x,y) += col(x,y-1);
        //nuclearia(x, y) += nuclearia(x-1, y) + nuclearia(x, y-1) - nuclearia(x-1, y-1);
        if (x-1 >= 0) nuclearia(x,y) += nuclearia(x-1,y);
        if (y-1 >= 0) nuclearia(x,y) += nuclearia(x,y-1);
        if (x-1 >= 0 and y-1 >= 0) nuclearia(x,y) -= nuclearia(x-1,y-1);
    }

    DBG(cout << "NUCLEARIA " << endl; FOR(y,0,H-1) { FOR(x,0,W-1) { cout << setw(2) << nuclearia(x, y) << ' '; } cout << endl; }); }

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-1,y-1,a,b}; }

    //int idx = 0;
    for (Plant p : plant) {
        //++idx;
        //if (idx != 1) continue;

        int r = (p.a-1)/p.b;
        //DBG(cout << "PLANT " << p.x << " " << p.y << " a b " << p.a << " " << p.b << " r " << r << endl;)
        addSquare(p.x-r, p.y-r, p.x+r, p.y+r, p.a % p.b);   // add directly to nuclearia_aux
        if (p.a % p.b == 0) ++r;
        if (r > 0) {
            addNegDiag(p.x-r+1, p.y-r+1, p.x+r  , p.y+r  ,  p.b);
            addPosDiag(p.x-r+1, p.y+r  , p.x+r  , p.y-r+1, -p.b);
        }
    }

    summariseDiags();
    addDiags();     // add to nuclearia_aux
    summariseLines();
    addLines();     // add to nuclearia_aux
    DBG(cout << "AUX " << endl; FOR(y,0,H-1) { FOR(x,0,W-1) { cout << nuclearia(x,y) << ' '; } cout << endl; })
    summarise();    // calc nuclearia
    summarise();    // calc nuclearia_pre

    DBG(ll g[W][H]; memset(g, 0, sizeof g);
    FOR(x,0,W-1) FOR(y,0,H-1) {
        for (Plant p : plant) {
            g[x][y] += max(0, p.a - p.b * max(abs(x-p.x),abs(y-p.y)));
        }
    }
    FOR(y,0,H-1) { FOR(x,0,W-1) { cout << g[x][y] << ' ';  } cout << endl; }
    FOR(x,0,W-1) FOR(y,0,H-1) {
        if (x-1 >= 0) g[x][y] += g[x-1][y];
        if (y-1 >= 0) g[x][y] += g[x][y-1];
        if (x-1 >= 0 and y-1 >= 0) g[x][y] -= g[x-1][y-1];
    }
    cout << endl;
    FOR(y,0,H-1) { FOR(x,0,W-1) { cout << g[x][y] << ' ';  } cout << endl; })

    cin >> Q; FOR(q,0,Q-1) {
        int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2; 
        --x1,--y1,--x2,--y2;
        ll s = nuclearia(x2,y2);
        if (x1-1 >= 0) s -= nuclearia(x1-1,y2);
        if (y1-1 >= 0) s -= nuclearia(x2,y1-1);
        if (x1-1 >= 0 and y1-1 >= 0) s += nuclearia(x1-1,y1-1);

        DBG(ll s2 = g[x2][y2];
        if (x1-1 >= 0) s2 -= g[x1-1][y2];
        if (y1-1 >= 0) s2 -= g[x2][y1-1];
        if (x1-1 >= 0 and y1-1 >= 0) s2 += g[x1-1][y1-1];
        cout << s << " " << s2 << endl;)

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

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