oj.uz

Submission #1108973

# Submission time Handle Problem Language Result Execution time Memory
1108973 2024-11-05T18:14:21 Z Kerim Mosaic (IOI24_mosaic) C++17
7 / 100
 711 ms 94460 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){
    memset(cnt, -1, sizeof cnt);
    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)
            res += mp[{x, y}], y += 1;
        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 2 ms 4088 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 2 ms 3920 KB Output is correct
2 Correct 2 ms 3920 KB Output is correct
3 Incorrect 2 ms 3920 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 2 ms 3920 KB Output is correct
2 Correct 2 ms 3920 KB Output is correct
3 Incorrect 2 ms 3920 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 696 ms 94328 KB Output is correct
2 Correct 696 ms 94300 KB Output is correct
3 Correct 670 ms 94392 KB Output is correct
4 Correct 704 ms 94360 KB Output is correct
5 Correct 361 ms 53180 KB Output is correct

Subtask #4
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3920 KB Output is correct
2 Correct 2 ms 3920 KB Output is correct
3 Incorrect 2 ms 3920 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 61 ms 13304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 711 ms 94408 KB Output is correct
2 Correct 685 ms 94272 KB Output is correct
3 Correct 645 ms 94284 KB Output is correct
4 Incorrect 664 ms 94460 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 94328 KB Output is correct
2 Correct 696 ms 94300 KB Output is correct
3 Correct 670 ms 94392 KB Output is correct
4 Correct 704 ms 94360 KB Output is correct
5 Correct 361 ms 53180 KB Output is correct
6 Correct 711 ms 94408 KB Output is correct
7 Correct 685 ms 94272 KB Output is correct
8 Correct 645 ms 94284 KB Output is correct
9 Incorrect 664 ms 94460 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #8
0.0 / 22.0

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