Submission #1108603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108603		VinhLuu	Bubble Sort 2 (JOI18_bubblesort2)	C++17	38 / 100	9041 ms	10772 KiB

bubblesort2

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

const int N = 1e6 + 5;

int n, q, a[N], _x[N], _y[N], kq[N];

namespace sub1{
  int b[N];
  vector<int> solve(){
    vector<int> ans;
    for(int k = 1; k <= q; k ++){
      int x = _x[k], y = _y[k];
      a[x] = y;
      int cnt = 0;
      for(int i = 1; i <= n; i ++) b[i] = a[i];
      while(true){
        bool ff = true;
        for(int i = 1; i < n; i ++) if(b[i] > b[i + 1]){
          swap(b[i], b[i + 1]);
          ff = false;
        }
        if(ff) break;
        cnt++;
      }
//      for(int i = 1; i <= n; i ++) cerr << a[i] << " ";
//      cerr << "   " << cnt << " x\n";
      ans.push_back(cnt);
    }
    return ans;
  }
}

namespace sub2{
  int affect[N];
  vector<int> solve(){
    vector<int> ans;
    for(int i = 1; i < n; i ++){
      for(int j = i + 1; j <= n; j ++){
        affect[j] += (a[i] > a[j]);
      }
    }
    for(int k = 1; k <= q; k ++){
      int x = _x[k], y = _y[k];
      int cnt = 0;
      for(int i = x + 1; i <= n; i ++) if(a[x] > a[i]) affect[i]--;
      a[x] = y;
      affect[x] = 0;
      for(int i = 1; i < x; i ++) if(a[i] > a[x]) affect[x]++;
      for(int i = x + 1; i <= n; i ++) if(a[x] > a[i]) affect[i]++;
      int mx = 0;
      for(int i = 1; i <= n; i ++) mx = max(mx, affect[i]);
      ans.push_back(mx);
    }
    return ans;
  }
}

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
  n = A.size();
  for(int i = 0; i < n; i ++) a[i + 1] = A[i];

  q = X.size();

  for(int k = 0; k < q; k ++){
    _x[k + 1] = X[k] + 1, _y[k + 1] = V[k];
  }

  return sub2 :: solve();
//  return sub1 :: solve();



  int ans = 0;

	std::vector<int> answer(q);
	for(int j = 0; j < q; j ++) {
		answer[j] = kq[j];
	}
	return answer;
}

//#define LOCAL

#ifdef LOCAL

int _n, _q;

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

	cin >> _n >> _q;

	std::vector<int> A(_n);
  for(int i = 0; i < _n; i ++)
    cin >> A[i];

	std::vector<int> X(_q),V(_q);
	for(int j = 0; j < _q ; j++){
		cin >> X[j] >> V[j];
	}


	std::vector<int> res=countScans(A,X,V);

	for(int j=0;j<int(res.size());j++)
		cout << res[j] << "\n";
}

/*
4 2
1 2 3 4
0 3
2 1
*/

#endif // LOCAL

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> sub2::solve()':
bubblesort2.cpp:47:11: warning: unused variable 'cnt' [-Wunused-variable]
   47 |       int cnt = 0;
      |           ^~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:76:7: warning: unused variable 'ans' [-Wunused-variable]
   76 |   int ans = 0;
      |       ^~~

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