oj.uz

Submission #58930

# Submission time Handle Problem Language Result Execution time Memory
58930 2018-07-19T20:33:31 Z khohko Bubble Sort 2 (JOI18_bubblesort2) C++17
100 / 100
 5835 ms 204296 KB 
#include<bits/stdc++.h>
#include "bubblesort2.h"
#pragma GCC optimize("O3")
using namespace std;
#define ll int
#define fr first
#define sc second
#define pb push_back
#define ARRS ((ll)(1e6+100))
#define MAX ((ll)(1e9+100))

ll fw[ARRS+100];

void add(ll i,ll x){
	i=ARRS-i;
	while(i<=ARRS+10){
		fw[i]+=x;
		i+=i&-i;
	}
}

ll quer(ll i){
	i=ARRS-i;
	ll p=0;
	while(i>0){
		p+=fw[i];
		i-=i&-i;
	}
	return p;
}

ll wl,wr,wx,wi;

struct node{
	node *L,*R;
	int x,s;
	node(){
		L=R=NULL;
		s=0;
		x=-MAX;
	}
	void updt(){
		x=-MAX;
		if(L)x=max(x,L->x);
		if(R)x=max(x,R->x);
	}
	void shep(ll y){
		s+=y;
		x+=y;
	}
	void shplit(){
		if(!L)L=new node();
		if(!R)R=new node();
		L->shep(s);
		R->shep(s);
		s=0;
	}
};

void updt(ll l,ll r,node *& x){
	if(wr<l||r-1<wl)return;
	if(!x)x=new node();
	if(wl<=l&&r-1<=wr){
		x->shep(wx);
		return;
	}
	x->shplit();
	updt(l,l+r>>1,x->L);
	updt(l+r>>1,r,x->R);
	x->updt();
}

void updt1(ll l,ll r,node *& x){
	if(wr<l||r-1<wl)return;
	if(!x)x=new node();
	if(wl<=l&&r-1<=wr){
		x->x=wx;
		x->s=0;
		return;
	}
	x->shplit();
	updt1(l,l+r>>1,x->L);
	updt1(l+r>>1,r,x->R);
	x->updt();
}

set<ll> mp[ARRS];

node *rt=NULL;

void up(ll x){
	if(mp[x].size()){
		wl=wr=x;
		wx=-(*mp[x].begin())+quer(x+1);
//		cout<<wl<<" "<<wx<<" "<<x<<" "<<(-*mp[x].begin())<<endl;
		updt1(-MAX,MAX,rt);
	}
	else {
		wl=wr=x;
		wx=-MAX;
		updt1(-MAX,MAX,rt);
	}
}

ll a[ARRS],n;
map<ll,ll> em;

void quer(ll i,ll x){

	mp[a[i]].erase(n-i-1);
	mp[x].insert(n-i-1);

	add(a[i],-1);
	add(x,1);

	up(x);
	up(a[i]);
	if(a[i]<=x){
		wl=a[i]+1;
		wr=x-1;
		wx=1;
	}
	else {
		wl=x+1;
		wr=a[i]-1;
		wx=-1;
	}
	updt(-MAX,MAX,rt);
	a[i]=x;
}


vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
	n=A.size();
	ll q=X.size();
	vector<int> PAS;
	vector<int> b;
	for(auto x:A)
		b.pb(x);
	for(auto x:V)
		b.pb(x);
	sort(b.begin(),b.end());
	ll C=1;
	for(int i=0; i<b.size(); i++){
		if(b[i]!=b[i-1]||!i)
			em[b[i]]=C++;
	}
	for(auto &x:A)
		x=em[x];
	for(auto &x:V)
		x=em[x];

	for(int i=0; i<n; i++){
		a[i]=A[i];
//		cout<<a[i]<<" ";

		add(a[i],1);
	}
	for(int i=0; i<n; i++){
		mp[a[i]].insert(n-i-1);
		up(a[i]);
	}
	//cout<<" ----> "<<rt->x<<endl;

	for(int i=0; i<q; i++){
		ll k=X[i];
		ll p=V[i];
		quer(k,p);
		PAS.pb(rt->x);
	}

	return PAS;
}

Compilation message

bubblesort2.cpp: In function 'void updt(int, int, node*&)':
bubblesort2.cpp:68:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  updt(l,l+r>>1,x->L);
         ~^~
bubblesort2.cpp:69:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  updt(l+r>>1,r,x->R);
       ~^~
bubblesort2.cpp: In function 'void updt1(int, int, node*&)':
bubblesort2.cpp:82:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  updt1(l,l+r>>1,x->L);
          ~^~
bubblesort2.cpp:83:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  updt1(l+r>>1,r,x->R);
        ~^~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:144:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<b.size(); i++){
               ~^~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 47480 KB Output is correct
2 Correct 60 ms 47592 KB Output is correct
3 Correct 56 ms 48032 KB Output is correct
4 Correct 53 ms 48108 KB Output is correct
5 Correct 56 ms 48108 KB Output is correct
6 Correct 51 ms 48132 KB Output is correct
7 Correct 65 ms 48252 KB Output is correct
8 Correct 48 ms 48252 KB Output is correct
9 Correct 55 ms 48252 KB Output is correct
10 Correct 57 ms 48252 KB Output is correct
11 Correct 58 ms 48252 KB Output is correct
12 Correct 67 ms 48252 KB Output is correct
13 Correct 59 ms 48252 KB Output is correct
14 Correct 57 ms 48252 KB Output is correct
15 Correct 54 ms 48252 KB Output is correct
16 Correct 53 ms 48252 KB Output is correct
17 Correct 67 ms 48252 KB Output is correct
18 Correct 54 ms 48252 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 47480 KB Output is correct
2 Correct 60 ms 47592 KB Output is correct
3 Correct 56 ms 48032 KB Output is correct
4 Correct 53 ms 48108 KB Output is correct
5 Correct 56 ms 48108 KB Output is correct
6 Correct 51 ms 48132 KB Output is correct
7 Correct 65 ms 48252 KB Output is correct
8 Correct 48 ms 48252 KB Output is correct
9 Correct 55 ms 48252 KB Output is correct
10 Correct 57 ms 48252 KB Output is correct
11 Correct 58 ms 48252 KB Output is correct
12 Correct 67 ms 48252 KB Output is correct
13 Correct 59 ms 48252 KB Output is correct
14 Correct 57 ms 48252 KB Output is correct
15 Correct 54 ms 48252 KB Output is correct
16 Correct 53 ms 48252 KB Output is correct
17 Correct 67 ms 48252 KB Output is correct
18 Correct 54 ms 48252 KB Output is correct
19 Correct 97 ms 49896 KB Output is correct
20 Correct 93 ms 50292 KB Output is correct
21 Correct 86 ms 50292 KB Output is correct
22 Correct 111 ms 50292 KB Output is correct
23 Correct 84 ms 50292 KB Output is correct
24 Correct 85 ms 50292 KB Output is correct
25 Correct 87 ms 50292 KB Output is correct
26 Correct 91 ms 50292 KB Output is correct
27 Correct 83 ms 50292 KB Output is correct
28 Correct 71 ms 50292 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 50292 KB Output is correct
2 Correct 161 ms 50856 KB Output is correct
3 Correct 221 ms 52260 KB Output is correct
4 Correct 226 ms 52260 KB Output is correct
5 Correct 227 ms 52260 KB Output is correct
6 Correct 223 ms 52284 KB Output is correct
7 Correct 241 ms 52284 KB Output is correct
8 Correct 254 ms 52284 KB Output is correct
9 Correct 242 ms 52284 KB Output is correct
10 Correct 291 ms 52284 KB Output is correct
11 Correct 262 ms 52284 KB Output is correct
12 Correct 281 ms 52388 KB Output is correct
13 Correct 277 ms 52388 KB Output is correct
14 Correct 220 ms 52388 KB Output is correct
15 Correct 212 ms 52388 KB Output is correct
16 Correct 195 ms 52388 KB Output is correct
17 Correct 172 ms 52388 KB Output is correct
18 Correct 228 ms 52388 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 47480 KB Output is correct
2 Correct 60 ms 47592 KB Output is correct
3 Correct 56 ms 48032 KB Output is correct
4 Correct 53 ms 48108 KB Output is correct
5 Correct 56 ms 48108 KB Output is correct
6 Correct 51 ms 48132 KB Output is correct
7 Correct 65 ms 48252 KB Output is correct
8 Correct 48 ms 48252 KB Output is correct
9 Correct 55 ms 48252 KB Output is correct
10 Correct 57 ms 48252 KB Output is correct
11 Correct 58 ms 48252 KB Output is correct
12 Correct 67 ms 48252 KB Output is correct
13 Correct 59 ms 48252 KB Output is correct
14 Correct 57 ms 48252 KB Output is correct
15 Correct 54 ms 48252 KB Output is correct
16 Correct 53 ms 48252 KB Output is correct
17 Correct 67 ms 48252 KB Output is correct
18 Correct 54 ms 48252 KB Output is correct
19 Correct 97 ms 49896 KB Output is correct
20 Correct 93 ms 50292 KB Output is correct
21 Correct 86 ms 50292 KB Output is correct
22 Correct 111 ms 50292 KB Output is correct
23 Correct 84 ms 50292 KB Output is correct
24 Correct 85 ms 50292 KB Output is correct
25 Correct 87 ms 50292 KB Output is correct
26 Correct 91 ms 50292 KB Output is correct
27 Correct 83 ms 50292 KB Output is correct
28 Correct 71 ms 50292 KB Output is correct
29 Correct 73 ms 50292 KB Output is correct
30 Correct 161 ms 50856 KB Output is correct
31 Correct 221 ms 52260 KB Output is correct
32 Correct 226 ms 52260 KB Output is correct
33 Correct 227 ms 52260 KB Output is correct
34 Correct 223 ms 52284 KB Output is correct
35 Correct 241 ms 52284 KB Output is correct
36 Correct 254 ms 52284 KB Output is correct
37 Correct 242 ms 52284 KB Output is correct
38 Correct 291 ms 52284 KB Output is correct
39 Correct 262 ms 52284 KB Output is correct
40 Correct 281 ms 52388 KB Output is correct
41 Correct 277 ms 52388 KB Output is correct
42 Correct 220 ms 52388 KB Output is correct
43 Correct 212 ms 52388 KB Output is correct
44 Correct 195 ms 52388 KB Output is correct
45 Correct 172 ms 52388 KB Output is correct
46 Correct 228 ms 52388 KB Output is correct
47 Correct 1376 ms 95180 KB Output is correct
48 Correct 4632 ms 189432 KB Output is correct
49 Correct 5835 ms 204220 KB Output is correct
50 Correct 5683 ms 204284 KB Output is correct
51 Correct 5180 ms 204296 KB Output is correct
52 Correct 5477 ms 204296 KB Output is correct
53 Correct 5017 ms 204296 KB Output is correct
54 Correct 5242 ms 204296 KB Output is correct
55 Correct 5366 ms 204296 KB Output is correct
56 Correct 5481 ms 204296 KB Output is correct
57 Correct 4875 ms 204296 KB Output is correct
58 Correct 4842 ms 204296 KB Output is correct
59 Correct 4888 ms 204296 KB Output is correct
60 Correct 4327 ms 204296 KB Output is correct
61 Correct 4169 ms 204296 KB Output is correct
62 Correct 4566 ms 204296 KB Output is correct
63 Correct 3994 ms 204296 KB Output is correct
64 Correct 4793 ms 204296 KB Output is correct
65 Correct 4276 ms 204296 KB Output is correct
66 Correct 3998 ms 204296 KB Output is correct
67 Correct 4480 ms 204296 KB Output is correct