oj.uz

Submission #1108980

# Submission time Handle Problem Language Result Execution time Memory
1108980 2024-11-05T18:18:24 Z Kerim Mosaic (IOI24_mosaic) C++17
48 / 100
 695 ms 94448 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];

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());
    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 Incorrect 1 ms 2384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2492 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Incorrect 1 ms 2384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2492 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Incorrect 1 ms 2384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 694 ms 94360 KB Output is correct
2 Correct 670 ms 94360 KB Output is correct
3 Correct 662 ms 94396 KB Output is correct
4 Correct 661 ms 94356 KB Output is correct
5 Correct 336 ms 52608 KB Output is correct

Subtask #4
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2492 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Incorrect 1 ms 2384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 11760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 94396 KB Output is correct
2 Correct 661 ms 94396 KB Output is correct
3 Correct 665 ms 94396 KB Output is correct
4 Correct 675 ms 94280 KB Output is correct
5 Correct 662 ms 94396 KB Output is correct
6 Correct 370 ms 52412 KB Output is correct
7 Correct 202 ms 35008 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 694 ms 94360 KB Output is correct
2 Correct 670 ms 94360 KB Output is correct
3 Correct 662 ms 94396 KB Output is correct
4 Correct 661 ms 94356 KB Output is correct
5 Correct 336 ms 52608 KB Output is correct
6 Correct 695 ms 94396 KB Output is correct
7 Correct 661 ms 94396 KB Output is correct
8 Correct 665 ms 94396 KB Output is correct
9 Correct 675 ms 94280 KB Output is correct
10 Correct 662 ms 94396 KB Output is correct
11 Correct 370 ms 52412 KB Output is correct
12 Correct 202 ms 35008 KB Output is correct
13 Correct 662 ms 94448 KB Output is correct
14 Correct 673 ms 94232 KB Output is correct
15 Correct 669 ms 94284 KB Output is correct
16 Correct 659 ms 94396 KB Output is correct
17 Correct 651 ms 94396 KB Output is correct
18 Correct 666 ms 94400 KB Output is correct
19 Correct 276 ms 43456 KB Output is correct

Subtask #8
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2384 KB Output isn't correct
2 Halted 0 ms 0 KB -