oj.uz

Submission #1108985

# Submission time Handle Problem Language Result Execution time Memory
1108985 2024-11-05T18:24:58 Z Kerim Mosaic (IOI24_mosaic) C++17
70 / 100
 698 ms 112324 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];
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();
    assert(X.front()==Y.front());
    if (n <= 5000){
        for (int i = 0; i < n; i++)
            dp[1][i+1] = X[i];
        for (int i = 0; i < n; i++)
            dp[i+1][1] = Y[i];
        for (int i = 2; i <= n; i++)
            for (int j = 2; j <= n; j++)
                dp[i][j] = wow(dp[i-1][j], dp[i][j-1]);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
        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;
            ans.push_back(dp[xx][yy] - dp[x-1][yy] - dp[xx][y-1] + dp[x-1][y-1]);
        }
        return ans;
    }
    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 ii = 3;
    // for(int jj = 3; jj <= n; ++jj)
    //     cnt[ii-jj+n] = mp[{ii, jj}];
    for (auto [key, value]: mp)
        cnt[key.first-key.second+n] = value;
    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 i = 1; i < n+n; i++)
        cnt[i] += cnt[i-1];
    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;
        if (x <= 3){
            ans.pb(arcalyk[x][yy]-arcalyk[x][y-1]);
            continue;
        }
        int res = 0;
        while (y <= 3 and y <= yy)
            res += mp[{x, y}], y += 1;
        if (y <= yy){
            int a = x-y+n, b = x-yy+n;
            res += cnt[a] - cnt[b-1];
        }
        ans.pb(res);
    }
    return ans;
}

// int main(){
//     int n;
//     scanf("%d", &n);
//     vector<int> X, Y;
//     for(int i = 1; i <= n; ++i){
//         int x;
//         scanf("%d", &x);
//         X.pb(x);
//     }
//     for(int i = 1; i <= n; ++i){
//         int x;
//         scanf("%d", &x);
//         Y.pb(x);
//     }
//     int q;
//     scanf("%d", &q);
//     vector<int> T, B, L, R;
//     while(q--){
//         int a, b, c, d;
//         scanf("%d%d%d%d", &a, &b, &c, &d);
//         T.pb(a), B.pb(b), L.pb(c), R.pb(d);
//     }
//     vector<ll> ans = mosaic(X, Y, T, B, L, R);
//     for(ll i : ans)
//         printf("%lld ", i);
//     puts("");
//     return 0;
// }

Subtask #0
0.0 / 0.0

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 1 ms 336 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 448 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 1 ms 336 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 448 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 4432 KB Output is correct
12 Correct 2 ms 4588 KB Output is correct
13 Correct 2 ms 4688 KB Output is correct
14 Correct 1 ms 4432 KB Output is correct
15 Correct 1 ms 2384 KB Output is correct
16 Correct 1 ms 2384 KB Output is correct
17 Correct 1 ms 2384 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 675 ms 92824 KB Output is correct
2 Correct 650 ms 92860 KB Output is correct
3 Correct 660 ms 92748 KB Output is correct
4 Correct 673 ms 92860 KB Output is correct
5 Correct 327 ms 52100 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 1 ms 336 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 448 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 4432 KB Output is correct
12 Correct 2 ms 4588 KB Output is correct
13 Correct 2 ms 4688 KB Output is correct
14 Correct 1 ms 4432 KB Output is correct
15 Correct 1 ms 2384 KB Output is correct
16 Correct 1 ms 2384 KB Output is correct
17 Correct 1 ms 2384 KB Output is correct
18 Correct 184 ms 112324 KB Output is correct
19 Correct 181 ms 112072 KB Output is correct
20 Correct 183 ms 111764 KB Output is correct
21 Correct 195 ms 111948 KB Output is correct
22 Correct 186 ms 111884 KB Output is correct
23 Correct 84 ms 52412 KB Output is correct
24 Correct 80 ms 52412 KB Output is correct
25 Correct 84 ms 52412 KB Output is correct

Subtask #5
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 11964 KB Output is correct
2 Incorrect 671 ms 92860 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 677 ms 92864 KB Output is correct
2 Correct 665 ms 92864 KB Output is correct
3 Correct 663 ms 92884 KB Output is correct
4 Correct 695 ms 92756 KB Output is correct
5 Correct 688 ms 92860 KB Output is correct
6 Correct 332 ms 52128 KB Output is correct
7 Correct 206 ms 34752 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 675 ms 92824 KB Output is correct
2 Correct 650 ms 92860 KB Output is correct
3 Correct 660 ms 92748 KB Output is correct
4 Correct 673 ms 92860 KB Output is correct
5 Correct 327 ms 52100 KB Output is correct
6 Correct 677 ms 92864 KB Output is correct
7 Correct 665 ms 92864 KB Output is correct
8 Correct 663 ms 92884 KB Output is correct
9 Correct 695 ms 92756 KB Output is correct
10 Correct 688 ms 92860 KB Output is correct
11 Correct 332 ms 52128 KB Output is correct
12 Correct 206 ms 34752 KB Output is correct
13 Correct 698 ms 92716 KB Output is correct
14 Correct 648 ms 92860 KB Output is correct
15 Correct 687 ms 92860 KB Output is correct
16 Correct 672 ms 92904 KB Output is correct
17 Correct 677 ms 92764 KB Output is correct
18 Correct 670 ms 92864 KB Output is correct
19 Correct 289 ms 43060 KB Output is correct

Subtask #8
0.0 / 22.0

# Verdict Execution time Memory 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 504 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 336 KB Output is correct
9 Correct 1 ms 448 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 4432 KB Output is correct
13 Correct 2 ms 4588 KB Output is correct
14 Correct 2 ms 4688 KB Output is correct
15 Correct 1 ms 4432 KB Output is correct
16 Correct 1 ms 2384 KB Output is correct
17 Correct 1 ms 2384 KB Output is correct
18 Correct 1 ms 2384 KB Output is correct
19 Correct 675 ms 92824 KB Output is correct
20 Correct 650 ms 92860 KB Output is correct
21 Correct 660 ms 92748 KB Output is correct
22 Correct 673 ms 92860 KB Output is correct
23 Correct 327 ms 52100 KB Output is correct
24 Correct 184 ms 112324 KB Output is correct
25 Correct 181 ms 112072 KB Output is correct
26 Correct 183 ms 111764 KB Output is correct
27 Correct 195 ms 111948 KB Output is correct
28 Correct 186 ms 111884 KB Output is correct
29 Correct 84 ms 52412 KB Output is correct
30 Correct 80 ms 52412 KB Output is correct
31 Correct 84 ms 52412 KB Output is correct
32 Correct 46 ms 11964 KB Output is correct
33 Incorrect 671 ms 92860 KB Output isn't correct
34 Halted 0 ms 0 KB -