oj.uz

Submission #63433

# Submission time Handle Problem Language Result Execution time Memory
63433 2018-08-01T19:07:39 Z Benq Nuclearia (CEOI15_nuclearia) C++11
0 / 100
 1000 ms 735928 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

ll** make(int a, int b) {
    ll** x = new ll*[a];
    F0R(i,a) {
        x[i] = new ll[b];
        F0R(j,b) x[i][j] = 0;
    }
    return x;
}

struct cum {
    ll **L, **up, **down;
    int W,H;
    void init(int _W, int _H) { 
        W = _W, H = _H;
        L = make(W,H); 
        up = make(W,H);
        down = make(W,H);
    }
    void prop() {
        F0R(i,W) {
            F0R(j,H) {
                L[i][j] += down[i][j]+up[i][j];
                if (i != W-1) {
                    up[i+1][min(H-1,j+1)] += up[i][j];
                    if (j) down[i+1][j-1] += down[i][j];
                }
            }
        }
        F0R(i,W) F0Rd(j,H-1) L[i][j] += L[i][j+1];
    }
};

cum c, cX;
int W,H,N;
ll **res, **ans;
vector<array<int,4>> todo;

pi trans(pi x) {
    return {H-1-x.s,x.f};
}

void rot() {
    ll **RES = make(H,W);
    F0R(i,W) F0R(j,H) {
        pi x = trans({i,j});
        RES[x.f][x.s] = res[i][j];
    }
    F0R(i,sz(todo)) {
        pi x = trans({todo[i][0],todo[i][1]});
        todo[i][0] = x.f, todo[i][1] = x.s;
    }
    swap(res,RES); swap(W,H);
}

void prop() {
    c.prop(), cX.prop();
    F0R(i,W) F0R(j,H) res[i][j] += c.L[i][j]+cX.L[i][j]*i;
}

void process(array<int,4> a) {
    int mul = a[2]/a[3];
    if (a[0]+1 < W) {
        c.up[a[0]+1][a[1]] += a[2]+a[0]*a[3];
        cX.up[a[0]+1][a[1]] -= a[3];
    }
    if (a[0]+mul+1 < W) {
        c.up[a[0]+1+mul][min(a[1]+mul,H-1)] -= a[2]+a[0]*a[3];
        cX.up[a[0]+1+mul][min(a[1]+mul,H-1)] += a[3];
    }
    if (a[0]+1 < W && a[1]-2 >= 0) {
        c.down[a[0]+1][a[1]-2] -= a[2]+a[0]*a[3];
        cX.down[a[0]+1][a[1]-2] += a[3];
    }
    if (a[0]+1+mul < W && a[1]-2-mul >= 0) {
        c.down[a[0]+1+mul][a[1]-2-mul] += a[2]+a[0]*a[3];
        cX.down[a[0]+1+mul][a[1]-2-mul] -= a[3];
    }
}

void solve() {
    c.init(W,H), cX.init(W,H);
    for (auto a: todo) process(a);
    prop();
}

ll query(int x1, int x2, int y1, int y2) {
    return ans[x2][y2]-ans[x1-1][y2]-ans[x2][y1-1]+ans[x1-1][y1-1];
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> W >> H >> N;
    res = make(W,H);
    F0R(i,N) {
        int x,y,a,b; cin >> x >> y >> a >> b; x--, y--;
        res[x][y] += a;
        todo.pb({x,y,a,b});
    }
    F0R(i,4) {
        solve();
        rot();
    }
    /*F0R(i,W) {
        F0R(j,H) cout << res[i][j] << " ";
        cout << "\n";
    }*/
    ans = make(W+1,H+1);
    FOR(i,1,W+1) {
        FOR(j,1,H+1) {
            ans[i][j] = res[i-1][j-1]+ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];
        }
    }
    int Q; cin >> Q;
    F0R(i,Q) {
        int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2;
        cout << (ll)round((ld)query(x1,x2,y1,y2)/(x2-x1+1)/(y2-y1+1)) << "\n";
    }
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1130 ms 420592 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1133 ms 580868 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 814 ms 589560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 950 ms 630804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1121 ms 685668 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1130 ms 735928 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 954 ms 735928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 797 ms 735928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1114 ms 735928 KB Time limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1128 ms 735928 KB Time limit exceeded

Subtask #11
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1109 ms 735928 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1151 ms 735928 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1117 ms 735928 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1131 ms 735928 KB Time limit exceeded
2 Halted 0 ms 0 KB -