Submission #1217887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217887		dosts	Mosaic (IOI24_mosaic)	C++20	5 / 100	1119 ms	2162688 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;

vi mosaic(vector<int32_t> X, vector<int32_t> Y,
                              vector<int32_t> T, vector<int32_t> B,
                              vector<int32_t> L, vector<int32_t> R) {
  int N = X.size(),Q = T.size();
  vector<vi> grid(N+1,vi(N+1,0));
  for (int i = 1;i<=N;i++) grid[1][i] = X[i-1];
  for (int i = 1;i<=N;i++) grid[i][1] = Y[i-1];
  for (int i = 2;i<=N;i++) {
    for (int j = 2;j<=N;j++) {
      grid[i][j] = (!grid[i-1][j] && !grid[i][j-1]);
      if (grid[i][j] && i >= 3 && j >= 3) assert(grid[i-1][j-1]);
    }
  }
  for (int i=1;i<=N;i++) {
    for (int j=1;j<=N;j++) {
      grid[i][j] += grid[i][j-1]+grid[i-1][j]-grid[i-1][j-1];
    }
  }
  auto rectsum = [&](int x1,int y1,int x2,int y2) {
    return grid[x2][y2]-grid[x1-1][y2]-grid[x2][y1-1]+grid[x1-1][y1-1];
  };
  
  vi ans(Q,0);
  for (int i = 0;i<Q;i++) {
    T[i]++,L[i]++,R[i]++,B[i]++;
    ans[i] = rectsum(T[i],L[i],B[i],R[i]);
  }
  return ans;
}

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