oj.uz

Submission #1109261

# Submission time Handle Problem Language Result Execution time Memory
1109261 2024-11-06T09:44:06 Z Kerim Mosaic (IOI24_mosaic) C++17
60 / 100
 1000 ms 103428 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);
                if (a <= b)
                    res += cnt[b--] * 1LL * (j+1);
            }
            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 2384 KB Output is correct
7 Correct 1 ms 2384 KB Output is correct
8 Correct 1 ms 2596 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 2 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 2384 KB Output is correct
7 Correct 1 ms 2384 KB Output is correct
8 Correct 1 ms 2596 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 2 ms 2384 KB Output is correct
11 Correct 2 ms 2384 KB Output is correct
12 Correct 1 ms 2528 KB Output is correct
13 Correct 2 ms 2384 KB Output is correct
14 Correct 2 ms 2384 KB Output is correct
15 Correct 2 ms 2384 KB Output is correct
16 Correct 2 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 807 ms 97724 KB Output is correct
2 Correct 841 ms 97904 KB Output is correct
3 Correct 837 ms 97592 KB Output is correct
4 Correct 818 ms 99004 KB Output is correct
5 Correct 409 ms 57240 KB Output is correct

Subtask #4
0.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 2384 KB Output is correct
7 Correct 1 ms 2384 KB Output is correct
8 Correct 1 ms 2596 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 2 ms 2384 KB Output is correct
11 Correct 2 ms 2384 KB Output is correct
12 Correct 1 ms 2528 KB Output is correct
13 Correct 2 ms 2384 KB Output is correct
14 Correct 2 ms 2384 KB Output is correct
15 Correct 2 ms 2384 KB Output is correct
16 Correct 2 ms 2384 KB Output is correct
17 Correct 1 ms 2384 KB Output is correct
18 Correct 390 ms 14144 KB Output is correct
19 Correct 828 ms 16892 KB Output is correct
20 Execution timed out 1016 ms 15892 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 12220 KB Output is correct
2 Execution timed out 1031 ms 97436 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 867 ms 99068 KB Output is correct
2 Correct 772 ms 99424 KB Output is correct
3 Correct 773 ms 97980 KB Output is correct
4 Correct 851 ms 97604 KB Output is correct
5 Correct 829 ms 99376 KB Output is correct
6 Correct 416 ms 58812 KB Output is correct
7 Correct 239 ms 36148 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 807 ms 97724 KB Output is correct
2 Correct 841 ms 97904 KB Output is correct
3 Correct 837 ms 97592 KB Output is correct
4 Correct 818 ms 99004 KB Output is correct
5 Correct 409 ms 57240 KB Output is correct
6 Correct 867 ms 99068 KB Output is correct
7 Correct 772 ms 99424 KB Output is correct
8 Correct 773 ms 97980 KB Output is correct
9 Correct 851 ms 97604 KB Output is correct
10 Correct 829 ms 99376 KB Output is correct
11 Correct 416 ms 58812 KB Output is correct
12 Correct 239 ms 36148 KB Output is correct
13 Correct 833 ms 97860 KB Output is correct
14 Correct 844 ms 103428 KB Output is correct
15 Correct 832 ms 100380 KB Output is correct
16 Correct 809 ms 97412 KB Output is correct
17 Correct 808 ms 102844 KB Output is correct
18 Correct 846 ms 102204 KB Output is correct
19 Correct 334 ms 48596 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 2384 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 1 ms 2596 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 2528 KB Output is correct
14 Correct 2 ms 2384 KB Output is correct
15 Correct 2 ms 2384 KB Output is correct
16 Correct 2 ms 2384 KB Output is correct
17 Correct 2 ms 2384 KB Output is correct
18 Correct 1 ms 2384 KB Output is correct
19 Correct 807 ms 97724 KB Output is correct
20 Correct 841 ms 97904 KB Output is correct
21 Correct 837 ms 97592 KB Output is correct
22 Correct 818 ms 99004 KB Output is correct
23 Correct 409 ms 57240 KB Output is correct
24 Correct 390 ms 14144 KB Output is correct
25 Correct 828 ms 16892 KB Output is correct
26 Execution timed out 1016 ms 15892 KB Time limit exceeded
27 Halted 0 ms 0 KB -