oj.uz

답안 #851752

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
851752 2023-09-20T14:19:28 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 2128 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;
      auto y = S.upper_bound(A[j]);
			if(y != S.end()) x = S.size() - S.order_of_key(*y);
			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

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 480 KB Output is correct
2 Correct 221 ms 508 KB Output is correct
3 Correct 1430 ms 848 KB Output is correct
4 Correct 1457 ms 912 KB Output is correct
5 Correct 1380 ms 652 KB Output is correct
6 Correct 1242 ms 660 KB Output is correct
7 Correct 1310 ms 912 KB Output is correct
8 Correct 1362 ms 652 KB Output is correct
9 Correct 1381 ms 660 KB Output is correct
10 Correct 1113 ms 864 KB Output is correct
11 Correct 1113 ms 848 KB Output is correct
12 Correct 1134 ms 656 KB Output is correct
13 Correct 1154 ms 848 KB Output is correct
14 Correct 1146 ms 660 KB Output is correct
15 Correct 1129 ms 664 KB Output is correct
16 Correct 1129 ms 908 KB Output is correct
17 Correct 1156 ms 908 KB Output is correct
18 Correct 1200 ms 904 KB Output is correct

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 480 KB Output is correct
2 Correct 221 ms 508 KB Output is correct
3 Correct 1430 ms 848 KB Output is correct
4 Correct 1457 ms 912 KB Output is correct
5 Correct 1380 ms 652 KB Output is correct
6 Correct 1242 ms 660 KB Output is correct
7 Correct 1310 ms 912 KB Output is correct
8 Correct 1362 ms 652 KB Output is correct
9 Correct 1381 ms 660 KB Output is correct
10 Correct 1113 ms 864 KB Output is correct
11 Correct 1113 ms 848 KB Output is correct
12 Correct 1134 ms 656 KB Output is correct
13 Correct 1154 ms 848 KB Output is correct
14 Correct 1146 ms 660 KB Output is correct
15 Correct 1129 ms 664 KB Output is correct
16 Correct 1129 ms 908 KB Output is correct
17 Correct 1156 ms 908 KB Output is correct
18 Correct 1200 ms 904 KB Output is correct
19 Execution timed out 9069 ms 1508 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 9011 ms 2128 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 480 KB Output is correct
2 Correct 221 ms 508 KB Output is correct
3 Correct 1430 ms 848 KB Output is correct
4 Correct 1457 ms 912 KB Output is correct
5 Correct 1380 ms 652 KB Output is correct
6 Correct 1242 ms 660 KB Output is correct
7 Correct 1310 ms 912 KB Output is correct
8 Correct 1362 ms 652 KB Output is correct
9 Correct 1381 ms 660 KB Output is correct
10 Correct 1113 ms 864 KB Output is correct
11 Correct 1113 ms 848 KB Output is correct
12 Correct 1134 ms 656 KB Output is correct
13 Correct 1154 ms 848 KB Output is correct
14 Correct 1146 ms 660 KB Output is correct
15 Correct 1129 ms 664 KB Output is correct
16 Correct 1129 ms 908 KB Output is correct
17 Correct 1156 ms 908 KB Output is correct
18 Correct 1200 ms 904 KB Output is correct
19 Execution timed out 9069 ms 1508 KB Time limit exceeded
20 Halted 0 ms 0 KB -