Submission #1242290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242290		mychecksedad	Mosaic (IOI24_mosaic)	C++20	0 / 100	127 ms	34096 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 = 2e5+100;

ll T[4*N], sum[4*N], TT[4*N];
int sz[4*N];

void build(int l, int r, int k){
  if(l == r){
    T[k] = 0;
    TT[k] = 0;
    sum[k] = 0;
    sz[k] = 1;
  }else{
    int mid = l+r>>1;
    build(l, mid, k<<1);
    build(mid+1, r, k<<1|1);
    TT[k] = 0;
    T[k] = 0;
    sum[k] = 0;
    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;
  array<ll, 3> res;
  res[1] = q[1] + p[1];
  res[0] = q[0] + p[0] + p[1] * q[2];
  res[2] = q[2] + p[2];
  return res;
}
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;
  array<ll, 3> res;
  res[1] = q[1] + p[1];
  res[0] = q[0] + p[0] + q[1] * p[2];
  res[2] = q[2] + p[2];
  return res;
}
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();
  build(1, n * 2, 1);
  vector<vector<pii>> qp(q);
  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;
  };

  for(int i = 0; i < q; ++i){
    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});
  }

  if(n == 1){
    vector<ll> C(q, X[0]);
    assert(false);
    return C;
  }

  vector<ll> ANS(id);

  vector<ll> prefX(n);
  vector<ll> prefY(n);
  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];

  vi D;
  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();
  }
  // id from 1 to 2*n-3
  for(int i = 1; i <= 2*n-3; ++i){
    upd(1, 2*n, i, 1, D[i-1]);
    cerr << D[i-1] << ' ';
  }
  cerr <<" arran\n\n\n";

  // for(int x: D) cerr << x << ' ';

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

  int p = 0;
  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-1 + x-1;
      int col_id = n-1-y+1;
      int origin = n-1;
      if(x == y){
        // cerr << row_id << ' ' << col_id << " pf\n";
        // cerr << get2(1, sz, origin, row_id, 1)[1] << ' ' << get2(1, sz, origin, row_id, 1)[2] << " f\n";
        ANS[ID] += get(1, sz, origin, row_id, 1)[0];
        ANS[ID] += get2(1, sz, col_id, origin - 1, 1)[0];
      }else{
        int mn = min(x, y);  
        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;
      cerr << ID << ' ' << ANS[ID] << " crap\n";
    }
    cerr << '\n';
  }
  return C;
}

• 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