oj.uz

Submission #421378

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

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

int sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
    if (r<nodel||l>noder) {
        return 0;
    }
    if (l<=nodel&&noder<=r) {
        return seg[node];
    }
    int mid=(nodel+noder)/2;
    return sum(l,r,node*2,nodel,mid)+sum(l,r,node*2+1,mid+1,noder);
}

void update(int i,int val) {
    i+=sz;
    seg[i]=val;
    while (i>1) {
        i/=2;
        seg[i]=seg[i*2]+seg[i*2+1];
    }
}

int cal(vector<int> v) {
    int ret=0;
    vector<int> pr;
    for(int i=0;i<v.size();i++) {
        pr.push_back(v[i]);
    }
    sort(pr.begin(),pr.end());
    pr.erase(unique(pr.begin(),pr.end()),pr.end());
    memset(seg,0,sizeof(seg));
    for(int i=0;i<v.size();i++) {
        int val=lower_bound(pr.begin(),pr.end(),v[i])-pr.begin();
        ret=max(ret,sum(val+1,sz-1));
        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:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i=0;i<v.size();i++) {
      |                 ~^~~~~~~~~
bubblesort2.cpp:38:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i=0;i<v.size();i++) {
      |                 ~^~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 356 KB Output is correct
2 Correct 190 ms 368 KB Output is correct
3 Correct 1060 ms 416 KB Output is correct
4 Correct 1082 ms 412 KB Output is correct
5 Correct 1100 ms 416 KB Output is correct
6 Correct 844 ms 412 KB Output is correct
7 Correct 922 ms 408 KB Output is correct
8 Correct 990 ms 452 KB Output is correct
9 Correct 1024 ms 408 KB Output is correct
10 Correct 882 ms 408 KB Output is correct
11 Correct 889 ms 420 KB Output is correct
12 Correct 886 ms 420 KB Output is correct
13 Correct 901 ms 408 KB Output is correct
14 Correct 882 ms 420 KB Output is correct
15 Correct 881 ms 412 KB Output is correct
16 Correct 865 ms 420 KB Output is correct
17 Correct 901 ms 412 KB Output is correct
18 Correct 924 ms 416 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 356 KB Output is correct
2 Correct 190 ms 368 KB Output is correct
3 Correct 1060 ms 416 KB Output is correct
4 Correct 1082 ms 412 KB Output is correct
5 Correct 1100 ms 416 KB Output is correct
6 Correct 844 ms 412 KB Output is correct
7 Correct 922 ms 408 KB Output is correct
8 Correct 990 ms 452 KB Output is correct
9 Correct 1024 ms 408 KB Output is correct
10 Correct 882 ms 408 KB Output is correct
11 Correct 889 ms 420 KB Output is correct
12 Correct 886 ms 420 KB Output is correct
13 Correct 901 ms 408 KB Output is correct
14 Correct 882 ms 420 KB Output is correct
15 Correct 881 ms 412 KB Output is correct
16 Correct 865 ms 420 KB Output is correct
17 Correct 901 ms 412 KB Output is correct
18 Correct 924 ms 416 KB Output is correct
19 Execution timed out 9022 ms 588 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9063 ms 1108 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 356 KB Output is correct
2 Correct 190 ms 368 KB Output is correct
3 Correct 1060 ms 416 KB Output is correct
4 Correct 1082 ms 412 KB Output is correct
5 Correct 1100 ms 416 KB Output is correct
6 Correct 844 ms 412 KB Output is correct
7 Correct 922 ms 408 KB Output is correct
8 Correct 990 ms 452 KB Output is correct
9 Correct 1024 ms 408 KB Output is correct
10 Correct 882 ms 408 KB Output is correct
11 Correct 889 ms 420 KB Output is correct
12 Correct 886 ms 420 KB Output is correct
13 Correct 901 ms 408 KB Output is correct
14 Correct 882 ms 420 KB Output is correct
15 Correct 881 ms 412 KB Output is correct
16 Correct 865 ms 420 KB Output is correct
17 Correct 901 ms 412 KB Output is correct
18 Correct 924 ms 416 KB Output is correct
19 Execution timed out 9022 ms 588 KB Time limit exceeded
20 Halted 0 ms 0 KB -