Submission #441185

#	Time	Username	Problem	Language	Result	Execution time	Memory
441185		peijar	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	4003 ms	189776 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = (1 << 21) + 1;

int iDeb[MAXN], iFin[MAXN], maxVal[MAXN], lazyAdd[MAXN];
set<int> ids[MAXN];
int curDelta[MAXN];

void pull(int iNoeud) {
  maxVal[iNoeud] = max(maxVal[2 * iNoeud], maxVal[2 * iNoeud + 1]);
}

void push(int iNoeud) {
  if (!lazyAdd[iNoeud])
    return;
  maxVal[iNoeud] += lazyAdd[iNoeud];
  if (iDeb[iNoeud] < iFin[iNoeud]) {
    lazyAdd[2 * iNoeud] += lazyAdd[iNoeud];
    lazyAdd[1 + 2 * iNoeud] += lazyAdd[iNoeud];
  } else {
    curDelta[iDeb[iNoeud]] += lazyAdd[iNoeud];
  }
  lazyAdd[iNoeud] = 0;
}

void buildTree(int iNoeud, int deb, int fin) {
  iDeb[iNoeud] = deb, iFin[iNoeud] = fin;
  maxVal[iNoeud] = -1e9;
  if (deb == fin)
    return;
  buildTree(2 * iNoeud, deb, (deb + fin) / 2);
  buildTree(2 * iNoeud + 1, (deb + fin) / 2 + 1, fin);
}

void change(int iNoeud, int value, int id, bool del) {
  push(iNoeud);
  if (iDeb[iNoeud] > value or iFin[iNoeud] < value)
    return;
  if (iDeb[iNoeud] == iFin[iNoeud]) {
    if (del)
      ids[value].erase(id);
    else
      ids[value].insert(id);
    maxVal[iNoeud] =
        (ids[value].empty() ? -1e9 : *ids[value].rbegin()) + curDelta[value];
    return;
  }
  change(2 * iNoeud, value, id, del);
  change(2 * iNoeud + 1, value, id, del);
  pull(iNoeud);
}

void add(int iNoeud, int deb, int fin, int val) {
  push(iNoeud);
  if (iDeb[iNoeud] > fin or iFin[iNoeud] < deb)
    return;
  if (iDeb[iNoeud] >= deb and iFin[iNoeud] <= fin) {
    lazyAdd[iNoeud] += val;
    push(iNoeud);
    return;
  }
  add(2 * iNoeud, deb, fin, val);
  add(1 + 2 * iNoeud, deb, fin, val);
  pull(iNoeud);
}

int query(int iNoeud, int deb, int fin) {
  push(iNoeud);
  if (deb > iFin[iNoeud] or fin < iDeb[iNoeud])
    return -1e9;
  if (deb <= iDeb[iNoeud] and fin >= iFin[iNoeud])
    return maxVal[iNoeud];
  return max(query(2 * iNoeud, deb, fin), query(2 * iNoeud + 1, deb, fin));
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
  vector<int> values;
  for (auto v : A)
    values.push_back(v);
  for (auto v : V)
    values.push_back(v);
  sort(values.begin(), values.end());
  values.resize(unique(values.begin(), values.end()) - values.begin());
  for (auto &v : A)
    v = lower_bound(values.begin(), values.end(), v) - values.begin();
  for (auto &v : V)
    v = lower_bound(values.begin(), values.end(), v) - values.begin();
  int nbVal = values.size();
  buildTree(1, 0, nbVal - 1);
  for (int i = 0; i < (int)A.size(); ++i)
    change(1, A[i], i + 1, false);
  for (int i = 0; i < (int)A.size(); ++i) {
    add(1, A[i], nbVal - 1, -1);
  }

  /*cout << "-------------\n";
  for (int k = 0; k < nbVal; ++k)
    cout << query(1, k, k) << ' ';
  cout << endl;
  for (int k = 0; k < (int)A.size(); ++k)
    cout << curDelta[k] << ' ';
  cout << endl;
  for (int k = 0; k < nbVal; ++k)
    cout << (ids[k].empty() ? -1 : *ids[k].rbegin()) << ' ';
  cout << endl;*/
  int Q = X.size();
  vector<int> answer(Q);
  for (int j = 0; j < Q; j++) {
    add(1, A[X[j]], nbVal - 1, 1);
    change(1, A[X[j]], X[j] + 1, true);
    change(1, V[j], X[j] + 1, false);
    A[X[j]] = V[j];
    add(1, A[X[j]], nbVal - 1, -1);
    /*cout << "-------------\n";
    for (int k = 0; k < nbVal; ++k)
      cout << query(1, k, k) << ' ';
    cout << endl;
    for (int k = 0; k < (int)A.size(); ++k)
      cout << curDelta[k] << ' ';
    cout << endl;
    for (int k = 0; k < nbVal; ++k)
      cout << (ids[k].empty() ? -1 : *ids[k].rbegin()) << ' ';
    cout << endl;*/
    answer[j] = query(1, 0, nbVal - 1);
  }
  return answer;
}

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40