Submission #142692

#	Time	Username	Problem	Language	Result	Execution time	Memory
142692		lyc	Nuclearia (CEOI15_nuclearia)	C++14	25 / 100	726 ms	111540 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 = 3000000;

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+1)) + x]; }
} nuclearia, posDiag, negDiag, row, col;

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

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

inline void addRow(int y, int sx, int ex, ll m) {
    row(sx,y) += m;
    if (ex+1 <= W) 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 < 1 and sy < 1) {
        int out = max(1-sx, 1-sy);
        nuclearia(1,1) += (ll) out * m;
        sx += out, sy += out;
    } else if (sx < 1) {
        int out = 1-sx;
        addCol(1,sy,sy+out-1,m);
        sx += out, sy += out;
    } else if (sy < 1) {
        int out = 1-sy;
        addRow(1,sx,sx+out-1,m);
        sx += out, sy += out;
    }

    negDiag(sx, sy) += m;
    if (ex+1 <= W and ey+1 <= H) 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 (sx < 1 and sy > H) {
        int out = max(1-sx, sy-H);
        sx += out, sy -= out;
    } else if (sx < 1) {
        int out = 1-sx;
        addCol(1,sy-out+1,sy,m);
        sx += out, sy -= out;
    } else if (sy > H) {
        int out = sy-H;
        sx += out, sy -= out;
    }

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

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

inline void summariseDiags() {
    FOR(x,1,W) FOR(y,1,H) {
        negDiag(x,y) += negDiag(x-1,y-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,1,W) FOR(y,1,H) {
        nuclearia(x,y) += negDiag(x,y) + posDiag(x,y);
    }
}

inline void summariseLines() {
    FOR(x,1,W) FOR(y,1,H) {
        row(x,y) += row(x-1,y);
        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,1,W) FOR(y,1,H) {
        nuclearia(x,y) += row(x,y) + col(x,y);
    }
}

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

    DBG(cout << "NUCLEARIA " << endl; FOR(y,1,H) { FOR(x,1,W) { 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,y,a,b}; }

    for (Plant p : plant) {
        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,1,H) { FOR(x,1,W) { cout << nuclearia(x,y) << ' '; } cout << endl; })
    summarise();    // calc nuclearia
    summarise();    // calc nuclearia_pre

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

        ll r = (ll)(x2-x1+1)*(y2-y1+1);
        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: 15 / 15
• Subtask 12: 10 / 10
• Subtask 13: 0 / 12
• Subtask 14: 0 / 8