Submission #1228432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228432		spetr	Measures (CEOI22_measures)	C++20	0 / 100	457 ms	74236 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll mmod = 998244353;  
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>
const ll inf = 1e18;
vll tree;

void push(ll i){
  if (2*i+2 < tree.size()){
    tree[2*i+1][3] += tree[i][5];
    tree[2*i+1][4] += tree[i][5];
    tree[2*i+1][5] += tree[i][5];
    tree[2*i+2][3] += tree[i][5];
    tree[2*i+2][4] += tree[i][5];
    tree[2*i+2][5] += tree[i][5];
    tree[i][5] = 0;
  }
}
ll secti(ll l, ll r, ll L, ll R, ll i){
  push(i);

  if (r < L || l > R){
    return 0;
  }
  if (L>= l && r >= R){
    return tree[i][2];
  }

  ll mid = (L+R)/2;
  ll a = secti(l, r, L, mid, 2*i+1);
  ll b = secti(l, r, mid+1, R, 2*i+2);
  return a + b;
}

void update(ll i, ll c){
  vl positions;
  while (i != 0){
    positions.push_back(i);
    i--;
    i/=2;
  }
  positions.push_back(0);
  for (ll i = positions.size()-1; i >= 0; i--){
    push(positions[i]);
    tree[positions[i]][2]++;
    tree[positions[i]][3] = min(tree[positions[i]][3], c);
    tree[positions[i]][4] = max(tree[positions[i]][4], c);
  }
}

void pricti(ll l, ll r, ll L, ll R, ll c, ll i){
  push(i);

  if (r < L || l > R){
    return;
  }
  if (L>= l && r >= R){
    tree[i][3] += c;
    tree[i][4] += c;
    tree[i][5] += c;
    return;
  }

  ll mid = (L+R)/2;
  pricti(l, r, L, mid, c, 2*i+1);
  pricti(l, r, mid+1, R, c, 2*i+2);
}

ll najdi_minimum(ll l, ll r, ll L, ll R, ll i){
  push(i);

  if (r < L || l > R){
    return inf;
  }
  if (L>= l && r >= R){
    return tree[i][3];
  }

  ll mid = (L+R)/2;
  ll a = najdi_minimum(l, r, L, mid, 2*i+1);
  ll b = najdi_minimum(l, r, mid+1, R, 2*i+2);
  return min(a,b);
}

ll najdi_maximum(ll l, ll r, ll L, ll R, ll i){
  push(i);

  if (r < L || l > R){
    return -inf;
  }
  if (L>= l && r >= R){
    return tree[i][4];
  }

  ll mid = (L+R)/2;
  ll a = najdi_maximum(l, r, L, mid, 2*i+1);
  ll b = najdi_maximum(l, r, mid+1, R, 2*i+2);
  return max(a,b);
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, m, d;
    cin >> n >> m >> d;

    vl nums (n+m);
    set<ll> mnozina;

    for (ll i = 0; i < n + m; i++){cin >> nums[i]; mnozina.insert(nums[i]);}

    map<ll,ll> mapa;
    ll i = 0;
    for (ll x : mnozina){
      mapa[x] = i;
      i++;
    }

    vl pocty (mnozina.size(),0);
    vl index (mnozina.size(),0);

    for (ll i = 0; i < n+m; i++){
      pocty[mapa[nums[i]]] ++;
    }

    for (ll i = 0; i < mnozina.size()-1; i++){
      index[i+1] = index[i] + pocty[i];
    }

    ll velikost = 2; while (velikost < n+m){velikost*=2;}
     
    vl sorted (n+m); for (ll i = 0; i < nums.size(); i++){sorted[i] = nums[i];} sort(sorted.begin(), sorted.end());
    for (ll i = 0; i < n+m; i++){
      tree.push_back({sorted[i], sorted[i], 0, inf, -inf, 0});
    }
    while (tree.size() < velikost){
      tree.push_back({inf,inf,0,inf,-inf,0});
    }
    reverse(tree.begin(), tree.end());
    for (ll i = 0; i < tree.size()-1; i+=2){
      tree.push_back({tree[i][0], tree[i+1][1], 0, inf, -inf, 0});
    }
    reverse(tree.begin(), tree.end());

    for (ll i = 0; i < n+m; i++){
      ll pos = index[mapa[nums[i]]];
      index[mapa[nums[i]]]++;
      ll cnt = secti(0,max(0ll,pos-1),0,velikost-1,0);
      update(pos + velikost - 1, nums[i]-cnt*d);
      pricti(min(pos+1, velikost-1), velikost-1, 0, velikost-1, -d, 0);
      ll minimum = najdi_minimum(pos, velikost-1, 0, velikost-1, 0);
      ll maximum = najdi_maximum(0, pos, 0, velikost-1, 0);

      if (i > n-1){
        double delta = maximum - minimum;
        cout << 0.5*delta<< " ";
      }

    }


    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 35
• Subtask 4: 0 / 41