oj.uz

Submission #850800

# Submission time Handle Problem Language Result Execution time Memory
850800 2023-09-17T13:08:33 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 2304 KB 
#include <bits/stdc++.h>
#define all(v) ((v).begin(),(v).end())
#define ll long long
#define F first
#define S second
const ll mod = 1e9 + 7;
const ll mxN = 1e5 + 2;
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T>
using indexed_set = tree<T,null_type,less<T>,rb_tree_tag, tree_order_statistics_node_update>;

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

vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
	int Q=X.size();
	int N = A.size();
	set<pair<int,int>>s;
	vector<int>ans;
	for(int i = 0; i < Q;i++){
		A[X[i]] = V[i];
		s.clear();
		int x = 0;
		indexed_set<int>S;
		for(int j = 0;j < N;j++){
			int x = 0;
			if(S.upper_bound(A[j]) != S.end()) x = S.size() - S.order_of_key(*(S.upper_bound(A[j])));
			s.insert({x,j});
			S.insert(A[j]);
		}
		auto y = s.end();
		y--;
		ans.push_back((*y).first);
	}
	return ans;
}
// 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 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:32:7: warning: unused variable 'x' [-Wunused-variable]
   32 |   int x = 0;
      |       ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 344 KB Output is correct
2 Correct 259 ms 348 KB Output is correct
3 Correct 1653 ms 848 KB Output is correct
4 Correct 1639 ms 1208 KB Output is correct
5 Correct 1597 ms 1108 KB Output is correct
6 Correct 1455 ms 856 KB Output is correct
7 Correct 1540 ms 956 KB Output is correct
8 Correct 1590 ms 856 KB Output is correct
9 Correct 1631 ms 712 KB Output is correct
10 Correct 1273 ms 936 KB Output is correct
11 Correct 1289 ms 944 KB Output is correct
12 Correct 1333 ms 848 KB Output is correct
13 Correct 1314 ms 848 KB Output is correct
14 Correct 1301 ms 600 KB Output is correct
15 Correct 1251 ms 940 KB Output is correct
16 Correct 1297 ms 600 KB Output is correct
17 Correct 1255 ms 940 KB Output is correct
18 Correct 1391 ms 848 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 344 KB Output is correct
2 Correct 259 ms 348 KB Output is correct
3 Correct 1653 ms 848 KB Output is correct
4 Correct 1639 ms 1208 KB Output is correct
5 Correct 1597 ms 1108 KB Output is correct
6 Correct 1455 ms 856 KB Output is correct
7 Correct 1540 ms 956 KB Output is correct
8 Correct 1590 ms 856 KB Output is correct
9 Correct 1631 ms 712 KB Output is correct
10 Correct 1273 ms 936 KB Output is correct
11 Correct 1289 ms 944 KB Output is correct
12 Correct 1333 ms 848 KB Output is correct
13 Correct 1314 ms 848 KB Output is correct
14 Correct 1301 ms 600 KB Output is correct
15 Correct 1251 ms 940 KB Output is correct
16 Correct 1297 ms 600 KB Output is correct
17 Correct 1255 ms 940 KB Output is correct
18 Correct 1391 ms 848 KB Output is correct
19 Execution timed out 9058 ms 1684 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 9014 ms 2304 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 344 KB Output is correct
2 Correct 259 ms 348 KB Output is correct
3 Correct 1653 ms 848 KB Output is correct
4 Correct 1639 ms 1208 KB Output is correct
5 Correct 1597 ms 1108 KB Output is correct
6 Correct 1455 ms 856 KB Output is correct
7 Correct 1540 ms 956 KB Output is correct
8 Correct 1590 ms 856 KB Output is correct
9 Correct 1631 ms 712 KB Output is correct
10 Correct 1273 ms 936 KB Output is correct
11 Correct 1289 ms 944 KB Output is correct
12 Correct 1333 ms 848 KB Output is correct
13 Correct 1314 ms 848 KB Output is correct
14 Correct 1301 ms 600 KB Output is correct
15 Correct 1251 ms 940 KB Output is correct
16 Correct 1297 ms 600 KB Output is correct
17 Correct 1255 ms 940 KB Output is correct
18 Correct 1391 ms 848 KB Output is correct
19 Execution timed out 9058 ms 1684 KB Time limit exceeded
20 Halted 0 ms 0 KB -