oj.uz

Submission #1109153

# Submission time Handle Problem Language Result Execution time Memory
1109153 2024-11-06T06:18:30 Z Kerim Mosaic (IOI24_mosaic) C++17
42 / 100
 803 ms 99264 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;
            // }
            int len = b-a+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*min(k, len);
        }
        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 552 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 336 KB Output is correct

Subtask #2
0.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 552 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 336 KB Output is correct
11 Incorrect 1 ms 336 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 798 ms 97212 KB Output is correct
2 Correct 787 ms 97724 KB Output is correct
3 Correct 763 ms 97216 KB Output is correct
4 Correct 780 ms 97428 KB Output is correct
5 Correct 392 ms 53180 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 552 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 336 KB Output is correct
11 Incorrect 1 ms 336 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 9824 KB Output is correct
2 Correct 90 ms 12988 KB Output is correct
3 Correct 105 ms 15772 KB Output is correct
4 Correct 96 ms 13368 KB Output is correct
5 Correct 92 ms 13256 KB Output is correct
6 Correct 89 ms 12988 KB Output is correct
7 Correct 84 ms 12988 KB Output is correct
8 Correct 85 ms 12872 KB Output is correct
9 Correct 83 ms 12988 KB Output is correct
10 Correct 86 ms 12460 KB Output is correct
11 Correct 93 ms 11384 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 779 ms 99260 KB Output is correct
2 Correct 722 ms 99264 KB Output is correct
3 Correct 752 ms 98552 KB Output is correct
4 Correct 784 ms 97212 KB Output is correct
5 Correct 803 ms 97472 KB Output is correct
6 Correct 393 ms 56012 KB Output is correct
7 Correct 236 ms 35556 KB Output is correct

Subtask #7
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 798 ms 97212 KB Output is correct
2 Correct 787 ms 97724 KB Output is correct
3 Correct 763 ms 97216 KB Output is correct
4 Correct 780 ms 97428 KB Output is correct
5 Correct 392 ms 53180 KB Output is correct
6 Correct 779 ms 99260 KB Output is correct
7 Correct 722 ms 99264 KB Output is correct
8 Correct 752 ms 98552 KB Output is correct
9 Correct 784 ms 97212 KB Output is correct
10 Correct 803 ms 97472 KB Output is correct
11 Correct 393 ms 56012 KB Output is correct
12 Correct 236 ms 35556 KB Output is correct
13 Incorrect 783 ms 97468 KB Output isn't correct
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 552 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 336 KB Output is correct
12 Incorrect 1 ms 336 KB Output isn't correct
13 Halted 0 ms 0 KB -