Submission #1221985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221985		hyakup	Mosaic (IOI24_mosaic)	C++20	0 / 100	83 ms	23880 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int maxn = 2e5 + 10;

vector<ll> mosaic(vector<int> x, vector<int> y, vector<int> t, vector<int> b, vector<int> l, vector<int> r ){
  int n = x.size(), q = t.size();

  if( n == 1 ) return vector<ll>(q, x[0]);

  vector<ll> sx(n), sy(n), sum(2*maxn), cont(2*maxn), marcx(n), marcy(n);
  sx[0] = sy[0] = x[0];
  if( x[1] == 0 && y[1] == 0 ){
    marcx[0] = marcy[0] = true;
    cont[maxn] = 1;
  }

  if( n > 2 && x[2] == 0 && y[1] == 1 ){
    marcx[1] = true;
    cont[maxn - 1] = 1;
    sum[maxn - 1] = -1;
  }

  if( n > 2 && x[1] == 1 && y[2] == 0 ){
    marcy[1] = true;
    cont[maxn + 1] = 1;
    sum[maxn + 1] = 1;
  }

  for( int i = 1; i < n; i++ ){
    sx[i] = sx[i - 1] + x[i];
    sy[i] = sy[i - 1] + y[i];

    if( i + 1 < n ){
      if( x[i] == 1 && x[i + 1] == 0 ) sum[maxn - i] = -i, cont[maxn - i] = 1, marcx[i] = true;
      else if( i - 2 >= 0 && marcx[i - 2] && x[i + 1] == 0 ) sum[maxn - i] = -i, cont[maxn - i] = 1, marcx[i] = true;

      if( y[i] == 1 && y[i + 1] == 0 ) sum[maxn + i] = i, cont[maxn + i] = 1, marcy[i] = true;
      else if( i - 2 >= 0 && marcy[i - 2] && y[i + 1] == 0 ) sum[maxn + i] = i, cont[maxn + i] = 1, marcy[i] = true;
    }
  }

  for( int i = 1; i < (int)sum.size(); i++ ){
    sum[i] += sum[i - 1];
    cont[i] += cont[i - 1];
  }

  auto query = [&]( ll l, ll r, ll val, ll t ){
    if( l > r ) return 0LL;
    return val*(cont[r] - cont[l - 1]) + t*(sum[r] - sum[l - 1]);
  };


  vector<ll> resp(q);
  for( int i = 0; i < q; i++ ){
    if( t[i] == 0 ) resp[i] = x[r[i]];
    else if( l[i] == 0 ) resp[i] = y[t[i]];
    else if( cont[maxn + b[i] - r[i]] - cont[maxn + b[i] - r[i] - 1] > 0 ) resp[i] = 1; 

    // if( t[i] == 0 && l[i] == 0 ) resp[i] = x[0];
    // if( t[i] == 0 ) resp[i] += sx[r[i]] - sx[max(0, l[i] - 1)];
    // if( l[i] == 0 ) resp[i] += sy[b[i]] - sy[max(0, t[i] - 1)];
    //
    // t[i] = max( t[i], 1 );
    // l[i] = max( l[i], 1 );
    //
    // if( t[i] > b[i] || l[i] > r[i] ) continue;
    //
    // ll L = min(b[i] - r[i], t[i] - l[i]);
    // ll R = max(b[i] - r[i], t[i] - l[i]);
    //
    // resp[i] += query( maxn + L, maxn + R, min(b[i] - t[i] + 1, r[i] - l[i] + 1), 0 );
    // resp[i] += query( maxn + R + 1, maxn + b[i] - l[i], b[i] - l[i] + 1, -1 );
    // resp[i] += query( maxn + t[i] - r[i], maxn + L - 1, r[i] - t[i] + 1, 1);
  }
  return resp;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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