oj.uz

답안 #276501

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
276501 2020-08-20T13:16:32 Z MarcoMeijer Nuclearia (CEOI15_nuclearia) C++14
44 / 100
 1000 ms 243960 KB 
#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;
ll w, h, n, w1;
ll x[MX], y[MX], a[MX], b[MX];
ll c[MX], d[MX], e[MX], g[MX], v[MX], temp[MX];

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) RE(j,h)
        temp[h-1-j + i*h1] = v[f(i,j)];
    swap(w,h);
    w1 = h1;
    RE(i,w) RE(j,h) v[f(i,j)] = temp[f(i,j)];
}
void addArea(ll bx, ll by, ll ex, ll ey, ll val) {
    bx = max(0ll,bx);
    by = max(0ll,by);
    ex = min(w,ex+1);
    ey = min(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;
}
void add(ll x, ll y, ll del) {
    if(x >= w || y >= h) return;
    if(x < 0 && y < 0) {
        ll add = min(-x, -y);
        x += add;
        y += add;
        c[0] += del*add;
    }
    if(x < 0) {
        g[f(0,y)] += del;
        g[f(0,y-x)] -= del;
        y -= x;
        x = 0;
    }
    if(y < 0) {
        d[f(x,0)] += del;
        d[f(x-y,0)] -= del;
        x -= y;
        y = 0;
    }
    e[f(x,y)] += del;
}
void solve() {
    RE(i,w) RE(j,h) c[f(i,j)] = d[f(i,j)] = e[f(i,j)] = g[f(i,j)] = 0;
    RE(i,n) {
        ll 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]);
        addArea(x[i]+r+1,y[i]+r+1,w,h,-ll(r*2+1)*b[i]);
        addArea(x[i]-r,y[i]+r+1,x[i]+r,h,-ll(r*2+2)*b[i]);
    }
    RE(i,w) RE(j,h) d[f(i,j)] += (i ? d[f(i-1,j)] : 0ll);
    RE(i,w) RE(j,h) g[f(i,j)] += (j ? g[f(i,j-1)] : 0ll);
    RE(i,w) RE(j,h) e[f(i,j)] += (i&&j ? e[f(i-1,j-1)] : 0ll);
    RE(i,w) RE(j,h) c[f(i,j)] += d[f(i,j)]+e[f(i,j)]+g[f(i,j)];
    RE(i,w) RE(j,h) {
        if(i) c[f(i,j)] += c[f(i-1,j)];
        if(j) c[f(i,j)] += c[f(i,j-1)];
        if(i&&j) c[f(i,j)] -= c[f(i-1,j-1)];
        v[f(i,j)] += c[f(i,j)];
    }
}

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

    RE(i,4) {
        solve();
        rotate();
    }

    RE(i,w) RE(j,h) c[f(i,j)] = 0;
    RE(i,n) {
        ll r = (a[i]-1)/b[i];
        addArea(x[i]-r, y[i]-r, x[i]+r, y[i]+r, (-b[i]*r+a[i])*2ll -ll(r*2+4)*b[i]);
    }
    RE(i,w) RE(j,h) {
        if(i) c[f(i,j)] += c[f(i-1,j)];
        if(j) c[f(i,j)] += c[f(i,j-1)];
        if(i&&j) c[f(i,j)] -= c[f(i-1,j-1)];
        v[f(i,j)] += c[f(i,j)];
    }

    RE(i,w) RE(j,h) v[f(i,j)] /= 2;

    // create sums
    REV(i,0,w) REV(j,0,h) v[f(i+1,j+1)] = v[f(i,j)];
    RE(i,w) v[f(i,0)]=0;
    RE(i,h) v[f(0,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
    ll q;
    IN(q);
    RE(i,q) {
        ll x1, x2, y1, y2;
        IN(x1,y1,x2,y2); x1--; y1--;
        ll sm = v[f(x2,y2)] - v[f(x1,y2)] - v[f(x2,y1)] + v[f(x1,y1)];
        ll area = abs(x2-x1)*abs(y2-y1);
        OUTL((sm+area/2)/area);
    }
}

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 369 ms 235284 KB Output is correct
2 Correct 81 ms 4964 KB Output is correct
3 Correct 75 ms 4060 KB Output is correct

Subtask #2
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 358 ms 235276 KB Output is correct
2 Correct 90 ms 4760 KB Output is correct

Subtask #3
0 / 3.0

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

Subtask #4
0 / 2.0

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

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 478 ms 237436 KB Output is correct
2 Correct 81 ms 5512 KB Output is correct

Subtask #6
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 291 ms 96968 KB Output is correct
2 Correct 75 ms 4728 KB Output is correct

Subtask #7
0 / 6.0

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

Subtask #8
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 248 ms 73336 KB Output is correct
2 Correct 72 ms 4472 KB Output is correct

Subtask #9
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 690 ms 243952 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 685 ms 243960 KB Output is correct

Subtask #11
0 / 15.0

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

Subtask #12
0 / 10.0

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

Subtask #13
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 906 ms 127468 KB Output is correct
2 Execution timed out 1083 ms 130296 KB Time limit exceeded

Subtask #14
0 / 8.0

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