oj.uz

Submission #421435

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

const int INF=1e9+1;
const int sz=8192;
int tree[sz*2];
vector<int> pr;

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;
    memset(tree,0,sizeof(tree));
    for(int i=0;i<v.size();i++) {
        ret=max(ret,sum(sz-1)-sum(v[i]));
        update(v[i],1);
    }
    return ret;
}

vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
	int q=X.size();
	vector<int> ret(q);
	pr.push_back(-1);
	for(int i=0;i<A.size();i++) {
        pr.push_back(A[i]);
	}
	for(int i=0;i<q;i++) {
        pr.push_back(V[i]);
	}
	sort(pr.begin(),pr.end());
	pr.erase(unique(pr.begin(),pr.end()),pr.end());
	for(int i=0;i<A.size();i++) {
        A[i]=lower_bound(pr.begin(),pr.end(),A[i])-pr.begin();
	}
	for(int i=0;i<q;i++) {
        V[i]=lower_bound(pr.begin(),pr.end(),V[i])-pr.begin();
	}
	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:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=0;i<v.size();i++) {
      |                 ~^~~~~~~~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i=0;i<A.size();i++) {
      |              ~^~~~~~~~~
bubblesort2.cpp:48:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i=0;i<A.size();i++) {
      |              ~^~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 388 KB Output is correct
2 Correct 33 ms 372 KB Output is correct
3 Correct 207 ms 420 KB Output is correct
4 Correct 171 ms 420 KB Output is correct
5 Correct 165 ms 424 KB Output is correct
6 Correct 158 ms 428 KB Output is correct
7 Correct 199 ms 420 KB Output is correct
8 Correct 166 ms 420 KB Output is correct
9 Correct 166 ms 332 KB Output is correct
10 Correct 160 ms 432 KB Output is correct
11 Correct 164 ms 420 KB Output is correct
12 Correct 176 ms 424 KB Output is correct
13 Correct 161 ms 332 KB Output is correct
14 Correct 159 ms 428 KB Output is correct
15 Correct 166 ms 420 KB Output is correct
16 Correct 171 ms 424 KB Output is correct
17 Correct 179 ms 428 KB Output is correct
18 Correct 194 ms 428 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 388 KB Output is correct
2 Correct 33 ms 372 KB Output is correct
3 Correct 207 ms 420 KB Output is correct
4 Correct 171 ms 420 KB Output is correct
5 Correct 165 ms 424 KB Output is correct
6 Correct 158 ms 428 KB Output is correct
7 Correct 199 ms 420 KB Output is correct
8 Correct 166 ms 420 KB Output is correct
9 Correct 166 ms 332 KB Output is correct
10 Correct 160 ms 432 KB Output is correct
11 Correct 164 ms 420 KB Output is correct
12 Correct 176 ms 424 KB Output is correct
13 Correct 161 ms 332 KB Output is correct
14 Correct 159 ms 428 KB Output is correct
15 Correct 166 ms 420 KB Output is correct
16 Correct 171 ms 424 KB Output is correct
17 Correct 179 ms 428 KB Output is correct
18 Correct 194 ms 428 KB Output is correct
19 Incorrect 2027 ms 660 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2462 ms 844 KB Output is correct
2 Execution timed out 9060 ms 1608 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 388 KB Output is correct
2 Correct 33 ms 372 KB Output is correct
3 Correct 207 ms 420 KB Output is correct
4 Correct 171 ms 420 KB Output is correct
5 Correct 165 ms 424 KB Output is correct
6 Correct 158 ms 428 KB Output is correct
7 Correct 199 ms 420 KB Output is correct
8 Correct 166 ms 420 KB Output is correct
9 Correct 166 ms 332 KB Output is correct
10 Correct 160 ms 432 KB Output is correct
11 Correct 164 ms 420 KB Output is correct
12 Correct 176 ms 424 KB Output is correct
13 Correct 161 ms 332 KB Output is correct
14 Correct 159 ms 428 KB Output is correct
15 Correct 166 ms 420 KB Output is correct
16 Correct 171 ms 424 KB Output is correct
17 Correct 179 ms 428 KB Output is correct
18 Correct 194 ms 428 KB Output is correct
19 Incorrect 2027 ms 660 KB Output isn't correct
20 Halted 0 ms 0 KB -