Submission #1108802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108802		KasymK	Mosaic (IOI24_mosaic)	C++17	29 / 100	211 ms	304068 KiB

mosaic

#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i)
#define wr puts("----------------")
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int N = 5005;
const int NN = 2e5+5;
int v[N][N];
ll p[N][N];
ll par[NN];

vector<ll> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R){
    memset(v, -1, sizeof v);
    int n = (int)X.size();
    if(n >= N){
        for(int i = 1; i <= n; ++i)
            par[i] = par[i-1]+X[i-1];
        int Q = (int)T.size();
        vector<ll> ans;
        for(int i = 0; i < Q; ++i)
            ans.pb(par[R[i]+1]-par[L[i]]);
        return ans;
    }
    for(int i = 1; i <= n; ++i)
        par[i] = par[i-1]+X[i-1], v[1][i] = X[i-1];
    for(int i = 1; i <= n; ++i)
        v[i][1] = Y[i-1];
    auto wow = [&](int a, int b) -> int {
        return (!(a|b)?1:0);
    };
    auto sm = [&](int x, int x1, int y, int y1) -> ll {
        return (p[x1][y1]+p[x-1][y-1]-p[x-1][y1]-p[x1][y-1]);
    };
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if(v[i][j]==-1 and ~v[i-1][j] and ~v[i][j-1])
                v[i][j] = wow(v[i-1][j], v[i][j-1]);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            p[i][j] = p[i-1][j]+p[i][j-1]-p[i-1][j-1]+v[i][j];
    int Q = (int)L.size();
    vector<ll> ans;
    for(int i = 0; i < Q; ++i)
        ans.pb(sm(T[i]+1, B[i]+1, L[i]+1, R[i]+1));
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 0 / 8
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19
• Subtask 8: 0 / 22