oj.uz

Submission #1109263

# Submission time Handle Problem Language Result Execution time Memory
1109263 2024-11-06T09:50:02 Z Kerim Mosaic (IOI24_mosaic) C++17
70 / 100
 1000 ms 97724 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], par[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];
    for (int i = 1; i < n+n; i++)
        par[i] = par[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);
            for (int j = 0; j < k; j++){
                res += cnt[a++] * 1LL * (j+1);
                res += cnt[b--] * 1LL * (j+1);
            }
            if (a > b)
                res -= cnt[++b] * 1LL * k;
            res += (par[b]-par[a-1])*1LL*k;
        }
        ans.pb(res);
    }
    return ans;
}

// int main(){
//     freopen("file.in", "r", stdin);
//     srand((unsigned)time(NULL));
//     while (1){
//         int n = rand()%10+2;
//         scanf("%d", &n);
//         vector<int> X, Y;
//         for(int i = 1; i <= n; ++i){
//             int x = rand()%2;
//             scanf("%d", &x);
//             X.pb(x);
//         }
//         for(int i = 1; i <= n; ++i){
//             int x = rand()%2;
//             scanf("%d", &x);
//             Y.pb(x);
//         }
//         Y[0] = X[0];
//         int q = 1000;
//         scanf("%d", &q);
//         vector<int> T, B, L, R;
//         while(q--){
//             int a = rand()%n, b = rand()%n, c = rand()%n, d = rand()%n;
//             scanf("%d%d%d%d", &a, &b, &c, &d);
//             if (a > b) swap(a, b);
//             if (c > d) swap(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);
//         printf("n = %d\n", n);
//     }
//     return 0;
// }

Subtask #0
0.0 / 0.0

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

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 1 ms 2552 KB Output is correct
7 Correct 2 ms 2384 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 1 ms 2384 KB Output is correct
11 Correct 2 ms 2384 KB Output is correct
12 Correct 2 ms 2384 KB Output is correct
13 Correct 1 ms 2384 KB Output is correct
14 Correct 2 ms 2552 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 811 ms 97480 KB Output is correct
2 Correct 816 ms 97644 KB Output is correct
3 Correct 791 ms 97468 KB Output is correct
4 Correct 785 ms 97424 KB Output is correct
5 Correct 394 ms 56252 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 1 ms 2552 KB Output is correct
7 Correct 2 ms 2384 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 1 ms 2384 KB Output is correct
11 Correct 2 ms 2384 KB Output is correct
12 Correct 2 ms 2384 KB Output is correct
13 Correct 1 ms 2384 KB Output is correct
14 Correct 2 ms 2552 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 300 ms 13984 KB Output is correct
19 Correct 583 ms 14028 KB Output is correct
20 Correct 811 ms 14020 KB Output is correct
21 Correct 552 ms 16068 KB Output is correct
22 Correct 479 ms 14020 KB Output is correct
23 Correct 140 ms 12700 KB Output is correct
24 Correct 67 ms 16376 KB Output is correct
25 Correct 68 ms 15044 KB Output is correct

Subtask #5
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 11964 KB Output is correct
2 Execution timed out 1077 ms 94392 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 97468 KB Output is correct
2 Correct 777 ms 97468 KB Output is correct
3 Correct 794 ms 97724 KB Output is correct
4 Correct 795 ms 97428 KB Output is correct
5 Correct 797 ms 97468 KB Output is correct
6 Correct 387 ms 56252 KB Output is correct
7 Correct 235 ms 36148 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 811 ms 97480 KB Output is correct
2 Correct 816 ms 97644 KB Output is correct
3 Correct 791 ms 97468 KB Output is correct
4 Correct 785 ms 97424 KB Output is correct
5 Correct 394 ms 56252 KB Output is correct
6 Correct 795 ms 97468 KB Output is correct
7 Correct 777 ms 97468 KB Output is correct
8 Correct 794 ms 97724 KB Output is correct
9 Correct 795 ms 97428 KB Output is correct
10 Correct 797 ms 97468 KB Output is correct
11 Correct 387 ms 56252 KB Output is correct
12 Correct 235 ms 36148 KB Output is correct
13 Correct 753 ms 97604 KB Output is correct
14 Correct 788 ms 97696 KB Output is correct
15 Correct 865 ms 97468 KB Output is correct
16 Correct 844 ms 97620 KB Output is correct
17 Correct 828 ms 97500 KB Output is correct
18 Correct 775 ms 97468 KB Output is correct
19 Correct 322 ms 47040 KB Output is correct

Subtask #8
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 1 ms 2552 KB Output is correct
8 Correct 2 ms 2384 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 1 ms 2384 KB Output is correct
11 Correct 1 ms 2384 KB Output is correct
12 Correct 2 ms 2384 KB Output is correct
13 Correct 2 ms 2384 KB Output is correct
14 Correct 1 ms 2384 KB Output is correct
15 Correct 2 ms 2552 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 811 ms 97480 KB Output is correct
20 Correct 816 ms 97644 KB Output is correct
21 Correct 791 ms 97468 KB Output is correct
22 Correct 785 ms 97424 KB Output is correct
23 Correct 394 ms 56252 KB Output is correct
24 Correct 300 ms 13984 KB Output is correct
25 Correct 583 ms 14028 KB Output is correct
26 Correct 811 ms 14020 KB Output is correct
27 Correct 552 ms 16068 KB Output is correct
28 Correct 479 ms 14020 KB Output is correct
29 Correct 140 ms 12700 KB Output is correct
30 Correct 67 ms 16376 KB Output is correct
31 Correct 68 ms 15044 KB Output is correct
32 Correct 56 ms 11964 KB Output is correct
33 Execution timed out 1077 ms 94392 KB Time limit exceeded
34 Halted 0 ms 0 KB -