oj.uz

Submission #1013533

# Submission time Handle Problem Language Result Execution time Memory
1013533 2024-07-03T15:34:14 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
100 / 100
 2735 ms 162052 KB 
// #include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
using pii=pair<int,int>;

#define pb push_back
#define all(v) v.begin(),v.end()
vector<int> a;
int n;
struct Node{
	int val=0;
	int lazy=0;
	Node* left,*right;
	Node() : left(nullptr),right(nullptr) {}
};
Node* root;
void build(Node* node,int l,int r){
	if(l==r) return;
	int mid=(l+r)/2;
	node->left=new Node();
	node->right=new Node();
	build(node->left,l,mid);
	build(node->right,mid+1,r);
}
void push(Node* node,int l,int r){
	if(node->lazy==0) return;
	node->val+=node->lazy;
	if(node->left) {
		node->left->lazy+=node->lazy;
	}
	if(node->right) {
		node->right->lazy+=node->lazy;
	}
	node->lazy=0;
}
void update(Node* node,int l,int r,int ql,int qr,int x){
	push(node,l,r);
	if(ql>r||qr<l) return;
	if(ql<=l&&r<=qr){
		node->lazy+=x;
		push(node,l,r);
		return;
	}
	int mid=(l+r)/2;
	update(node->left,l,mid,ql,qr,x);
	update(node->right,mid+1,r,ql,qr,x);
	push(node,l,r);
	node->val=max(node->left->val,node->right->val);
}

vector<int> countScans(vector<int> A,vector<int> x,vector<int> y){
	a=A;
	root=new Node();
	n=a.size();
	int q=x.size();
	build(root,0,n+q);
	vector<pii> v;
	for(int i=0;i<n;i++){
		v.pb({a[i],i});
	}
	for(int i=0;i<q;i++){
		v.pb({y[i],x[i]});
	}
	sort(all(v));
	map<pii,int> mp;
	for(int i=0;i<n+q;i++){
		mp[v[i]]=i;
	}
	for(int i=0;i<n;i++){
		a[i]=mp[{a[i],i}];
	}
	for(int i=0;i<q;i++){
		y[i]=mp[{y[i],x[i]}];
	}
	vector<int> Ans(q);
	int sz=n+q;
	auto ch  = [&](int i,int x){
		update(root,0,sz,a[i],a[i],i*x);
		update(root,0,sz,a[i]+1,sz,-x);
	};
	for(int i=0;i<n;i++){
		ch(i,1);
	}
	for(int i=0;i<q;i++){
		ch(x[i],-1);
		a[x[i]]=y[i];
		ch(x[i],1);
		Ans[i]=root->val;
	}
	
	return Ans;
}



#ifdef IOI
// #include "bubblesort2.h"

// #include <cstdio>
// #include <cstdlib>
// #include <vector>

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();
	
	vector<int> A(N);
	for(int i=0;i<N;i++)
		A[i]=readInt();
	
	vector<int> X(Q),V(Q);
	for(int j=0;j<Q;j++){
		X[j]=readInt();
		V[j]=readInt();
	}
	
	vector<int> res=countScans(A,X,V);
	
	for(int j=0;j<int(res.size());j++)
		printf("%d\n",res[j]);
}

#endif

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 3 ms 860 KB Output is correct
4 Correct 4 ms 1036 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 3 ms 860 KB Output is correct
9 Correct 5 ms 860 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 3 ms 856 KB Output is correct
12 Correct 3 ms 1004 KB Output is correct
13 Correct 3 ms 860 KB Output is correct
14 Correct 4 ms 988 KB Output is correct
15 Correct 3 ms 860 KB Output is correct
16 Correct 3 ms 860 KB Output is correct
17 Correct 3 ms 860 KB Output is correct
18 Correct 3 ms 860 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 3 ms 860 KB Output is correct
4 Correct 4 ms 1036 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 3 ms 860 KB Output is correct
9 Correct 5 ms 860 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 3 ms 856 KB Output is correct
12 Correct 3 ms 1004 KB Output is correct
13 Correct 3 ms 860 KB Output is correct
14 Correct 4 ms 988 KB Output is correct
15 Correct 3 ms 860 KB Output is correct
16 Correct 3 ms 860 KB Output is correct
17 Correct 3 ms 860 KB Output is correct
18 Correct 3 ms 860 KB Output is correct
19 Correct 14 ms 2428 KB Output is correct
20 Correct 17 ms 2652 KB Output is correct
21 Correct 16 ms 2796 KB Output is correct
22 Correct 17 ms 2652 KB Output is correct
23 Correct 16 ms 2652 KB Output is correct
24 Correct 15 ms 2648 KB Output is correct
25 Correct 15 ms 2524 KB Output is correct
26 Correct 15 ms 2612 KB Output is correct
27 Correct 14 ms 2396 KB Output is correct
28 Correct 14 ms 2456 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4568 KB Output is correct
2 Correct 84 ms 9808 KB Output is correct
3 Correct 117 ms 15024 KB Output is correct
4 Correct 122 ms 15048 KB Output is correct
5 Correct 111 ms 15044 KB Output is correct
6 Correct 122 ms 14896 KB Output is correct
7 Correct 118 ms 15044 KB Output is correct
8 Correct 117 ms 14944 KB Output is correct
9 Correct 122 ms 15048 KB Output is correct
10 Correct 109 ms 12324 KB Output is correct
11 Correct 102 ms 12228 KB Output is correct
12 Correct 95 ms 12232 KB Output is correct
13 Correct 85 ms 12228 KB Output is correct
14 Correct 103 ms 12232 KB Output is correct
15 Correct 95 ms 12236 KB Output is correct
16 Correct 87 ms 12236 KB Output is correct
17 Correct 111 ms 12240 KB Output is correct
18 Correct 94 ms 12320 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 3 ms 860 KB Output is correct
4 Correct 4 ms 1036 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 3 ms 860 KB Output is correct
9 Correct 5 ms 860 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 3 ms 856 KB Output is correct
12 Correct 3 ms 1004 KB Output is correct
13 Correct 3 ms 860 KB Output is correct
14 Correct 4 ms 988 KB Output is correct
15 Correct 3 ms 860 KB Output is correct
16 Correct 3 ms 860 KB Output is correct
17 Correct 3 ms 860 KB Output is correct
18 Correct 3 ms 860 KB Output is correct
19 Correct 14 ms 2428 KB Output is correct
20 Correct 17 ms 2652 KB Output is correct
21 Correct 16 ms 2796 KB Output is correct
22 Correct 17 ms 2652 KB Output is correct
23 Correct 16 ms 2652 KB Output is correct
24 Correct 15 ms 2648 KB Output is correct
25 Correct 15 ms 2524 KB Output is correct
26 Correct 15 ms 2612 KB Output is correct
27 Correct 14 ms 2396 KB Output is correct
28 Correct 14 ms 2456 KB Output is correct
29 Correct 24 ms 4568 KB Output is correct
30 Correct 84 ms 9808 KB Output is correct
31 Correct 117 ms 15024 KB Output is correct
32 Correct 122 ms 15048 KB Output is correct
33 Correct 111 ms 15044 KB Output is correct
34 Correct 122 ms 14896 KB Output is correct
35 Correct 118 ms 15044 KB Output is correct
36 Correct 117 ms 14944 KB Output is correct
37 Correct 122 ms 15048 KB Output is correct
38 Correct 109 ms 12324 KB Output is correct
39 Correct 102 ms 12228 KB Output is correct
40 Correct 95 ms 12232 KB Output is correct
41 Correct 85 ms 12228 KB Output is correct
42 Correct 103 ms 12232 KB Output is correct
43 Correct 95 ms 12236 KB Output is correct
44 Correct 87 ms 12236 KB Output is correct
45 Correct 111 ms 12240 KB Output is correct
46 Correct 94 ms 12320 KB Output is correct
47 Correct 498 ms 44512 KB Output is correct
48 Correct 2358 ms 147992 KB Output is correct
49 Correct 2670 ms 161872 KB Output is correct
50 Correct 2484 ms 161956 KB Output is correct
51 Correct 2522 ms 161876 KB Output is correct
52 Correct 2735 ms 161784 KB Output is correct
53 Correct 2545 ms 162028 KB Output is correct
54 Correct 2314 ms 161972 KB Output is correct
55 Correct 2471 ms 161976 KB Output is correct
56 Correct 2114 ms 161972 KB Output is correct
57 Correct 2294 ms 162052 KB Output is correct
58 Correct 2225 ms 161984 KB Output is correct
59 Correct 1998 ms 153016 KB Output is correct
60 Correct 1995 ms 152880 KB Output is correct
61 Correct 2074 ms 152996 KB Output is correct
62 Correct 2017 ms 148716 KB Output is correct
63 Correct 1881 ms 148816 KB Output is correct
64 Correct 1834 ms 148992 KB Output is correct
65 Correct 1876 ms 144760 KB Output is correct
66 Correct 1894 ms 144716 KB Output is correct
67 Correct 1974 ms 144756 KB Output is correct