Submission #884045

#	Time	Username	Problem	Language	Result	Execution time	Memory
884045		vjudge1	Bubble Sort 2 (JOI18_bubblesort2)	C++17	38 / 100	9013 ms	3696 KiB

bubblesort2

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int const NMAX = 5e5;
int arr[1 + NMAX];

int const MMAX = 1e6;
int aib[1 + MMAX];

void update(int pos, int add, int m) {
  //cerr << "Update : ";
  for(int i = pos;i <= m;i = 2 * i - (i & (i-1))) {
    //cerr << i << ' ';
    aib[i] += add;
  }
  //cerr << ";\n";
}

int query(int pos, int m) {
  int ans = 0;
  //cerr << "Query : ";
  for(int i = pos;i > 0;i = (i & (i-1))) {
    ans += aib[i];
    //cerr << i << ' ';
  }
  //cerr << ";\n";
  return ans;
}

int solve(int n, int m) {
  for(int i = 0;i <= m;i++) {
    aib[i] = 0;
  }
  int ans = 0;
  //cerr << "  ";
  for(int i = 0;i < n;i++) {
    //cerr << arr[i] << ' ';
    ans = max(ans, (query(m, m) - query(arr[i], m)));
    update(arr[i], 1, m);
  }
  //cerr << "\n";
  return ans;
}

vector <int> countScans(vector <int> vec, vector <int> pos, vector <int> val) {
  // Normalize
  //cerr << "Normalize ... must be bad\n";
  vector <int> all;
  for(int i = 0;i < vec.size();i++){
    all.push_back(vec[i]);
  }
  for(int i = 0;i < val.size();i++){
    all.push_back(val[i]);
  }
  sort(all.begin(), all.end());
  all.erase(unique(all.begin(), all.end()), all.end());

  map <int, int> norm;
  for(int i = 0;i < all.size();i++) {
    norm[all[i]] = i+1;
  }
  int n = vec.size();
  for(int i = 0;i < vec.size();i++) {
    vec[i] = norm[vec[i]];
    arr[i] = vec[i];
  }
  for(int i = 0;i < val.size();i++) {
    val[i] = norm[val[i]];
  }
  //cerr << "Normalize Accepted : Failed Solve\n";
  // Solve
  vector <int> ans;
  int t = pos.size();

  for(int q = 0;q < t;q++) {
    arr[pos[q]] = val[q];
    //cerr << "  Can't solve this\n";
    ans.push_back(solve(n, all.size()));
  }
  return ans;
}
/*
void test() {
  int n, t;
  cin >> n >> t;
  vector <int> vec, pos, val;
  vector <int> ans;
  for(int i = 0;i < n;i++) {
    int c;
    cin >> c;
    vec.push_back(c);
  }
  for(int i = 0;i < t;i++) {
    int c1, c2;
    cin >> c1 >> c2;
    pos.push_back(c1);
    val.push_back(c2);
  }
  ans = countScans(vec, pos, val);
  for(int i = 0;i < ans.size();i++) {
    cout << ans[i] << ' ';
  }
}
/*
Example:
4 2
1 2 3 4
0 3
2 1

5 4
2 2 2 2 1
0 2
4 5
0 6
1 6

int main() {

  test();
  return 0;
}
*/

Compilation message (stderr)

bubblesort2.cpp:108:1: warning: "/*" within comment [-Wcomment]
  108 | /*
      |  
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:53:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int i = 0;i < vec.size();i++){
      |                 ~~^~~~~~~~~~~~
bubblesort2.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for(int i = 0;i < val.size();i++){
      |                 ~~^~~~~~~~~~~~
bubblesort2.cpp:63:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int i = 0;i < all.size();i++) {
      |                 ~~^~~~~~~~~~~~
bubblesort2.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for(int i = 0;i < vec.size();i++) {
      |                 ~~^~~~~~~~~~~~
bubblesort2.cpp:71:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   for(int i = 0;i < val.size();i++) {
      |                 ~~^~~~~~~~~~~~

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