Submission #1218219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218219		nikd	Mosaic (IOI24_mosaic)	C++20	7 / 100	105 ms	58308 KiB

mosaic

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

struct seg{
  int n; 

  struct node{
    int l; int r; ll sm; ll v;
  };
  node merge(node a, node b){
    if(a.l == -1) return b;
    if(a.l > b.l) swap(a, b);
    return node{a.l, b.r, a.sm+b.sm, a.v+b.v+b.sm*(b.l-a.r)};
  }
  vector<node> t;

  seg(vector<int> &a): n(a.size()){
    t.resize(2*n);
    for(int i = n; i<2*n; i++) t[i] = node{i-n, i-n, a[i-n], a[i-n]};
    for(int i = n-1; i>0; i--) t[i] = merge(t[i << 1], t[(i << 1) | 1]);
  }

  node q(int l, int r){
    node res{-1, -1, -1, -1};
    for(l+=n, r+= n; l<=r; l>>=1, r>>=1){
      if(l&1) res = merge(res, t[l++]);
      if(!(r&1)) res = merge(res, t[r--]);
    }
    return res;
  }
};


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

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

  if(n == 2){
    vector<vector<int>> mt(2, vector<int>(2));
    mt[0] = x;
    mt[1][0] = y[1];
    mt[1][1] = !(x[1] | y[1]);

    vector<ll> sl(n, 0);
    for(int j = 0; j<q; j++){
      for(int i = t[j]; i<=b[j]; i++){
        for(int k = l[j]; k<=r[j]; k++){
          sl[j] += mt[i][j];
        }
      }
    }
    return sl;
  }

  vector<int> xx(n-1);
  xx[0] = !(x[1] | y[1]);
  for(int i = 1; i<n-1; i++) xx[i] = !(xx[i-1] | x[i+1]);

  vector<int> yy(n-2); 
  yy[0] = !(xx[0] | y[2]);
  for(int i = 1; i<n-2; i++) yy[i] = !(yy[i-1] | y[i+2]);

  vector<int> tr(2*n-5);
  tr[n-3] = !(xx[1] | yy[0]);

  for(int i = n-2; i<2*n-5; i++) tr[i] = !(tr[i-1] | xx[i-n+4]);
  for(int i = n-4; i>=0; i--) tr[i] = !(tr[i+1] | yy[n-3-i]);

  vector<ll> px(n, 0);
  vector<ll> py(n, 0);
  vector<ll> pxx(n, 0);
  vector<ll> pyy(n, 0);
  px[0] = x[0]; 
  py[0] = x[0]; py[1] = py[0]+y[0]; 
  pxx[0] = y[0]; pxx[1] = pxx[0]+xx[0]; 
  pyy[0] = x[1]; pyy[1] = pyy[0]+xx[0]; pyy[2] = pyy[1]+yy[0];
  for(int i = 1; i<n; i++) px[i] = px[i-1]+x[i];
  for(int i = 2; i<n; i++) py[i] = py[i-1]+y[i-1];
  for(int i = 2; i<n; i++) pxx[i] = pxx[i-1] +xx[i-1];
  for(int i = 3; i<n; i++) pyy[i] = pyy[i-1] + yy[i-2];

  seg diag(tr);
  reverse(tr.begin(), tr.end());
  seg rdiag(tr);
  reverse(tr.begin(), tr.end());

  vector<ll> sol(q, 0);
  for(int i = 0; i<q; i++){
    if(t[i] == 0){
      sol[i] += px[r[i]]-(l[i] ? px[l[i]-1]: 0);
      t[i]++;
    }
    if(t[i] > b[i]) continue;
    if(t[i] == 1){
      sol[i] += pxx[r[i]]-(l[i] ? pxx[l[i]-1]: 0);
      t[i]++;
    }
    if(t[i] > b[i]) continue;
    if(l[i] == 0){
      sol[i] += py[b[i]]-(t[i] ? py[t[i]-1]: 0);
      l[i]++;
    }
    if(l[i] > r[i]) continue;
    if(l[i] == 1){
      sol[i] += pyy[b[i]]-(t[i] ? pyy[t[i]-1]: 0);
      l[i]++;
    }
    if(l[i] > r[i]) continue;

    if(b[i]-t[i] == r[i]- l[i]){
      // angolo1 {l, t}
      // angolo2 {l, b}
      ll k = diag.q(l[i]-b[i]+n-3, l[i]-t[i]+n-3).v;
      if(b[i] == t[i]) assert(k == tr[l[i]-b[i] +n-3]);
      sol[i] += k;
      if(b[i]-t[i] > 0) sol[i] += rdiag.q(2*n-6 - (r[i]-t[i]+n-3), 2*n-6 -(l[i]-t[i]+n-2)).v;
    }

    if(b[i]-t[i] < r[i]-l[i]){
      sol[i] += diag.q(l[i]-b[i]+n-3, l[i]-t[i]+n-3).v;
      sol[i] += rdiag.q(2*n-6 - (r[i]-t[i]+n-3), 2*n-6 -(r[i]-b[i]+n-3)).v;
      if(b[i]-t[i] + 1 <r[i]-l[i]){
        ll tmp =  diag.q(l[i]-t[i]+n-2, r[i]-b[i]+n-4).sm;
        tmp *= (r[i]-l[i]-b[i]+t[i]-1);
        sol[i] += tmp;
      }
    }

    if(r[i]-l[i] < b[i]-t[i]){
      sol[i] += diag.q(l[i]-b[i]+n-3, r[i]-b[i]+n-3).v;
      sol[i] += rdiag.q(2*n-6 - (r[i]-t[i]+n-3), 2*n-6 -(l[i]-t[i]+n-3)).v;
      if(r[i]-l[i] + 1 <b[i]-t[i]){
        ll tmp =  diag.q(r[i]-b[i]+n-2, l[i]-t[i]+n-4).sm;
        tmp *= (b[i]-t[i]-r[i]+l[i]-1);
        sol[i] += tmp;
      }
    }
  }
  return sol;
}

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