Submission #1099877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099877		model_code	Mosaic (IOI24_mosaic)	C++17	100 / 100	513 ms	150224 KiB

mosaic

// correct/full.cpp

#include "mosaic.h"
#include "bits/stdc++.h"
const int mxN = 1e6 + 5;
using ll = long long;
using namespace std;

vector<long long> layers[3];
vector<long long> sum[3];
map<int, int> mp[mxN];
int N, Q;
vector<ll> prefix, suffix;
void genLayers() {
  for(int i = 0; i < 3; i++) {
    if(i!=0) {
      for(int j = i; j < N; j++) {
        mp[i][j] = 1 - (mp[i-1][j] | mp[i][j-1]);
        mp[j][i] = 1 - (mp[j-1][i] | mp[j][i-1]);
      }
    }
    for(int j = N - 1; j >= i; --j) layers[i].push_back(mp[j][i]);
    for(int j = i + 1; j < N; j++) layers[i].push_back(mp[i][j]);
    ///got my layer
    ///generate the sum
    sum[i] = layers[i];
    for(int j = 1; j < layers[i].size(); j++) {
      sum[i][j] += sum[i][j-1];
    }
  }
  prefix = layers[2];
  suffix = layers[2];
  reverse(suffix.begin(), suffix.end());
  for(int i = 0; i < prefix.size(); i++) {
    prefix[i] *= i;
    if(i)prefix[i]+=prefix[i-1];
    suffix[i] *= i;
    if(i)suffix[i]+=suffix[i-1];
  }
}
int getLayerIndex(int x, int y) {
    int layer = min(x, y);
    if(y == layer) {
        return N - x - 1;
    }   else {
        return (N - layer - 1) + (y - layer);
    }

}
int getSum(int lay, int l, int r) {return sum[lay][r]-sum[lay][l]+layers[lay][l];} 
ll calcPrefixProjection(int l, int r) {
  return prefix[r] - (l == 0 ? 0 : prefix[l-1]) - 1ll * getSum(2, l, r) * (l - 1);
}
ll calcSuffixProjection(int l, int r) {
  int orgL = l, orgR = r;
  tie(l, r) = make_pair(layers[2].size()-r-1,layers[2].size()-l-1);
  return suffix[r] - (l == 0 ? 0 : suffix[l-1]) - 1ll * getSum(2, orgL, orgR) * (l - 1);  
}
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) {

    N = X.size();
    vector<int> layer(N * 2 - 1);
    for(int i = 0; i < N; i++) {
      mp[0][i] = X[i];
    }
    for(int i = 0; i < N; i++) {
      mp[i][0] = Y[i];
    }

    genLayers();

    vector<long long> ans;
    auto tmpB = B;
    for(int i = 0; i < T.size(); i++) {
        ///Rows A to C
        ///Columns B to D
        int A = T[i], C = tmpB[i];
        int B = L[i], D = R[i];
        long long total = 0;


        for (int i = 0; i < 2; ++i) {
            if (A == i && B == i) { ///both row and column
                total += getSum(i, N - 1 - C, (N-1-i) + (D-i));
                ++A, ++B;
            } else if (A == i) {  ///only row
                total += getSum(i, N - 1 - i + (B-i), N - 1 - i + (D-i));
                ++A;
            } else if (B == i) {  ///only column
                total += getSum(i, N - 1 - C, N - 1 - A);
                ++B;
            }
            if (A > C || B > D) break;
        }

        if (A <= C && B <= D) {
          ///The submatrix is divided into 3 parts
          ///1. increasing prefix from 1 to x
          ///2. decreasing suffix from 1 to x
          ///3. constant shit
          int l, r, offset;
          {
            int x = C, y = B;
            int projDistance = min(x-2,y-2);
            int px = x - projDistance, py = y - projDistance;
            int prefixL = getLayerIndex(px, py);
            int prefixR = prefixL + min(C-A,D-B)-1;
            if(prefixL <= prefixR) {
              total += calcPrefixProjection(prefixL, prefixR);
            }
            l = prefixR + 1;
            offset = (prefixR-prefixL+2);
          }
          {
            int x = A, y = D;
            int projDistance = min(x-2,y-2);
            int px = x - projDistance, py = y - projDistance;
            int prefixR = getLayerIndex(px, py);
            int prefixL = prefixR - min(C-A,D-B) + 1;
            if(prefixL <= prefixR) {
              total += calcSuffixProjection(prefixL, prefixR);
            }
            r = prefixL - 1;
          }
          if(l <= r) {
            total += 1ll*getSum(2, l, r) * offset;
          }
        }

        ans.push_back(total);
    }
    
    return ans;
}

Compilation message (stderr)

mosaic.cpp: In function 'void genLayers()':
mosaic.cpp:27:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int j = 1; j < layers[i].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~~~~
mosaic.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(int i = 0; i < prefix.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
mosaic.cpp: In function 'std::vector<long long int> mosaic(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
mosaic.cpp:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i = 0; i < T.size(); i++) {
      |                    ~~^~~~~~~~~~

• 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