Submission #1242332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242332		mychecksedad	Mosaic (IOI24_mosaic)	C++20	22 / 100	210 ms	204228 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define ll long long int
#define cerr if(0) cerr
const int N = 5005;

int a[N][N], pref[N][N];
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 n = X.size();
  int q = T.size();
  vector<array<int, 3>> Q;
  for(int i = 0; i < n; ++i) a[0][i] = X[i];
  for(int i = 0; i < n; ++i) a[i][0] = Y[i];
  
  for(int i = 1; i < n; ++i){
    for(int j = 1; j < n ; ++j){
      if(a[i - 1][j] == 0 && a[i][j - 1] == 0) a[i][j] = 1;
      else a[i][j] = 0;
    }
  }
  for(int i = 0; i < n; ++i){
    for(int j = 0; j< n; ++j){
      pref[i][j] = a[i][j];
      if(i > 0) pref[i][j] += pref[i - 1][j];
      if(j > 0) pref[i][j] += pref[i][j - 1];
      if(i > 0 && j > 0) pref[i][j] -= pref[i - 1][j - 1];
    }
  }
  vector<ll> C(q);
  for(int i = 0; i < q; ++i){
    int x1 = T[i], x2 = B[i];
    int y1 = L[i], y2 = R[i];
    C[i] = pref[x2][y2];
    if(x1 > 0) C[i] -= pref[x1 - 1][y2];
    if(y1 > 0) C[i] -= pref[x2][y1 - 1];
    if(x1 > 0 && y1 > 0) C[i] += pref[x1-1][y1-1];
  }

  return C;
}

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