oj.uz

답안 #541422

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
541422 2022-03-23T14:44:35 Z AugustinasJucas Nuclearia (CEOI15_nuclearia) C++14
42 / 100
 1000 ms 205060 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
vector<vector<long long> > val;
vector<vector<long long> > pref;
int n, m, p, q;
bool swp = 0;
void precalc(){
//    cout << "pref: \n";
    for(int i = 0; i < n; i++) {
        long long s = 0;
        for(int j = 0; j < m; j++) {
            s += val[i][j];
            pref[i][j] = (i == 0 ? 0ll : pref[i-1][j]) + s;
//            cout << pref[i][j] << " ";
        }
//        cout << endl;
    }
}
long long getSum(int e1, int s1, int e2, int s2) {
    long long ret = 0;
    ret += pref[e2][s2];
    if(e1 != 0) {
        ret -= pref[e1-1][s2];
    }
    if(s1 != 0){
        ret -= pref[e2][s1-1];
    }
    if(e1 != 0 && s1 != 0) {
        ret += pref[e1-1][s1-1];
    }
    return ret;
}
long long rnd(long long x, long long y) {
    long long maz = x / y;
    x %= y;

    if(2ll*x >= y) maz++;
    return maz;
}
void maz () {
    for(int h = 0; h < p; h++) {
        long long e, s, a, b;
        cin >> s >> e >> a >> b; e--; s--;
        if(swp) swap(e, s);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                val[i][j] += max(0ll, 1ll * a - 1ll * b * max(abs(i-e), abs(s-j)));
            }
        }
    }

    precalc();
    
    cin >> q;
    while(q--) {
        int e1, s1, e2, s2;
        cin >> s1 >> e1 >> s2 >> e2; s1--; e1--; s2--; e2--;
        if(swp) {
            swap(e1, s1);
            swap(e2, s2);
        }
        long long sm = getSum(e1, s1, e2, s2);
        long long S = sm;
        long long pl = (1+abs(e1-e2)) * (abs(s1-s2)+1);
        long long ans = rnd(S, pl);
        cout << ans << "\n";

    }
}
void doEil(int eil, int s, int nutol, long long a, long long b, vector<vector<long long> > &A, vector<vector<long long> > &B){
    long long nl = a / b;
    long long prm = a % b;

    int le = s - nl;
    int mid = s;
    int ri = s + nl;

    le = max(0, le);
    ri = min(ri, m-1);
    
    long long vL = a - b * abs(le - s);
    long long vR = a - b * abs(ri - s);
    
    A[eil][le] += vL;
    A[eil][ri+1] -= vR;

    B[eil][le] += b;
    B[eil][mid-nutol] -= b;
    B[eil][mid+nutol] -= b;
//    B[eil][mid] -= 2*b;
    B[eil][ri] += b;
}
void h1(){
//    vector<long long> A(m+2, 0), B(m+2, 0);
    vector<vector<long long> > A(n, vector<long long> (m+2, 0)), B(n, vector<long long> (m+2, 0));
    for(int h = 0; h < p; h++) {
        long long e, s, a, b;
        cin >> s >> e >> a >> b; e--; s--;
        if(swp) {
            swap(e, s);
        }
        long long nl = a / b;
        
        for(int i = max(0ll, e-nl); i <= min(1ll*n-1, e+nl); i++) {
            doEil(i, s, abs(i-e), a, b, A, B);
        } 
    }
    for(int j = 0; j < n; j++){
        long long sitas = 0;
        long long delta = 0;
        for(int i = 0; i < m; i++) {
            sitas += A[j][i];
            sitas += delta;
            val[j][i] = sitas;
            delta += B[j][i];
        }
    }

//    cout << "val: \n"; for(int i = 0; i < m; i++) cout << val[0][i] << " ";
//    cout << endl << endl;

    precalc();
    
    cin >> q;
    while(q--) {
        int e1, s1, e2, s2;
        cin >> s1 >> e1 >> s2 >> e2; s1--; e1--; s2--; e2--;
        if(swp) {
            swap(e1, s1);
            swap(e2, s2);
        }
        long long sm = getSum(e1, s1, e2, s2);
        long long S = sm;
        long long pl = (1+abs(e1-e2)) * (abs(s1-s2)+1);
        long long ans = rnd(S, pl);
        cout << ans << "\n";

    }
   
}
int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin >> m >> n >> p;
    // noriu visada eiti per eilutes. t.y., n <= m turi galioti!
    if(n > m){
        swap(n, m);
        swp = 1;
    }
    vector<vector<long long> > iden(n, vector<long long> (m, 0));
    val = iden; pref = iden;
    h1();
    return 0;
    if(n == 1) {
        h1();
        return 0;
    }else if(1ll * m * n * p <= 100000000ll) {
        maz();
        return 0;
    }
    return 0;
}

Compilation message

nuclearia.cpp: In function 'void doEil(int, int, int, long long int, long long int, std::vector<std::vector<long long int> >&, std::vector<std::vector<long long int> >&)':
nuclearia.cpp:73:15: warning: unused variable 'prm' [-Wunused-variable]
   73 |     long long prm = a % b;
      |               ^~~

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 117628 KB Output is correct
2 Correct 64 ms 4652 KB Output is correct
3 Correct 56 ms 3844 KB Output is correct

Subtask #2
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 117700 KB Output is correct
2 Correct 74 ms 4712 KB Output is correct

Subtask #3
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 172 ms 199120 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 99188 KB Output is correct
2 Correct 79 ms 4572 KB Output is correct

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 123580 KB Output is correct
2 Correct 91 ms 5244 KB Output is correct

Subtask #6
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 53104 KB Output is correct
2 Correct 63 ms 4612 KB Output is correct

Subtask #7
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 254 ms 205060 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 121 ms 49216 KB Output is correct
2 Runtime error 1 ms 464 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #9
15.0 / 15.0

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

Subtask #10
10.0 / 10.0

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

Subtask #11
0 / 15.0

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

Subtask #12
0 / 10.0

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

Subtask #13
0 / 12.0

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

Subtask #14
0 / 8.0

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