oj.uz

Submission #421434

# Submission time Handle Problem Language Result Execution time Memory
421434 2021-06-09T07:15:52 Z 조영욱(#7654) Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 2112 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;

const int INF=1e9+1;
const int sz=8192;
int tree[sz*2];

int sum(int i) {
    int ret=0;
    while (i>0) {
        ret+=tree[i];
        i-=(i&-i);
    }
    return ret;
}

void update(int i,int x) {
    while (i<sz) {
        tree[i]+=x;
        i+=(i&-i);
    }
}

int cal(vector<int> v) {
    int ret=0;
    vector<int> pr;
    for(int i=0;i<v.size();i++) {
        pr.push_back(v[i]);
    }
    pr.push_back(-1);
    sort(pr.begin(),pr.end());
    pr.erase(unique(pr.begin(),pr.end()),pr.end());
    memset(tree,0,sizeof(tree));
    for(int i=0;i<v.size();i++) {
        int val=lower_bound(pr.begin(),pr.end(),v[i])-pr.begin();
        ret=max(ret,sum(sz-1)-sum(val));
        update(val,1);
    }
    return ret;
}

vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
	int q=X.size();
	vector<int> ret(q);
	for (int j=0;j<q;j++) {
		A[X[j]]=V[j];
		ret[j]=cal(A);
	}
	return ret;
}

Compilation message

bubblesort2.cpp: In function 'int cal(std::vector<int>)':
bubblesort2.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=0;i<v.size();i++) {
      |                 ~^~~~~~~~~
bubblesort2.cpp:35:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i=0;i<v.size();i++) {
      |                 ~^~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 384 KB Output is correct
2 Correct 105 ms 332 KB Output is correct
3 Correct 674 ms 420 KB Output is correct
4 Correct 668 ms 420 KB Output is correct
5 Correct 670 ms 412 KB Output is correct
6 Correct 522 ms 412 KB Output is correct
7 Correct 573 ms 420 KB Output is correct
8 Correct 596 ms 412 KB Output is correct
9 Correct 664 ms 416 KB Output is correct
10 Correct 553 ms 408 KB Output is correct
11 Correct 559 ms 412 KB Output is correct
12 Correct 586 ms 412 KB Output is correct
13 Correct 629 ms 412 KB Output is correct
14 Correct 569 ms 412 KB Output is correct
15 Correct 578 ms 416 KB Output is correct
16 Correct 534 ms 412 KB Output is correct
17 Correct 589 ms 408 KB Output is correct
18 Correct 687 ms 412 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 384 KB Output is correct
2 Correct 105 ms 332 KB Output is correct
3 Correct 674 ms 420 KB Output is correct
4 Correct 668 ms 420 KB Output is correct
5 Correct 670 ms 412 KB Output is correct
6 Correct 522 ms 412 KB Output is correct
7 Correct 573 ms 420 KB Output is correct
8 Correct 596 ms 412 KB Output is correct
9 Correct 664 ms 416 KB Output is correct
10 Correct 553 ms 408 KB Output is correct
11 Correct 559 ms 412 KB Output is correct
12 Correct 586 ms 412 KB Output is correct
13 Correct 629 ms 412 KB Output is correct
14 Correct 569 ms 412 KB Output is correct
15 Correct 578 ms 416 KB Output is correct
16 Correct 534 ms 412 KB Output is correct
17 Correct 589 ms 408 KB Output is correct
18 Correct 687 ms 412 KB Output is correct
19 Execution timed out 9047 ms 588 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7298 ms 1000 KB Output is correct
2 Execution timed out 9029 ms 2112 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 384 KB Output is correct
2 Correct 105 ms 332 KB Output is correct
3 Correct 674 ms 420 KB Output is correct
4 Correct 668 ms 420 KB Output is correct
5 Correct 670 ms 412 KB Output is correct
6 Correct 522 ms 412 KB Output is correct
7 Correct 573 ms 420 KB Output is correct
8 Correct 596 ms 412 KB Output is correct
9 Correct 664 ms 416 KB Output is correct
10 Correct 553 ms 408 KB Output is correct
11 Correct 559 ms 412 KB Output is correct
12 Correct 586 ms 412 KB Output is correct
13 Correct 629 ms 412 KB Output is correct
14 Correct 569 ms 412 KB Output is correct
15 Correct 578 ms 416 KB Output is correct
16 Correct 534 ms 412 KB Output is correct
17 Correct 589 ms 408 KB Output is correct
18 Correct 687 ms 412 KB Output is correct
19 Execution timed out 9047 ms 588 KB Time limit exceeded
20 Halted 0 ms 0 KB -