Submission #1242380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242380		mychecksedad	Mosaic (IOI24_mosaic)	C++20	100 / 100	918 ms	84508 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 = 4e5+100;


vi D, DD;
ll T[4*N], sum[4*N], TT[4*N], prefX[N], prefY[N], ANS[N*2], pref2[N];
int sz[4*N];
vector<pii> qp[N];

void build(int l, int r, int k){
  if(l == r){
    T[k] = DD[l-1];
    TT[k] = DD[l-1];
    sum[k] = DD[l-1];
    sz[k] = 1;
  }else{
    int mid = l+r>>1;
    build(l, mid, k<<1);
    build(mid+1, r, k<<1|1);
    T[k] = T[k<<1|1] + T[k<<1] + sz[k<<1|1] * sum[k<<1];
    TT[k] = TT[k<<1|1] + TT[k<<1] + sz[k<<1] * sum[k<<1|1];
    sum[k] = sum[k<<1] + sum[k<<1|1];
    sz[k] = sz[k<<1] + sz[k<<1|1];
  }
}
void upd(int l, int r, int p, int k, int val){
  if(l == r){
    T[k] = val;
    TT[k] = val;
    sum[k] = val;
    sz[k] = 1;
    return;
  }
  int mid = l+r>>1;
  if(p <= mid) upd(l, mid, p, k<<1, val);
  else upd(mid+1, r, p, k<<1|1, val);
  T[k] = T[k<<1|1] + T[k<<1] + sz[k<<1|1] * sum[k<<1];
  TT[k] = TT[k<<1|1] + TT[k<<1] + sz[k<<1] * sum[k<<1|1];
  sum[k] = sum[k<<1] + sum[k<<1|1];
  sz[k] = sz[k<<1] + sz[k<<1|1];
}
array<ll, 3> get(int l, int r, int ql, int qr, int k){
  if(ql > r || l > qr) return array<ll, 3>{0, 0, 0};
  if(ql <= l && r <= qr){
    return {T[k], sum[k], sz[k]};
  }
  int mid = l+r>>1;
  array<ll, 3> p = get(l, mid, ql, qr, k<<1);
  array<ll, 3> q = get(mid+1, r, ql, qr, k<<1|1);
  if(q[2] == 0) return p;
  if(p[2] == 0) return q;
  q[1] = q[1] + p[1];
  q[0] = q[0] + p[0] + p[1] * q[2];
  q[2] = q[2] + p[2];
  return q;
}
array<ll, 3> get2(int l, int r, int ql, int qr, int k){
  if(ql > r || l > qr) return array<ll, 3>{0, 0, 0};
  if(ql <= l && r <= qr){
    return {TT[k], sum[k], sz[k]};
  }
  int mid = l+r>>1;
  array<ll, 3> p = get2(l, mid, ql, qr, k<<1);
  array<ll, 3> q = get2(mid+1, r, ql, qr, k<<1|1);
  if(q[2] == 0) return p;
  if(p[2] == 0) return q;
  p[1] = q[1] + p[1];
  p[0] = q[0] + p[0] + q[1] * p[2];
  p[2] = q[2] + p[2];
  return p;
}
ll get3(int l, int r, int ql, int qr, int k){
  if(ql > r || l > qr) return 0ll;
  if(ql <= l && r <= qr) return sum[k];
  int mid = l+r>>1;
  return get3(l, mid, ql, qr, k<<1) + get3(mid+1, r, ql, qr, k<<1|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) {
  int n = X.size();
  int q = T.size();
  vector<array<int, 3>> Q;

  int id = 0;
  function<int(int, int)> add_q = [&](int l, int r){
    Q.pb({l, r, id});
    ++id;
    return id-1;
  };

  if(n == 1){
    vector<ll> C(q, X[0]);
    return C;
  }
  prefX[0] = X[0];
  prefY[0] = Y[0];
  for(int i = 1; i < n; ++i) prefX[i] = prefX[i - 1] + X[i];
  for(int i = 1; i < n; ++i) prefY[i] = prefY[i - 1] + Y[i];

  for(int i = 0; i < q; ++i){
    qp[i].clear();
    int x1 = T[i], x2 = B[i];
    int y1 = L[i], y2 = R[i];
    qp[i].pb({add_q(x2, y2), 1});
    if(y1 > 0)
      qp[i].pb({add_q(x2, y1 - 1), -1});
    if(x1 > 0)
      qp[i].pb({add_q(x1 - 1, y2), -1});
    if(y1 > 0 && x1 > 0)
      qp[i].pb({add_q(x1 - 1, y1 - 1), 1});
  }

  D.clear();
  DD.clear();
  int last = Y[1];
  for(int i = 1; i < n; ++i){
    if(last == 0 && X[i] == 0) D.pb(1);
    else D.pb(0);
    last = D.back();
  }
  reverse(all(D));
  last = D.back();
  for(int i = 2; i < n; ++i){
    if(last == 0 && Y[i] == 0) D.pb(1);
    else D.pb(0);
    last = D.back();
  }

  pref2[0] = D[0];
  for(int i = 1; i < (int) D.size(); ++i) pref2[i] = pref2[i - 1] + D[i];

  if(n > 2){

    last = D[n-1];
    int cur = n-3;
    for(int i = 2; i < n; ++i, cur--){
      if(last == 0 && D[cur] == 0) DD.pb(1);
      else DD.pb(0);
      last = DD.back();
    }

    reverse(all(DD));
    last = DD.back();
    cur = n;
    for(int i = 3; i < n; ++i, cur++){
      if(last == 0 && D[cur] == 0) DD.pb(1);
      else DD.pb(0);
      last = DD.back();
    }
  }

  // id from 1 to 2*n-3
  if(n > 2){
    build(1, n * 2 - 5, 1);
  }

  // return vector<ll>(q, 0);
  int sz = 2*n-5;

  for(auto [x, y, ID]: Q){
    if(x == 0){
      ANS[ID] = prefX[y];
    }else if(y == 0){
      ANS[ID] = prefY[x];
    }else{
      ANS[ID] = prefX[y] + prefY[x] - X[0];
      // + something from the segtree...
      int row_id = n-2 + x-2;
      int col_id = n-2-y+2;
      int origin = n-2;

      ANS[ID] += pref2[n-1 + x-1 - 1] - (n-1-y+1 >= 2 ? pref2[n-1-y+1-2] : 0ll);
      if(x == 1 || y == 1){
        continue;
      }

      if(x == y){
        ANS[ID] += get(1, sz, origin, row_id, 1)[0];
        ANS[ID] += get2(1, sz, col_id, origin - 1, 1)[0];
      }else{
        ll mn = min(x, y) - 1;  
        ANS[ID] += get(1, sz, row_id - mn + 1, row_id, 1)[0];
        ANS[ID] += get2(1, sz, col_id, col_id + mn - 1, 1)[0];
        ANS[ID] += get3(1, sz, col_id + mn, row_id - mn, 1) * (mn);        
      }
    }
  }


  vector<ll> C(q);
  for(int i = 0; i < q; ++i){
    for(auto [ID, p]: qp[i]){
      C[i] += ANS[ID] * p;
    }
  }
  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