oj.uz

Submission #1109274

# Submission time Handle Problem Language Result Execution time Memory
1109274 2024-11-06T10:07:04 Z Kerim Mosaic (IOI24_mosaic) C++17
100 / 100
 875 ms 117228 KB 
#include "bits/stdc++.h"
#define ll long long
#define pb push_back
#define pii pair<int, int>
using namespace std;
const int N = 4e5+5;
int cnt[N], arcalyk[4][N], tarhun[N][4];
ll pre[N], suf[N], cep[N], sag[N];
const int M = 5005;
int dp[M][M];
int wow(int a, int b){
    return (!(a|b)?1:0);
}

vector<ll> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R){
    int n = (int)X.size();
    for (int i = 0; i < n+n; i++)
        cnt[i] = 0;
    map<pii, int> mp;
    for(int i = 1; i <= n; ++i)
        mp[{1, i}] = X[i-1], mp[{i, 1}] = Y[i-1];
    for(int i = 2; i <= n; ++i)
        for(int j = 2; j <= 3; ++j)
            mp[{i, j}] = wow(mp[{i-1, j}], mp[{i, j-1}]);
    for(int i = 2; i <= 3; ++i)
        for(int j = 2; j <= n; ++j)
            mp[{i, j}] = wow(mp[{i-1, j}], mp[{i, j-1}]);

    int i = 3;
    for(int j = 3; j <= n; ++j)
        cnt[i-j+n] = mp[{i, j}];
    int j = 3;
    for(int i = 3; i <= n; ++i)
        cnt[i-j+n] = mp[{i, j}];

    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= n; j++)
            arcalyk[i][j] = mp[{i,j}] + arcalyk[i][j-1];
    for (int j = 1; j <= 3; j++)
        for (int i = 1; i <= n; i++)
            tarhun[i][j] = mp[{i,j}] + tarhun[i-1][j];

    suf[n+n] = cep[n+n] = 0;
    sag[0] = pre[0] = cnt[0];
    for (int i = 1; i < n+n; i++){
        pre[i] = pre[i-1] + cnt[i];
        sag[i] = sag[i-1] + pre[i-1] + cnt[i];
    }
    for (int i = n+n-1; i >= 0; i--){
        suf[i] = suf[i+1] + cnt[i];
        cep[i] = cep[i+1] + suf[i+1] + cnt[i];
    }

    vector<ll> ans;
    for(int i = 0; i < (int)L.size(); ++i){
        int x = T[i]+1, y = L[i]+1, yy = R[i]+1, xx = B[i]+1;
        ll res = 0;
        while (x <= 3 and x <= xx)
            res += arcalyk[x][yy]-arcalyk[x][y-1], x += 1;
        if (x <= xx){
            while (y <= 3 and y <= yy)
                res += tarhun[xx][y]-tarhun[x-1][y], y += 1;
        }
        if (x <= xx and y <= yy){
            int a = x-y+n, b = x-yy+n, k = xx-x+1;
            swap(a, b);
            int len = b-a+1;
            b += k-1;
            k = min(k, len);
            res += cep[a] - (cep[a+k]+k*suf[a+k]);
            res += sag[b] - (sag[b-k]+k*pre[b-k]);

            // for (int j = 0; j < k; j++){
                // res += cnt[a++] * 1LL * (j+1);
                // res += cnt[b--] * 1LL * (j+1);
            // }
            a += k; b -= k;
            if (a > b)
                res -= cnt[++b] * 1LL * k;
            res += (pre[b]-pre[a-1])*1LL*k;
        }
        ans.pb(res);
    }
    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10576 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10740 KB Output is correct
2 Correct 2 ms 10576 KB Output is correct
3 Correct 2 ms 10576 KB Output is correct
4 Correct 2 ms 10576 KB Output is correct
5 Correct 2 ms 10576 KB Output is correct
6 Correct 2 ms 10576 KB Output is correct
7 Correct 2 ms 10576 KB Output is correct
8 Correct 2 ms 10576 KB Output is correct
9 Correct 2 ms 10576 KB Output is correct
10 Correct 2 ms 10576 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10740 KB Output is correct
2 Correct 2 ms 10576 KB Output is correct
3 Correct 2 ms 10576 KB Output is correct
4 Correct 2 ms 10576 KB Output is correct
5 Correct 2 ms 10576 KB Output is correct
6 Correct 2 ms 10576 KB Output is correct
7 Correct 2 ms 10576 KB Output is correct
8 Correct 2 ms 10576 KB Output is correct
9 Correct 2 ms 10576 KB Output is correct
10 Correct 2 ms 10576 KB Output is correct
11 Correct 2 ms 10576 KB Output is correct
12 Correct 3 ms 10576 KB Output is correct
13 Correct 2 ms 10752 KB Output is correct
14 Correct 2 ms 10576 KB Output is correct
15 Correct 2 ms 10576 KB Output is correct
16 Correct 2 ms 10576 KB Output is correct
17 Correct 2 ms 10576 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 800 ms 111436 KB Output is correct
2 Correct 807 ms 111504 KB Output is correct
3 Correct 788 ms 111440 KB Output is correct
4 Correct 830 ms 111532 KB Output is correct
5 Correct 373 ms 67256 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10740 KB Output is correct
2 Correct 2 ms 10576 KB Output is correct
3 Correct 2 ms 10576 KB Output is correct
4 Correct 2 ms 10576 KB Output is correct
5 Correct 2 ms 10576 KB Output is correct
6 Correct 2 ms 10576 KB Output is correct
7 Correct 2 ms 10576 KB Output is correct
8 Correct 2 ms 10576 KB Output is correct
9 Correct 2 ms 10576 KB Output is correct
10 Correct 2 ms 10576 KB Output is correct
11 Correct 2 ms 10576 KB Output is correct
12 Correct 3 ms 10576 KB Output is correct
13 Correct 2 ms 10752 KB Output is correct
14 Correct 2 ms 10576 KB Output is correct
15 Correct 2 ms 10576 KB Output is correct
16 Correct 2 ms 10576 KB Output is correct
17 Correct 2 ms 10576 KB Output is correct
18 Correct 109 ms 22176 KB Output is correct
19 Correct 82 ms 22196 KB Output is correct
20 Correct 74 ms 22216 KB Output is correct
21 Correct 70 ms 22212 KB Output is correct
22 Correct 84 ms 22212 KB Output is correct
23 Correct 68 ms 20948 KB Output is correct
24 Correct 88 ms 20872 KB Output is correct
25 Correct 66 ms 20868 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 20092 KB Output is correct
2 Correct 836 ms 111428 KB Output is correct
3 Correct 875 ms 115900 KB Output is correct
4 Correct 838 ms 114392 KB Output is correct
5 Correct 841 ms 113196 KB Output is correct
6 Correct 815 ms 114972 KB Output is correct
7 Correct 831 ms 113392 KB Output is correct
8 Correct 860 ms 114184 KB Output is correct
9 Correct 442 ms 70800 KB Output is correct
10 Correct 440 ms 71048 KB Output is correct
11 Correct 427 ms 69060 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 830 ms 111640 KB Output is correct
2 Correct 823 ms 111660 KB Output is correct
3 Correct 820 ms 111504 KB Output is correct
4 Correct 806 ms 111504 KB Output is correct
5 Correct 834 ms 111580 KB Output is correct
6 Correct 402 ms 67260 KB Output is correct
7 Correct 268 ms 49712 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 800 ms 111436 KB Output is correct
2 Correct 807 ms 111504 KB Output is correct
3 Correct 788 ms 111440 KB Output is correct
4 Correct 830 ms 111532 KB Output is correct
5 Correct 373 ms 67256 KB Output is correct
6 Correct 830 ms 111640 KB Output is correct
7 Correct 823 ms 111660 KB Output is correct
8 Correct 820 ms 111504 KB Output is correct
9 Correct 806 ms 111504 KB Output is correct
10 Correct 834 ms 111580 KB Output is correct
11 Correct 402 ms 67260 KB Output is correct
12 Correct 268 ms 49712 KB Output is correct
13 Correct 799 ms 111660 KB Output is correct
14 Correct 789 ms 111624 KB Output is correct
15 Correct 874 ms 111548 KB Output is correct
16 Correct 873 ms 111456 KB Output is correct
17 Correct 830 ms 111508 KB Output is correct
18 Correct 798 ms 111756 KB Output is correct
19 Correct 329 ms 58048 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10576 KB Output is correct
2 Correct 2 ms 10740 KB Output is correct
3 Correct 2 ms 10576 KB Output is correct
4 Correct 2 ms 10576 KB Output is correct
5 Correct 2 ms 10576 KB Output is correct
6 Correct 2 ms 10576 KB Output is correct
7 Correct 2 ms 10576 KB Output is correct
8 Correct 2 ms 10576 KB Output is correct
9 Correct 2 ms 10576 KB Output is correct
10 Correct 2 ms 10576 KB Output is correct
11 Correct 2 ms 10576 KB Output is correct
12 Correct 2 ms 10576 KB Output is correct
13 Correct 3 ms 10576 KB Output is correct
14 Correct 2 ms 10752 KB Output is correct
15 Correct 2 ms 10576 KB Output is correct
16 Correct 2 ms 10576 KB Output is correct
17 Correct 2 ms 10576 KB Output is correct
18 Correct 2 ms 10576 KB Output is correct
19 Correct 800 ms 111436 KB Output is correct
20 Correct 807 ms 111504 KB Output is correct
21 Correct 788 ms 111440 KB Output is correct
22 Correct 830 ms 111532 KB Output is correct
23 Correct 373 ms 67256 KB Output is correct
24 Correct 109 ms 22176 KB Output is correct
25 Correct 82 ms 22196 KB Output is correct
26 Correct 74 ms 22216 KB Output is correct
27 Correct 70 ms 22212 KB Output is correct
28 Correct 84 ms 22212 KB Output is correct
29 Correct 68 ms 20948 KB Output is correct
30 Correct 88 ms 20872 KB Output is correct
31 Correct 66 ms 20868 KB Output is correct
32 Correct 57 ms 20092 KB Output is correct
33 Correct 836 ms 111428 KB Output is correct
34 Correct 875 ms 115900 KB Output is correct
35 Correct 838 ms 114392 KB Output is correct
36 Correct 841 ms 113196 KB Output is correct
37 Correct 815 ms 114972 KB Output is correct
38 Correct 831 ms 113392 KB Output is correct
39 Correct 860 ms 114184 KB Output is correct
40 Correct 442 ms 70800 KB Output is correct
41 Correct 440 ms 71048 KB Output is correct
42 Correct 427 ms 69060 KB Output is correct
43 Correct 830 ms 111640 KB Output is correct
44 Correct 823 ms 111660 KB Output is correct
45 Correct 820 ms 111504 KB Output is correct
46 Correct 806 ms 111504 KB Output is correct
47 Correct 834 ms 111580 KB Output is correct
48 Correct 402 ms 67260 KB Output is correct
49 Correct 268 ms 49712 KB Output is correct
50 Correct 799 ms 111660 KB Output is correct
51 Correct 789 ms 111624 KB Output is correct
52 Correct 874 ms 111548 KB Output is correct
53 Correct 873 ms 111456 KB Output is correct
54 Correct 830 ms 111508 KB Output is correct
55 Correct 798 ms 111756 KB Output is correct
56 Correct 329 ms 58048 KB Output is correct
57 Correct 806 ms 116088 KB Output is correct
58 Correct 806 ms 116860 KB Output is correct
59 Correct 839 ms 117228 KB Output is correct
60 Correct 820 ms 116700 KB Output is correct
61 Correct 819 ms 116668 KB Output is correct
62 Correct 831 ms 116924 KB Output is correct
63 Correct 421 ms 72124 KB Output is correct
64 Correct 237 ms 51908 KB Output is correct