Submission #1109153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109153		Kerim	Mosaic (IOI24_mosaic)	C++17	42 / 100	803 ms	99264 KiB

mosaic

#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
• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 7 / 7
• Subtask 4: 0 / 10
• Subtask 5: 8 / 8
• Subtask 6: 22 / 22
• Subtask 7: 0 / 19
• Subtask 8: 0 / 22