oj.uz

Submission #1109148

# Submission time Handle Problem Language Result Execution time Memory
1109148 2024-11-06T06:10:11 Z Kerim Mosaic (IOI24_mosaic) C++17
49 / 100
 1000 ms 102288 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];
const int M = 5005;
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());
    bool ok = true;
    for (int i = 0; i < n; i++)
        ok &= X[i] == 0, ok &= Y[i] == 0;
    if (ok){
        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;
            if (x == 1)
                x += 1;
            if (y == 1)
                y += 1;
            ll rec = (xx-x+1)*1LL*(yy-y+1);
            if (rec % 2 == 0)
                ans.push_back(rec/2);
            else{
                if ((xx+yy)%2)
                    ans.push_back(rec/2);
                else
                    ans.push_back(rec/2+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 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++)
    //     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, 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);
            for (int j = 0; j < k; j++){
                for (int h = a; h <= b; h++)
                    res += cnt[h];
                a += 1;
                b += 1;
            }
            // b += k-1;
            // for (int j = 0; j < k; j++){
            //     res += cnt[a++] * 1LL * (j+1);
            //     if (a <= b)
            //         res += cnt[b--] * 1LL * (j+1);
            // }
            // res += (b-a+1)*1LL*k;
            // for (int i = 0; i <= ; i++){
            //     res += cnt[a] - cnt[b-1];
            //     a += 1;
            //     b += 1;
            // }
        }
        ans.pb(res);
    }
    return ans;
}

// l = 1, r = 2, k = 5

// 1 2 3 4 5 6 7 8
// 1 1
//   1 1
//     1 1
//       1 1
//         1 1
// 1 2 2 2 2 1



// 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 336 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 336 KB Output is correct
9 Correct 1 ms 504 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 336 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 336 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 2 ms 348 KB Output is correct
13 Correct 2 ms 336 KB Output is correct
14 Correct 3 ms 336 KB Output is correct
15 Correct 1 ms 452 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 801 ms 97548 KB Output is correct
2 Correct 785 ms 97240 KB Output is correct
3 Correct 789 ms 97400 KB Output is correct
4 Correct 697 ms 99632 KB Output is correct
5 Correct 351 ms 54832 KB Output is correct

Subtask #4
0.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 336 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 336 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 2 ms 348 KB Output is correct
13 Correct 2 ms 336 KB Output is correct
14 Correct 3 ms 336 KB Output is correct
15 Correct 1 ms 452 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Execution timed out 1047 ms 8940 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 10732 KB Output is correct
2 Correct 93 ms 18620 KB Output is correct
3 Correct 95 ms 17896 KB Output is correct
4 Correct 112 ms 13528 KB Output is correct
5 Correct 97 ms 13168 KB Output is correct
6 Correct 93 ms 14448 KB Output is correct
7 Correct 102 ms 16044 KB Output is correct
8 Correct 91 ms 15628 KB Output is correct
9 Correct 83 ms 12788 KB Output is correct
10 Correct 97 ms 14704 KB Output is correct
11 Correct 86 ms 14012 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 813 ms 97980 KB Output is correct
2 Correct 790 ms 96560 KB Output is correct
3 Correct 823 ms 98748 KB Output is correct
4 Correct 829 ms 97428 KB Output is correct
5 Correct 834 ms 102288 KB Output is correct
6 Correct 431 ms 58204 KB Output is correct
7 Correct 246 ms 35384 KB Output is correct

Subtask #7
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 801 ms 97548 KB Output is correct
2 Correct 785 ms 97240 KB Output is correct
3 Correct 789 ms 97400 KB Output is correct
4 Correct 697 ms 99632 KB Output is correct
5 Correct 351 ms 54832 KB Output is correct
6 Correct 813 ms 97980 KB Output is correct
7 Correct 790 ms 96560 KB Output is correct
8 Correct 823 ms 98748 KB Output is correct
9 Correct 829 ms 97428 KB Output is correct
10 Correct 834 ms 102288 KB Output is correct
11 Correct 431 ms 58204 KB Output is correct
12 Correct 246 ms 35384 KB Output is correct
13 Execution timed out 1010 ms 94536 KB Time limit exceeded
14 Halted 0 ms 0 KB -

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 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 336 KB Output is correct
9 Correct 1 ms 336 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 2 ms 348 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 3 ms 336 KB Output is correct
16 Correct 1 ms 452 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 801 ms 97548 KB Output is correct
20 Correct 785 ms 97240 KB Output is correct
21 Correct 789 ms 97400 KB Output is correct
22 Correct 697 ms 99632 KB Output is correct
23 Correct 351 ms 54832 KB Output is correct
24 Execution timed out 1047 ms 8940 KB Time limit exceeded
25 Halted 0 ms 0 KB -