Submission #886998

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
886998	2023-12-13 12:10:42	amirhoseinfar1385	Bubble Sort 2 (JOI18_bubblesort2)	C++17	60 / 100	9033 ms	5184 KiB

bubblesort2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include "bubblesort2.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10;
int dp[maxn],n,q,maxa;
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
  n=A.size(),q=X.size(),maxa=0;
  for(int i=0;i<n;i++){
    int ted=0;
    for(int j=i-1;j>=0;j--){
      ted+=A[j]>A[i]?1:0;
    } 
    dp[i]=ted;
    maxa=maxa>ted?maxa:ted;
  }
  vector<int>ret(q);
  for(int i=0;i<q;i++){
    int ind=X[i],w=V[i];
    for(int j=ind+1;j<n;j++){
      dp[j]+=A[ind]>A[j]?-1:0;
    }
    dp[ind]=0;
    A[ind]=w;
    for(int j=ind-1;j>=0;j--){
      dp[ind]+=A[j]>A[ind]?1:0;
    }
    for(int j=ind+1;j<n;j++){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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