Submission #276777

#	Time	Username	Problem	Language	Result	Execution time	Memory
276777		MarcoMeijer	Nuclearia (CEOI15_nuclearia)	C++14	100 / 100	893 ms	248952 KiB

nuclearia

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
 
using namespace std;
 
#define REP(a,b,c) for(int a=int(b); a!=int(c); a++)     
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)     
#define RE(a,b) REP(a,0,b)
#define RE1(a,b) REP(a,1,b+1)
#define REI(a,b,c) REP(a,b,c+1)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define pb push_back
#define sz size()
#define fi first
#define se second
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
 
template<class T> void IN(T& a) {cin>>a;}
template<class T, class... L> void IN(T& a, L&... b) {IN(a); IN(b...);}
template<class T> void OUT(const T& a) {cout<<a;}
template<class T, class... L> void OUT(const T& a, const L&... b) {OUT(a); OUT(b...);}
template<class... T> void OUTL(const T&... a) {OUT(a..., '\n');}
 
const int MX = 5e6+1e5;
int w, h, n, w1, N;
int x[MX], y[MX], a[MX], b[MX];
ll c[MX], d[MX], e[MX], g[MX], v[MX], temp[MX];
bool firstTime = 1;

inline int f(int i, int j) {return i+j*w1;}

void rotate() {
    // [x,y] => [h-1-y,x]
    RE(i,n) {
        y[i] = h-1-y[i];
        swap(x[i], y[i]);
    }
    int h1=h+1;
    RE(i,w) {
        int idx1 = h + i*h1;
        int idx2 = i;
        RE(j,h) {
            idx1--;
            temp[idx1] = v[idx2];
            idx2 += w1;
        }
    }
    swap(w,h);
    w1 = h1;
    RE(i,N) v[i] = temp[i];
}
inline void addArea(int bx, int by, int ex, int ey, ll val) {
    bx = max(0,bx);
    by = max(0,by);
    ex = min((int)w,ex+1);
    ey = min((int)h,ey+1);
    if(bx > ex) return;
    if(by > ey) return;
    c[f(bx,by)] += val;
    c[f(ex,by)] -= val;
    c[f(bx,ey)] -= val;
    c[f(ex,ey)] += val;
}
inline void add(int x, int y, int del) {
    if(x >= w || y >= h) return;
    if(x < 0 && y < 0) {
        int add = min(-x, -y);
        x += add;
        y += add;
        c[0] += del*add;
    }
    if(x < 0) {
        g[y] += del;
        g[y-x] -= del;
        y -= x;
        x = 0;
        if(y >= h) return;
    }
    if(y < 0) {
        d[x] += del;
        d[x-y] -= del;
        x -= y;
        y = 0;
        if(x >= w) return;
    }
    e[f(x,y)] += del;
}
void solve() {
    if(!firstTime) RE(i,N) c[i]=d[i]=e[i]=g[i]=0;
    RE(i,n) {
        int r = (a[i]-1)/b[i];
        add(x[i]-r, y[i]-r, b[i]);
        add(x[i]+r+1, y[i]+r+1, -b[i]);
        int bx = x[i]+r+1;
        int by = y[i]+r+1;
        if(bx < w && by < h)
            c[f(bx,by)] -= ((r<<1)+1)*b[i];
        bx = max(0,x[i]-r);
        by = y[i]+r+1;
        int ex = min((int)w,x[i]+r+1);
        if(by < h) {
            int val = ((r<<1)+2)*b[i];
            c[f(bx,by)] -= val;
            c[f(ex,by)] += val;
        }
        if(firstTime)
            addArea(x[i]-r, y[i]-r, x[i]+r, y[i]+r, a[i]+a[i] -ll((r<<2)+4)*b[i]);
    }
    RE(i,w) d[i] += (i ? d[i-1] : 0ll), c[i] += d[i];
    RE(j,h) g[j] += (j ? g[j-1] : 0ll), c[j*w1] += g[j];
    RE(i,w) {
        int idx=i;
        RE(j,h) {
            int idxl = idx-1;
            int idxu = idx-w1;
            int idxul = idxu-1;
            e[idx] += (i&&j ? e[idxul] : 0ll);
            c[idx] += e[idx];
            if(i) c[idx] += c[idxl];
            if(j) c[idx] += c[idxu];
            if(i&&j) c[idx] -= c[idxul];
            v[idx] += c[idx];
            idx += w1;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    // input
    IN(w,h,n); w1 = w+1;
    N = (w+1)*(h+1);
    RE(i,n) IN(x[i],y[i],a[i],b[i]), x[i]--, y[i]--;

    RE(i,4) {
        solve();
        rotate();
        firstTime = 0;
    }

    RE(i,N) v[i] >>= 1;

    // create sums
    REV(i,0,N) v[i+1+w1] = v[i], v[i]=0;
    RE(i,w) RE(j,h) v[f(i+1,j+1)] += v[f(i,j+1)]+v[f(i+1,j)]-v[f(i,j)];

    // anser queries
    int q;
    IN(q);
    while(q--) {
        int x1, x2, y1, y2;
        IN(x1,y1,x2,y2); x1--; y1--;
        int area = abs(x2-x1)*abs(y2-y1);
        y1 *= w1; y2 *= w1;
        ll sm = v[x2+y2] - v[x1+y2] - v[x2+y1] + v[x1+y1];
        OUTL((sm+area/2)/area);
    }
}

• 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