oj.uz

Submission #421374

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

const int INF=1e9+1;
const int sz=2048;
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 62 ms 204 KB Output is correct
2 Correct 177 ms 332 KB Output is correct
3 Correct 981 ms 408 KB Output is correct
4 Correct 985 ms 420 KB Output is correct
5 Correct 976 ms 408 KB Output is correct
6 Correct 771 ms 332 KB Output is correct
7 Correct 842 ms 412 KB Output is correct
8 Correct 941 ms 416 KB Output is correct
9 Correct 970 ms 408 KB Output is correct
10 Correct 799 ms 404 KB Output is correct
11 Correct 809 ms 404 KB Output is correct
12 Correct 795 ms 404 KB Output is correct
13 Correct 832 ms 412 KB Output is correct
14 Correct 797 ms 460 KB Output is correct
15 Correct 798 ms 400 KB Output is correct
16 Correct 789 ms 404 KB Output is correct
17 Correct 781 ms 408 KB Output is correct
18 Correct 768 ms 400 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 204 KB Output is correct
2 Correct 177 ms 332 KB Output is correct
3 Correct 981 ms 408 KB Output is correct
4 Correct 985 ms 420 KB Output is correct
5 Correct 976 ms 408 KB Output is correct
6 Correct 771 ms 332 KB Output is correct
7 Correct 842 ms 412 KB Output is correct
8 Correct 941 ms 416 KB Output is correct
9 Correct 970 ms 408 KB Output is correct
10 Correct 799 ms 404 KB Output is correct
11 Correct 809 ms 404 KB Output is correct
12 Correct 795 ms 404 KB Output is correct
13 Correct 832 ms 412 KB Output is correct
14 Correct 797 ms 460 KB Output is correct
15 Correct 798 ms 400 KB Output is correct
16 Correct 789 ms 404 KB Output is correct
17 Correct 781 ms 408 KB Output is correct
18 Correct 768 ms 400 KB Output is correct
19 Runtime error 5 ms 1100 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 204 KB Output is correct
2 Correct 177 ms 332 KB Output is correct
3 Correct 981 ms 408 KB Output is correct
4 Correct 985 ms 420 KB Output is correct
5 Correct 976 ms 408 KB Output is correct
6 Correct 771 ms 332 KB Output is correct
7 Correct 842 ms 412 KB Output is correct
8 Correct 941 ms 416 KB Output is correct
9 Correct 970 ms 408 KB Output is correct
10 Correct 799 ms 404 KB Output is correct
11 Correct 809 ms 404 KB Output is correct
12 Correct 795 ms 404 KB Output is correct
13 Correct 832 ms 412 KB Output is correct
14 Correct 797 ms 460 KB Output is correct
15 Correct 798 ms 400 KB Output is correct
16 Correct 789 ms 404 KB Output is correct
17 Correct 781 ms 408 KB Output is correct
18 Correct 768 ms 400 KB Output is correct
19 Runtime error 5 ms 1100 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -