답안 #883999

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
883999 2023-12-06T14:04:58 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
0 / 100
1020 ms 2908 KB
#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";
}

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

long long solve(int n, int m) {
  for(int i = 1;i <= m;i++) {
    aib[i] = 0;
  }
  long long 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 <long long> 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 <long long> 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 <long long> 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

4 4
1 2 3 4
0 5
1 5
2 5
3 5

int main() {

  test();
  return 0;
}
*/

Compilation message

bubblesort2.cpp:109:1: warning: "/*" within comment [-Wcomment]
  109 | /*
      |  
bubblesort2.cpp: In function 'std::vector<long long 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++) {
      |                 ~~^~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1020 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -