답안 #1105588

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1105588	2024-10-26T20:11:13 Z	Zicrus	모자이크 (IOI24_mosaic)	C++17	53 / 100	115 ms	52096 KB

mosaic

#include <bits/stdc++.h>
#include "mosaic.h"
using namespace std;

typedef long long ll;

ll n, q;
vector<vector<ll>> lay, layPref;
vector<ll> stairs;

vector<ll> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) {
    n = X.size();
    q = T.size();
    lay = vector<vector<ll>>(5, vector<ll>(2*n-1));
    layPref = vector<vector<ll>>(5, vector<ll>(2*n));
    stairs = vector<ll>(2*n);
    vector<ll> res(q);
    for (int i = 0; i < n; i++) {
        lay[0][n-1+i] = X[i];
        lay[0][n-1-i] = Y[i];
    }
    for (int L = 1; L < min(5ll, n); L++) {
        ll mid = n-1-L;
        lay[L][mid] = !lay[L-1][mid] && !lay[L-1][mid+2];
        for (int i = mid+1; i < 2*n-1-2*L; i++) {
            lay[L][i] = !lay[L][i-1] && !lay[L-1][i+2];
        }
        for (int i = mid-1; i >= 0; i--) {
            lay[L][i] = !lay[L][i+1] && !lay[L-1][i];
        }
    }
    for (int L = 0; L < min(5ll, n); L++) {
        for (int i = 0; i < 2*n-1-2*L; i++) {
            layPref[L][i+1] = layPref[L][i] + lay[L][i];
        }
    }
    if (n >= 5) {
        for (int i = 0; i < 2*n-1-2*5; i++) {
            stairs[i+1] = stairs[i] + (i+1)*lay[4][i];
        }
    }

    // Solve
    for (int k = 0; k < q; k++) {
        ll t = T[k], b = B[k], l = L[k], r = R[k];
        ll ans = 0;
        bool skip = false;
        while (t < 5 || l < 5) {
            if (t < l) { // Move t
                ll L = t;
                ll mid = n-1-L;
                ll ref = mid-L;
                ll idL = ref + l;
                ll idR = ref + r;
                ans += layPref[L][idR+1] - layPref[L][idL];
                t++;
            }
            else { // Move l
                ll L = l;
                ll idL = n-1-b;
                ll idR = n-1-t;
                ans += layPref[L][idR+1] - layPref[L][idL];
                l++;
            }

            // Check if done
            if (b-t < 0 || r-l < 0) {
                skip = true;
                break;
            }
        }

        if (skip) {
            res[k] = ans;
            continue;
        }

        // Get remaining area
        ll idBL = n-1-b + l-4;
        ll idBR = n-1-b + r-4;
        ll idTL = n-1-t + l-4;
        ll idTR = n-1-t + r-4;

        ll idL = min(idTL, idBR);
        ll idR = max(idTL, idBR);
        ll idLL = idBL;
        ll idRR = idTR;
        ll w = min(b-t+1, r-l+1);
        
        ans += (layPref[4][idR+1] - layPref[4][idL]) * w; // middle
        ans += stairs[idL] - stairs[idLL] - (layPref[4][idL] - layPref[4][idLL])*idLL; // left
        ll rightStair = stairs[idRR+1] - stairs[idR+1] - (layPref[4][idRR+1] - layPref[4][idR+1])*(idR+1);
        ans += (layPref[4][idRR+1] - layPref[4][idR+1])*(idRR-idR+1) - rightStair; // right

        res[k] = ans;
    }
    return res;
}

#ifdef TEST
#include "grader.cpp"
#endif

Subtask #0
0.0 / 0.0

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

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	592 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	428 KB	Output is correct
9	Correct	1 ms	504 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct

Subtask #2
0.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	592 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	428 KB	Output is correct
9	Correct	1 ms	504 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Correct	1 ms	336 KB	Output is correct
15	Incorrect	1 ms	336 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	94 ms	49876 KB	Output is correct
2	Correct	101 ms	49752 KB	Output is correct
3	Correct	102 ms	49168 KB	Output is correct
4	Correct	96 ms	49680 KB	Output is correct
5	Correct	78 ms	30496 KB	Output is correct

Subtask #4
0.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	592 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	428 KB	Output is correct
9	Correct	1 ms	504 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Correct	1 ms	336 KB	Output is correct
15	Incorrect	1 ms	336 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	51 ms	9800 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	109 ms	51472 KB	Output is correct
2	Correct	106 ms	51216 KB	Output is correct
3	Correct	99 ms	49936 KB	Output is correct
4	Correct	98 ms	49936 KB	Output is correct
5	Correct	104 ms	52096 KB	Output is correct
6	Correct	83 ms	32044 KB	Output is correct
7	Correct	73 ms	23756 KB	Output is correct

Subtask #7
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	94 ms	49876 KB	Output is correct
2	Correct	101 ms	49752 KB	Output is correct
3	Correct	102 ms	49168 KB	Output is correct
4	Correct	96 ms	49680 KB	Output is correct
5	Correct	78 ms	30496 KB	Output is correct
6	Correct	109 ms	51472 KB	Output is correct
7	Correct	106 ms	51216 KB	Output is correct
8	Correct	99 ms	49936 KB	Output is correct
9	Correct	98 ms	49936 KB	Output is correct
10	Correct	104 ms	52096 KB	Output is correct
11	Correct	83 ms	32044 KB	Output is correct
12	Correct	73 ms	23756 KB	Output is correct
13	Correct	106 ms	51472 KB	Output is correct
14	Correct	102 ms	51524 KB	Output is correct
15	Correct	115 ms	51716 KB	Output is correct
16	Correct	99 ms	49948 KB	Output is correct
17	Correct	103 ms	51224 KB	Output is correct
18	Correct	99 ms	51628 KB	Output is correct
19	Correct	80 ms	27652 KB	Output is correct

Subtask #8
0.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	592 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Correct	1 ms	428 KB	Output is correct
10	Correct	1 ms	504 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Correct	1 ms	336 KB	Output is correct
15	Correct	1 ms	336 KB	Output is correct
16	Incorrect	1 ms	336 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

답안 #1105588

Compilation message