제출 #1228622

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228622		spetr	Measures (CEOI22_measures)	C++20	100 / 100	754 ms	76812 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 = 1e16;
vll tree;


void oprava(ll i){
  if (2*i+2 < tree.size()){
    tree[i][3] = min(tree[2*i+1][3], tree[2*i+2][3]);
    tree[i][4] = max(tree[2*i+1][4], tree[2*i+2][4]);
  }
}

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;
    oprava(i);
  }
}

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 j = positions.size()-1; j >= 0; j--){
    push(positions[j]);
  }
  for (ll j = 0; j < positions.size(); j++){
    tree[positions[j]][2]++;
    tree[positions[j]][3] = min(tree[positions[j]][3], c);
    tree[positions[j]][4] = max(tree[positions[j]][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);
  oprava(i);
}

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+1][0], tree[i][1], 0, inf, -inf, 0});
    }
    reverse(tree.begin(), tree.end());
    ll delta = 0;
    for (ll i = 0; i < n+m; i++){
      ll pos = index[mapa[nums[i]]];
      index[mapa[nums[i]]]++;
      ll cnt = secti(0,pos,0,velikost-1,0) + 1;
      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);
      delta = max(maximum - minimum,delta);
      if (i > n-1){
        cout << delta/2;
        if (delta%2 == 1) cout << ".5";
        cout << " ";
      }

    }


    return 0;
}

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