답안 #63456 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
63456	2018-08-01T20:36:26 Z	Benq	Nuclearia (CEOI15_nuclearia)	C++11	100 / 100	993 ms	164492 KB

nuclearia

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#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()

#define NDEBUG
 
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;
 
array<ll,2> operator+(const array<ll,2>& l, const array<ll,2>& r) {
    return {l[0]+r[0],l[1]+r[1]}; 
}

array<ll,2> operator+=(array<ll,2>& l, const array<ll,2>& r) {
    return l = l+r;
}

template<class T> struct bad {
    int W,H;
    T dat[2500000];
    void init(int _W, int _H) {
        W = _W, H = _H;
        memset(dat,0,sizeof dat);
    }
    T get(int a, int b) { 
        return dat[H*a+b]; 
    }
    void ad(int a, int b, T val) { 
        dat[H*a+b] += val; 
    }
};
 
struct cum {
    bad<array<ll,2>> L, up, down;
    int W,H;
    void init(int _W, int _H) { 
        W = _W, H = _H;
        L.init(W,H), up.init(W,H), down.init(W,H); 
    }
    void prop() {
        F0R(i,W) {
            F0R(j,H) {
                L.ad(i,j,down.get(i,j)+up.get(i,j));
                if (i != W-1) {
                    up.ad(i+1,min(H-1,j+1),up.get(i,j));
                    if (j) down.ad(i+1,j-1,down.get(i,j));
                }
            }
        }
        F0R(i,W) F0Rd(j,H-1) L.ad(i,j,L.get(i,j+1));
    }
};
 
cum c;
bad<ll> res;
int W,H,N;
vector<array<int,4>> todo;
 
pi trans(pi x) {
    return {H-1-x.s,x.f};
}

void rot() {
    bad<ll> RES; RES.init(H,W);
    F0R(i,W) F0R(j,H) 
        RES.ad(H-1-j,i,res.get(i,j));
    F0R(i,sz(todo)) {
        int val = H-1-todo[i][1];
        todo[i][1] = todo[i][0];
        todo[i][0] = val;
    }
    swap(res,RES); swap(W,H);
}
 
void prop() {
    c.prop();
    F0R(i,W) F0R(j,H) {
        auto a = c.L.get(i,j);
        res.ad(i,j,a[0]+i*a[1]);
    }
}
 
void process(array<int,4> a) {
    int mul = a[2]/a[3];
    ll z = a[2]+(ll)a[0]*a[3];
    if (a[0]+1 < W) {
        c.up.ad(a[0]+1,a[1],{z,-a[3]});
        if (a[1]-2 >= 0) c.down.ad(a[0]+1,a[1]-2,{-z,a[3]});
    }
    if (a[0]+1+mul < W) {
        c.up.ad(a[0]+1+mul,min(a[1]+mul,H-1),{-z,a[3]});
        if (a[1]-2-mul >= 0) c.down.ad(a[0]+1+mul,a[1]-2-mul,{z,-a[3]});
    }
}
 
void solve() {
    c.init(W,H);
    for (auto a: todo) process(a);
    prop();
}
 
ll query(int x1, int x2, int y1, int y2) {
    x1 --, x2 --, y1 --, y2 --;
    ll ret = res.get(x2,y2);
    if (x1) {
        ret -= res.get(x1-1,y2);
        if (y1) ret += res.get(x1-1,y1-1);
    }
    if (y1) ret -= res.get(x2,y1-1);
    return ret;
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> W >> H >> N;
    res.init(W,H);
    F0R(i,N) {
        int x,y,a,b; cin >> x >> y >> a >> b; 
        x--, y--;
        res.ad(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";
    }
    exit(0);*/
    F0R(i,W) F0R(j,H) {
        if (i) {
            res.ad(i,j,res.get(i-1,j));
            if (j) res.ad(i,j,-res.get(i-1,j-1));
        }
        if (j) res.ad(i,j,res.get(i,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
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	393 ms	156920 KB	Output is correct
2	Correct	366 ms	159336 KB	Output is correct
3	Correct	318 ms	159336 KB	Output is correct

Subtask #2
2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	370 ms	159336 KB	Output is correct
2	Correct	379 ms	159432 KB	Output is correct

Subtask #3
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	535 ms	159432 KB	Output is correct
2	Correct	376 ms	159484 KB	Output is correct

Subtask #4
2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	554 ms	159484 KB	Output is correct
2	Correct	355 ms	159572 KB	Output is correct

Subtask #5
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	624 ms	159572 KB	Output is correct
2	Correct	378 ms	159620 KB	Output is correct

Subtask #6
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	476 ms	159620 KB	Output is correct
2	Correct	385 ms	159620 KB	Output is correct

Subtask #7
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	678 ms	159620 KB	Output is correct
2	Correct	336 ms	159764 KB	Output is correct

Subtask #8
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	535 ms	159764 KB	Output is correct
2	Correct	367 ms	159764 KB	Output is correct

Subtask #9
15.0 / 15.0

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

Subtask #10
10.0 / 10.0

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

Subtask #11
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	993 ms	162876 KB	Output is correct
2	Correct	887 ms	162876 KB	Output is correct

Subtask #12
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	811 ms	162876 KB	Output is correct
2	Correct	826 ms	164044 KB	Output is correct

Subtask #13
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	771 ms	164280 KB	Output is correct
2	Correct	777 ms	164388 KB	Output is correct

Subtask #14
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	902 ms	164492 KB	Output is correct
2	Correct	787 ms	164492 KB	Output is correct

답안 #63456

Compilation message