답안 #332358

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
332358	2020-12-02T06:11:02 Z	YJU	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	3628 ms	449044 KB

bubblesort2

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=1e6+5;
const ll K=350;
const ld pi=acos(-1);
const ll INF=(1LL<<30);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
 
ll tag[4*N],ma[4*N];
set<ll> cnt[4*N];
vector<ll> lis;
 
void push(ll id){
	if(tag[id]){
		tag[id*2]+=tag[id];
		ma[id*2]+=tag[id];
		tag[id*2+1]+=tag[id];
		ma[id*2+1]+=tag[id];
		tag[id]=0;
	}
}
 
void add(ll id,ll l,ll r,ll ql,ll qr,ll val){
	if(l>=ql&&r<=qr){tag[id]+=val;ma[id]+=val;return;}
	if(l>=qr||r<=ql)return ;
	ll mid=(l+r)/2;
	push(id);
	add(id*2,l,mid,ql,qr,val);
	add(id*2+1,mid,r,ql,qr,val);
	ma[id]=max(ma[id*2],ma[id*2+1]);
}
 
void upd(ll to,ll val,ll ty){
	while(SZ(cnt[to])==0);
	ll D=*prev(cnt[to].end());
	if(ty==0)cnt[to].erase(val);
	else cnt[to].insert(val);
	D=*prev(cnt[to].end())-D;
	add(1,1,SZ(lis)+1,to,to+1,D);
	add(1,1,SZ(lis)+1,to,SZ(lis)+1,(ty?-1:1));
}
 
vector<ll> countScans(vector<ll> A,vector<ll> X,vector<ll> V){
	vector<ll> ans;
	for(auto i:A)lis.pb(i);for(auto i:V)lis.pb(i);
    sort(lis.begin(),lis.end());
	lis.resize(unique(lis.begin(),lis.end())-lis.begin());
	for(auto &i:A)i=lwb(lis.begin(),lis.end(),i)-lis.begin()+1;
	for(auto &i:V)i=lwb(lis.begin(),lis.end(),i)-lis.begin()+1;
	
	REP(i,4*N)cnt[i].insert(-1);
	REP(i,SZ(A))upd(A[i],i,1);
	REP(i,SZ(X)){
		upd(A[X[i]],X[i],0);
		upd(A[X[i]]=V[i],X[i],1);
		ans.pb(ma[1]);
	}
	return ans;
}
 
/*
int main(){
	vector<ll> A,X,V;
	ll n,q,x;
	cin>>n>>q;
	REP(i,n)cin>>x,A.pb(x);
	REP(i,q)cin>>x,X.pb(x),cin>>x,V.pb(x);
	vector<ll> ans=countScans(A,X,V);
	for(ll i:ans)cout<<i<<"\n";
}
//*/

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:58:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   58 |  for(auto i:A)lis.pb(i);for(auto i:V)lis.pb(i);
      |  ^~~
bubblesort2.cpp:58:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   58 |  for(auto i:A)lis.pb(i);for(auto i:V)lis.pb(i);
      |                         ^~~

Subtask #1
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	398 ms	376172 KB	Output is correct
2	Correct	403 ms	376172 KB	Output is correct
3	Correct	421 ms	376364 KB	Output is correct
4	Correct	405 ms	376428 KB	Output is correct
5	Correct	412 ms	376404 KB	Output is correct
6	Correct	411 ms	376300 KB	Output is correct
7	Correct	403 ms	376428 KB	Output is correct
8	Correct	410 ms	376556 KB	Output is correct
9	Correct	406 ms	376292 KB	Output is correct
10	Correct	427 ms	376400 KB	Output is correct
11	Correct	403 ms	376300 KB	Output is correct
12	Correct	407 ms	376300 KB	Output is correct
13	Correct	412 ms	376428 KB	Output is correct
14	Correct	417 ms	376300 KB	Output is correct
15	Correct	428 ms	376300 KB	Output is correct
16	Correct	413 ms	376428 KB	Output is correct
17	Correct	412 ms	376556 KB	Output is correct
18	Correct	468 ms	376300 KB	Output is correct

Subtask #2
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	398 ms	376172 KB	Output is correct
2	Correct	403 ms	376172 KB	Output is correct
3	Correct	421 ms	376364 KB	Output is correct
4	Correct	405 ms	376428 KB	Output is correct
5	Correct	412 ms	376404 KB	Output is correct
6	Correct	411 ms	376300 KB	Output is correct
7	Correct	403 ms	376428 KB	Output is correct
8	Correct	410 ms	376556 KB	Output is correct
9	Correct	406 ms	376292 KB	Output is correct
10	Correct	427 ms	376400 KB	Output is correct
11	Correct	403 ms	376300 KB	Output is correct
12	Correct	407 ms	376300 KB	Output is correct
13	Correct	412 ms	376428 KB	Output is correct
14	Correct	417 ms	376300 KB	Output is correct
15	Correct	428 ms	376300 KB	Output is correct
16	Correct	413 ms	376428 KB	Output is correct
17	Correct	412 ms	376556 KB	Output is correct
18	Correct	468 ms	376300 KB	Output is correct
19	Correct	431 ms	377196 KB	Output is correct
20	Correct	450 ms	377196 KB	Output is correct
21	Correct	419 ms	377068 KB	Output is correct
22	Correct	438 ms	377068 KB	Output is correct
23	Correct	428 ms	377068 KB	Output is correct
24	Correct	426 ms	377068 KB	Output is correct
25	Correct	422 ms	377196 KB	Output is correct
26	Correct	419 ms	377068 KB	Output is correct
27	Correct	430 ms	377068 KB	Output is correct
28	Correct	415 ms	377068 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	460 ms	377836 KB	Output is correct
2	Correct	463 ms	379112 KB	Output is correct
3	Correct	512 ms	380516 KB	Output is correct
4	Correct	509 ms	380516 KB	Output is correct
5	Correct	508 ms	380516 KB	Output is correct
6	Correct	507 ms	380440 KB	Output is correct
7	Correct	508 ms	380388 KB	Output is correct
8	Correct	509 ms	380388 KB	Output is correct
9	Correct	508 ms	380388 KB	Output is correct
10	Correct	492 ms	380516 KB	Output is correct
11	Correct	487 ms	380388 KB	Output is correct
12	Correct	522 ms	380516 KB	Output is correct
13	Correct	501 ms	380516 KB	Output is correct
14	Correct	529 ms	380520 KB	Output is correct
15	Correct	486 ms	380644 KB	Output is correct
16	Correct	484 ms	380388 KB	Output is correct
17	Correct	490 ms	380388 KB	Output is correct
18	Correct	502 ms	380516 KB	Output is correct

Subtask #4
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	398 ms	376172 KB	Output is correct
2	Correct	403 ms	376172 KB	Output is correct
3	Correct	421 ms	376364 KB	Output is correct
4	Correct	405 ms	376428 KB	Output is correct
5	Correct	412 ms	376404 KB	Output is correct
6	Correct	411 ms	376300 KB	Output is correct
7	Correct	403 ms	376428 KB	Output is correct
8	Correct	410 ms	376556 KB	Output is correct
9	Correct	406 ms	376292 KB	Output is correct
10	Correct	427 ms	376400 KB	Output is correct
11	Correct	403 ms	376300 KB	Output is correct
12	Correct	407 ms	376300 KB	Output is correct
13	Correct	412 ms	376428 KB	Output is correct
14	Correct	417 ms	376300 KB	Output is correct
15	Correct	428 ms	376300 KB	Output is correct
16	Correct	413 ms	376428 KB	Output is correct
17	Correct	412 ms	376556 KB	Output is correct
18	Correct	468 ms	376300 KB	Output is correct
19	Correct	431 ms	377196 KB	Output is correct
20	Correct	450 ms	377196 KB	Output is correct
21	Correct	419 ms	377068 KB	Output is correct
22	Correct	438 ms	377068 KB	Output is correct
23	Correct	428 ms	377068 KB	Output is correct
24	Correct	426 ms	377068 KB	Output is correct
25	Correct	422 ms	377196 KB	Output is correct
26	Correct	419 ms	377068 KB	Output is correct
27	Correct	430 ms	377068 KB	Output is correct
28	Correct	415 ms	377068 KB	Output is correct
29	Correct	460 ms	377836 KB	Output is correct
30	Correct	463 ms	379112 KB	Output is correct
31	Correct	512 ms	380516 KB	Output is correct
32	Correct	509 ms	380516 KB	Output is correct
33	Correct	508 ms	380516 KB	Output is correct
34	Correct	507 ms	380440 KB	Output is correct
35	Correct	508 ms	380388 KB	Output is correct
36	Correct	509 ms	380388 KB	Output is correct
37	Correct	508 ms	380388 KB	Output is correct
38	Correct	492 ms	380516 KB	Output is correct
39	Correct	487 ms	380388 KB	Output is correct
40	Correct	522 ms	380516 KB	Output is correct
41	Correct	501 ms	380516 KB	Output is correct
42	Correct	529 ms	380520 KB	Output is correct
43	Correct	486 ms	380644 KB	Output is correct
44	Correct	484 ms	380388 KB	Output is correct
45	Correct	490 ms	380388 KB	Output is correct
46	Correct	502 ms	380516 KB	Output is correct
47	Correct	1227 ms	397972 KB	Output is correct
48	Correct	3436 ms	431492 KB	Output is correct
49	Correct	3603 ms	448732 KB	Output is correct
50	Correct	3620 ms	448888 KB	Output is correct
51	Correct	3628 ms	448768 KB	Output is correct
52	Correct	3621 ms	448596 KB	Output is correct
53	Correct	3582 ms	448568 KB	Output is correct
54	Correct	3354 ms	448820 KB	Output is correct
55	Correct	3562 ms	449044 KB	Output is correct
56	Correct	3471 ms	448704 KB	Output is correct
57	Correct	3490 ms	448796 KB	Output is correct
58	Correct	3379 ms	449020 KB	Output is correct
59	Correct	3025 ms	447676 KB	Output is correct
60	Correct	3135 ms	447348 KB	Output is correct
61	Correct	2967 ms	447524 KB	Output is correct
62	Correct	2876 ms	447412 KB	Output is correct
63	Correct	2885 ms	447260 KB	Output is correct
64	Correct	2826 ms	447252 KB	Output is correct
65	Correct	2732 ms	447028 KB	Output is correct
66	Correct	2671 ms	447308 KB	Output is correct
67	Correct	2665 ms	447136 KB	Output is correct

답안 #332358

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