Submission #1104947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104947		belgianbot	Mosaic (IOI24_mosaic)	C++17	100 / 100	136 ms	44452 KiB

mosaic

    #include "mosaic.h"
    #include <bits/stdc++.h>
    #define int long long
     
    using namespace std;
     
    vector<signed> X, Y, T, B, L, R;
    vector<long long> C;
    int N, Q;
     
    void sub() {
     
        vector<vector<bool>> grid(N, vector<bool>(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++) {
          grid[i][j] = !(grid[i - 1][j] || grid[i][j - 1]);
        }
      }
     
      vector<vector<int>> dp(N , vector<int> (N, 0));
      for (int i = 0; i < N; i++) {
        int l = 0;
        for (int j = 0; j < N; j++) {
          l += grid[i][j];
          if (i) dp[i][j] = dp[i - 1][j];
          dp[i][j] += l; 
        }
      }
     
      for (int i = 0; i < Q; i++) {
        int ans = 0;
        if (!L[i] && ! T[i]) ans = dp[B[i]][R[i]];
        else {
          ans = dp[B[i]][R[i]];
          if (L[i]) ans -= dp[B[i]][L[i] - 1];
          if (T[i]) ans -= dp[T[i] - 1][R[i]];
          if (L[i] && T[i]) ans += dp[T[i] - 1][L[i] - 1];
        }
        C[i] = ans;
      }
    }
    std::vector<long long> mosaic(std::vector<signed> X_, std::vector<signed> Y_,std::vector<signed> T_, std::vector<signed> B_, std::vector<signed> L_, std::vector<signed> R_) {
     
      ios::sync_with_stdio(false);
      cin.tie(0);
      X = X_; Y = Y_; T = T_; B = B_; L = L_; R = R_;
      Q = (int)T.size();
      N = X.size();
      C.resize(Q, 0);
      if (N <= 3) {
        sub();
        return C;
      }
      
      vector<vector<bool>> line(3, vector<bool>(N)), column(3, vector<bool>(N));
      for (int i = 0; i < N; i++) {
        line[0][i] = X[i];
        column[0][i] = Y[i];
      }
      line[1][0] = Y[1], line[2][0] = Y[2];
      column[1][0] = X[1], column[2][0] = X[2];
      for (int i = 1; i < 3; i++) {
        for (int j = 1; j < N; j++) {
          line[i][j] = !(line[i - 1][j] || line[i][j - 1]);
          column[i][j] = !(column[i - 1][j] || column[i][j - 1]);
        }
      }
     
      vector<vector<int>> dpLine(3 , vector<int> (N, 0)), dpColumn(3, vector<int>(N, 0));
      for (int i = 0; i < 3; i++) {
        int lLine = 0, lColumn = 0;
        for (int j = 0; j < N; j++) {
          lLine += line[i][j]; lColumn += column[i][j];
          if (i) {
            dpLine[i][j] = dpLine[i - 1][j];
            dpColumn[i][j] = dpColumn[i - 1][j];
          }
          dpLine[i][j] += lLine, dpColumn[i][j] += lColumn; 
        }
      }
      
      vector<bool> diag(2 * N-1, false);
      for (int i = 0; i <= N - 2; i++) {
        diag[N + 1 - i] = column[2][i];
        diag[N - 3 + i] = line[2][i];
      }
      
      vector<int> prefL(2 * N - 1, 0), prefR(2 * N-1, 0), pref(2 * N-1);
     
      int cnt = 1;
      for (int i = 0; i < 2 * N - 1; i++) {
        if (i) {
            prefL[i] = prefL[i - 1];
            pref[i] = pref[i - 1];
            prefR[2 * N - i - 2] = prefR[2 * N - i - 1];
        }
        prefL[i] += diag[i] * cnt;
        prefR[2 * N - i - 2] += diag[2 * N - i - 2] * cnt;
        pref[i] += diag[i];
        cnt++;
      }
      /*for (int i = 0; i < 3; i++) {
        prefL[i] = 0;
        pref[i] = 0;
        prefR[i] = 0;
        prefL[2*N - 2 - i] = 0;
        prefR[2*N - 2 - i] = 0;
        pref[2*N - 2 - i] = 0;
     
      }*/
      
      for (int i = 0; i < Q; i++) {
        int t = T[i], b = B[i], l = L[i], r = R[i];
        
        if (t < 3) {
            if (b < 3) {
                C[i] += dpLine[b][r];
                if (t) C[i] -= dpLine[t - 1][r];
                if (l) C[i] -= dpLine[b][l - 1];
                if (t && l) C[i] += dpLine[t - 1][l - 1];
                continue;
            }
            else {
                C[i] += dpLine[2][r];
                if (t) C[i] -= dpLine[t - 1][r];
                if (l) C[i] -= dpLine[2][l - 1];
                if (t && l) C[i] += dpLine[t - 1][l - 1];
            }
            t = 3;
        }
        if (l < 3) {
            if (r < 3) {
                C[i] += dpColumn[r][b];
                if (t) C[i] -= dpColumn[r][t - 1];
                if (l) C[i] -= dpColumn[l - 1][b];
                if (t && l) C[i] += dpColumn[l - 1][t - 1];
                continue;
            }
            else {
                C[i] += dpColumn[2][b];
                if (t) C[i] -= dpColumn[2][t - 1];
                if (l) C[i] -= dpColumn[l - 1][b];
                if (t && l) C[i] += dpColumn[l - 1][t - 1];
            }
            l = 3;
        }
        int diag1 = N - 1 - b + l;
        int diag2 = N - 1 - t + r;
        
        int mid = (diag1 + diag2 + 1) / 2;
        C[i] += prefL[mid] - prefL[diag1 - 1];
        C[i] -= (pref[mid] - pref[diag1 - 1]) * diag1;
        C[i] += prefR[mid + 1] - prefR[diag2 + 1];
        C[i] -= (pref[diag2] - pref[mid]) * (2 * N - 2 - diag2);
        int height = b - t + 1, large = r - l + 1, limit = min(height, large);
        /*if (mid >= diag1 + limit - 1)*/C[i] -= prefL[mid] - prefL[diag1 + limit - 1] - (pref[mid] - pref[diag1 + limit - 1]) * (diag1 + limit);
        /*if (mid + 1 - diag2 + limit - 1 <= 0)*/ C[i] -= prefR[mid + 1] - prefR[diag2 - limit + 1] - (pref[diag2 - limit]- pref[mid]) * (2 * N - 2 - diag2 + limit);
      }
      return C;
    }

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