Submission #1203005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203005		tamyte	Mosaic (IOI24_mosaic)	C++20	In queue	0 ms	0 KiB

mosaic

#include "mosaic.h"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> check(std::vector<int> X, std::vector<int> Y,
                              std::vector<int> T, std::vector<int> B,
                              std::vector<int> L, std::vector<int> R) {
        int Q = (int)T.size();
  int N = (int)X.size();
  vector<vector<int>> grid(N, vector<int>(N));
  for (int i = 0; i < N; ++i) {
    grid[0][i] = X[i];
    grid[i][0] = Y[i];
  }
  for (int i = 1; i < N; ++i) {
    for (int j = 1; j < N; ++j) {
        if (grid[i - 1][j] + grid[i][j - 1] == 0) grid[i][j] = 1;
        else grid[i][j] = 0;
    }
  }
  /*for (auto& v : grid) {
    for (auto& u : v) {
        cout << u << " ";
    }
    cout << "\n";
  }
  cout << "\n";*/

  vector<vector<ll>> dp(N, vector<ll>(N));
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
        dp[i][j] = grid[i][j];
        if (i > 0) dp[i][j] += dp[i - 1][j];
        if (j > 0) dp[i][j] += dp[i][j - 1];
        if (i > 0 && j > 0) dp[i][j] -= dp[i - 1][j - 1];
    }
  }
  std::vector<long long> C(Q, 0);
  for (int i = 0; i < Q; ++i) {
    int y1 = T[i];
    int y2 = B[i];
    int x1 = L[i];
    int x2 = R[i];
    ll res = 0;
    if (y1 > 0) res -= dp[y1 - 1][x2];
    if (x1 > 0) res -= dp[y2][x1 - 1];
    if (x1 > 0 && y1 > 0) res += dp[y1 - 1][x1 - 1];
    res += dp[y2][x2];
    C[i] = res;
  }
  return C;
}

std::vector<long long> mosaic(std::vector<int> X, std::vector<int> Y,
                              std::vector<int> T, std::vector<int> B,
                              std::vector<int> L, std::vector<int> R) {
  int Q = (int)T.size();
  int N = (int)X.size();
  if (N <= 2) {
    return check(X, Y, T, B, L, R);
  }
  map<int, int> mp;
  int start = (X[1] + Y[1] == 0);
    if (start == 1) {
        mp[0]++;
    }
    vector<int> nX, nY;
    nX.push_back(start);
    nY.push_back(start);
    for (int i = 2; i < N; ++i) {
        nX.push_back((nX.back() + X[i] == 0));
        if (nX.back() == 1) {
            mp[1 - i]++;
        }
    }
    for (int i = 2; i < N; ++i) {
        nY.push_back((nY.back() + Y[i] == 0));
        if (nY.back() == 1) {
            mp[i - 1]++;
        }
    }
    start = (nX[1] + nY[1] == 0);
    vector<int> nnX{start}, nnY{start};
    if (start == 1) {
        mp[0]++;
    }
    for (int i = 2; i < nX.size(); ++i) {
        nnX.push_back((nnX.back() + nX[i] == 0));
        if (nnX.back() == 1) {
            mp[1 - i]++;
        }
    }
    for (int i = 2; i < nY.size(); ++i) {
        nnY.push_back((nnY.back() + nY[i] == 0));
        if (nnY.back() == 1) {
            mp[i - 1]++;
        }
    }
    /*for (auto& u : mp) {
        cout << u.first << " " << u.second << "\n";
    }
    for (auto& u : nX) {
        cout << u << " ";
    }
    cout << endl;
    for (auto& u : nY) {
        cout << u << " ";
    }
    cout << endl;
    for (auto& u : nnX) {
        cout << u << " ";
    }
    cout << endl;
    for (auto& u : nnY) {
        cout << u << " ";
    }
    cout << endl;*/
    vector<ll> C(Q);
    for (int i = 0; i < Q; ++i) {
        int y1 = T[i];
        int y2 = B[i];
        int x1 = L[i];
        int x2 = R[i];
        if (y1 == 0 || x1 == 0) {
            if (y1 == 0) {
                C[i] = X[x1];
            } else {
                C[i] = Y[y1];
            }
            continue;
        }
        if (mp.count(y1 - x1)) {
            C[i] = 1;
        } else {
            C[i] = 0;
        }
    }
    return C;
}
/*
10
1 0 1 0 1 0 1 0 1 0
1 1 1 1 1 1 1 1 1 1
10
0 1 0 1 1 1 0 1 0 1
0 1 0 0 1 0 0 1 0 0



*/
/*
4
1 0 1 0
1 1 0 1
2
0 0 0 0
1 1 3 3
*/