답안 #58930 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58930	2018-07-19T20:33:31 Z	khohko	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	5835 ms	204296 KB

bubblesort2

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #58930

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 21.0 / 21.0

Subtask #3 22.0 / 22.0

Subtask #4 40.0 / 40.0

Subtask #1
17.0 / 17.0

Subtask #2
21.0 / 21.0

Subtask #3
22.0 / 22.0

Subtask #4
40.0 / 40.0