oj.uz

Submission #94081

# Submission time Handle Problem Language Result Execution time Memory
94081 2019-01-15T19:49:20 Z tincamatei Bubble Sort 2 (JOI18_bubblesort2) C++14
17 / 100
 167 ms 1756 KB 
#include <bits/stdc++.h>
#include "bubblesort2.h"

using namespace std;

const int MAX_N = 2000;

vector<int> a, poz;
int smen[MAX_N+1];

bool cmp(int x, int y) {
  return a[x] < a[y] || (a[x] == a[y] && x < y);
}

int getInv(int n) {
  int right = -1;
  sort(poz.begin(), poz.end(), cmp);

  for(int i = 0; i <= n; ++i)
    smen[i] = 0;

  for(int i = 0; i < n; ++i) {
    right = max(right, poz[i]);
    if(right > poz[i]) {
      smen[poz[i]]++;
      smen[right]--;
    }
  }

  int p = 0;
  int rez = 0;
  for(int i = 0; i < n; ++i) {
    p += smen[i];
    rez = max(rez, p);
  }

  return rez;
}

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
  int n, q;

  a = A;
  q = X.size();

  std::vector<int> rez(q);
  n = A.size();

  for(int i = 0; i < n; ++i)
    poz.push_back(i);

  for(int i = 0; i < q; ++i) {
    a[X[i]] = V[i];
    rez[i] = getInv(n);
  }
  return rez;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 376 KB Output is correct
2 Correct 29 ms 504 KB Output is correct
3 Correct 166 ms 504 KB Output is correct
4 Correct 166 ms 504 KB Output is correct
5 Correct 166 ms 504 KB Output is correct
6 Correct 162 ms 504 KB Output is correct
7 Correct 167 ms 504 KB Output is correct
8 Correct 164 ms 504 KB Output is correct
9 Correct 165 ms 528 KB Output is correct
10 Correct 161 ms 488 KB Output is correct
11 Correct 160 ms 504 KB Output is correct
12 Correct 163 ms 504 KB Output is correct
13 Correct 164 ms 604 KB Output is correct
14 Correct 163 ms 504 KB Output is correct
15 Correct 165 ms 488 KB Output is correct
16 Correct 166 ms 512 KB Output is correct
17 Correct 167 ms 504 KB Output is correct
18 Correct 167 ms 504 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 376 KB Output is correct
2 Correct 29 ms 504 KB Output is correct
3 Correct 166 ms 504 KB Output is correct
4 Correct 166 ms 504 KB Output is correct
5 Correct 166 ms 504 KB Output is correct
6 Correct 162 ms 504 KB Output is correct
7 Correct 167 ms 504 KB Output is correct
8 Correct 164 ms 504 KB Output is correct
9 Correct 165 ms 528 KB Output is correct
10 Correct 161 ms 488 KB Output is correct
11 Correct 160 ms 504 KB Output is correct
12 Correct 163 ms 504 KB Output is correct
13 Correct 164 ms 604 KB Output is correct
14 Correct 163 ms 504 KB Output is correct
15 Correct 165 ms 488 KB Output is correct
16 Correct 166 ms 512 KB Output is correct
17 Correct 167 ms 504 KB Output is correct
18 Correct 167 ms 504 KB Output is correct
19 Runtime error 6 ms 1144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 1756 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 376 KB Output is correct
2 Correct 29 ms 504 KB Output is correct
3 Correct 166 ms 504 KB Output is correct
4 Correct 166 ms 504 KB Output is correct
5 Correct 166 ms 504 KB Output is correct
6 Correct 162 ms 504 KB Output is correct
7 Correct 167 ms 504 KB Output is correct
8 Correct 164 ms 504 KB Output is correct
9 Correct 165 ms 528 KB Output is correct
10 Correct 161 ms 488 KB Output is correct
11 Correct 160 ms 504 KB Output is correct
12 Correct 163 ms 504 KB Output is correct
13 Correct 164 ms 604 KB Output is correct
14 Correct 163 ms 504 KB Output is correct
15 Correct 165 ms 488 KB Output is correct
16 Correct 166 ms 512 KB Output is correct
17 Correct 167 ms 504 KB Output is correct
18 Correct 167 ms 504 KB Output is correct
19 Runtime error 6 ms 1144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -