oj.uz

Submission #335807

# Submission time Handle Problem Language Result Execution time Memory
335807 2020-12-14T03:29:19 Z Mo_TOI_I_am_Garbage Bubble Sort 2 (JOI18_bubblesort2) C++14
17 / 100
 9000 ms 3688 KB 
#include "bubblesort2.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> pos;
int bit[500050];
void add(int x, int d)
{
	while(x)
	{
		bit[x] += d;
		x -= x & -x;
	}
}
int search(int x)
{
	int res = 0;
	while(x <= pos.size())
	{
		res += bit[x];
		x += x & -x;
	}
	return res;
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
	for(int x : A) pos.push_back(x);
	for(int x : V) pos.push_back(x);
	pos.push_back(-1e9);
	sort(pos.begin(), pos.end());
	pos.resize(unique(pos.begin(), pos.end()) - pos.begin());
	vector<int> res;
	for(int i=0; i < (int)X.size(); i ++)
	{
		memset(bit, 0, sizeof(bit));
		int ans = 0;
		A[X[i]] = V[i];
		for(int j=0; j < (int)A.size(); j ++)
		{
			int ind = lower_bound(pos.begin(), pos.end(), A[j]) - pos.begin(); 
			ans = max(ans, search(ind + 1));
			add(ind, 1);
		}
		res.push_back(ans);
	}
	return res;
}


// int readInt(){
// 	int i;
// 	if(scanf("%d",&i)!=1){
// 		fprintf(stderr,"Error while reading input\n");
// 		exit(1);
// 	}
// 	return i;
// }

// int main(){
// 	int N,Q;
// 	N=readInt();
// 	Q=readInt();
	
// 	std::vector<int> A(N);
// 	for(int i=0;i<N;i++)
// 		A[i]=readInt();
	
// 	std::vector<int> X(Q),V(Q);
// 	for(int j=0;j<Q;j++){
// 		X[j]=readInt();
// 		V[j]=readInt();
// 	}

// 	std::vector<int> res=countScans(A,X,V);
	

// 	for(int j=0;j<int(res.size());j++)
// 		printf("%d\n",res[j]);
// }

Compilation message

bubblesort2.cpp: In function 'int search(int)':
bubblesort2.cpp:17:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  while(x <= pos.size())
      |        ~~^~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 2284 KB Output is correct
2 Correct 125 ms 2436 KB Output is correct
3 Correct 549 ms 2540 KB Output is correct
4 Correct 566 ms 2456 KB Output is correct
5 Correct 540 ms 2540 KB Output is correct
6 Correct 442 ms 2412 KB Output is correct
7 Correct 460 ms 2540 KB Output is correct
8 Correct 485 ms 2412 KB Output is correct
9 Correct 547 ms 2540 KB Output is correct
10 Correct 455 ms 2540 KB Output is correct
11 Correct 484 ms 2540 KB Output is correct
12 Correct 463 ms 2540 KB Output is correct
13 Correct 488 ms 2448 KB Output is correct
14 Correct 535 ms 2412 KB Output is correct
15 Correct 478 ms 2412 KB Output is correct
16 Correct 480 ms 2448 KB Output is correct
17 Correct 480 ms 2448 KB Output is correct
18 Correct 473 ms 2448 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 2284 KB Output is correct
2 Correct 125 ms 2436 KB Output is correct
3 Correct 549 ms 2540 KB Output is correct
4 Correct 566 ms 2456 KB Output is correct
5 Correct 540 ms 2540 KB Output is correct
6 Correct 442 ms 2412 KB Output is correct
7 Correct 460 ms 2540 KB Output is correct
8 Correct 485 ms 2412 KB Output is correct
9 Correct 547 ms 2540 KB Output is correct
10 Correct 455 ms 2540 KB Output is correct
11 Correct 484 ms 2540 KB Output is correct
12 Correct 463 ms 2540 KB Output is correct
13 Correct 488 ms 2448 KB Output is correct
14 Correct 535 ms 2412 KB Output is correct
15 Correct 478 ms 2412 KB Output is correct
16 Correct 480 ms 2448 KB Output is correct
17 Correct 480 ms 2448 KB Output is correct
18 Correct 473 ms 2448 KB Output is correct
19 Correct 7104 ms 2788 KB Output is correct
20 Execution timed out 9073 ms 2796 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3506 ms 2920 KB Output is correct
2 Execution timed out 9052 ms 3688 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 2284 KB Output is correct
2 Correct 125 ms 2436 KB Output is correct
3 Correct 549 ms 2540 KB Output is correct
4 Correct 566 ms 2456 KB Output is correct
5 Correct 540 ms 2540 KB Output is correct
6 Correct 442 ms 2412 KB Output is correct
7 Correct 460 ms 2540 KB Output is correct
8 Correct 485 ms 2412 KB Output is correct
9 Correct 547 ms 2540 KB Output is correct
10 Correct 455 ms 2540 KB Output is correct
11 Correct 484 ms 2540 KB Output is correct
12 Correct 463 ms 2540 KB Output is correct
13 Correct 488 ms 2448 KB Output is correct
14 Correct 535 ms 2412 KB Output is correct
15 Correct 478 ms 2412 KB Output is correct
16 Correct 480 ms 2448 KB Output is correct
17 Correct 480 ms 2448 KB Output is correct
18 Correct 473 ms 2448 KB Output is correct
19 Correct 7104 ms 2788 KB Output is correct
20 Execution timed out 9073 ms 2796 KB Time limit exceeded
21 Halted 0 ms 0 KB -