답안 #448237

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
448237	2021-07-29T11:05:46 Z	CSQ31	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	2306 ms	136760 KB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
typedef pair<int,int> pii;
const int MAXN = 1e6+1;
vector<int>t(4*MAXN,-1e9),lazy(4*MAXN,0);
vector<set<int,greater<int>>>s(MAXN);
vector<int>f(MAXN);
void upd1(int v,int l,int r,int pos,int val){
	if(l > r)return;
	if(l==r){
		//lazy[v] = 0;
		if(val < 0)s[pos].erase(-val);
		else s[pos].insert(val);
		if(!s[pos].empty())t[v] = *s[pos].begin() - f[pos] + lazy[v];
		else t[v] = -1e9;
		return;
	}
	int tm=(l+r)/2;
	if(pos<=tm)upd1(2*v,l,tm,pos,val);
	else upd1(2*v+1,tm+1,r,pos,val);
	t[v] = max(t[2*v],t[2*v+1]) + lazy[v];
}
void upd2(int v,int l,int r,int tl,int tr,int val){
	if(l > r)return;
	if(l==tl && r == tr){
		lazy[v]+=val;
		t[v]+=val;
		return;
	}
	int tm = (tl+tr)/2;
	upd2(2*v,l,min(r,tm),tl,tm,val);
	upd2(2*v+1,max(l,tm+1),r,tm+1,tr,val);
	t[v] = max(t[2*v],t[2*v+1]) + lazy[v];
}
vector<int> countScans(vector<int> a,vector<int> x,vector<int>v){
	int q=sz(x);
	int n = sz(a);
	vector<int> answer(q);
	vector<int>b;
	for(int i=0;i<n;i++)b.push_back(a[i]);
	for(int i=0;i<q;i++)b.push_back(v[i]);
	sort(all(b));
	b.resize(unique(all(b))-b.begin());
	int m = sz(b);
	for(int i=0;i<n;i++)a[i] = lower_bound(all(b),a[i])-b.begin()+1;
	for(int i=0;i<q;i++)v[i] = lower_bound(all(b),v[i])-b.begin()+1;
	for(int i=0;i<n;i++)f[a[i]]++;
	for(int i=1;i<=m;i++)f[i]+=f[i-1];
	for(int i=0;i<n;i++)upd1(1,1,m,a[i],i+1);
	for(int i=0;i<q;i++){
		upd1(1,1,m,a[x[i]],-x[i]-1);
		upd1(1,1,m,v[i],x[i]+1);
		upd2(1,a[x[i]],m,1,m,1);
		upd2(1,v[i],m,1,m,-1);
		a[x[i]] = v[i];
		answer[i] = t[1];
	}
	return answer;
}

Subtask #1
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	42 ms	82480 KB	Output is correct
2	Correct	43 ms	82520 KB	Output is correct
3	Correct	45 ms	82692 KB	Output is correct
4	Correct	46 ms	82656 KB	Output is correct
5	Correct	47 ms	82576 KB	Output is correct
6	Correct	48 ms	82652 KB	Output is correct
7	Correct	46 ms	82620 KB	Output is correct
8	Correct	45 ms	82628 KB	Output is correct
9	Correct	45 ms	82624 KB	Output is correct
10	Correct	44 ms	82628 KB	Output is correct
11	Correct	45 ms	82580 KB	Output is correct
12	Correct	46 ms	82624 KB	Output is correct
13	Correct	45 ms	82608 KB	Output is correct
14	Correct	45 ms	82576 KB	Output is correct
15	Correct	45 ms	82624 KB	Output is correct
16	Correct	47 ms	82628 KB	Output is correct
17	Correct	45 ms	82608 KB	Output is correct
18	Correct	44 ms	82596 KB	Output is correct

Subtask #2
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	42 ms	82480 KB	Output is correct
2	Correct	43 ms	82520 KB	Output is correct
3	Correct	45 ms	82692 KB	Output is correct
4	Correct	46 ms	82656 KB	Output is correct
5	Correct	47 ms	82576 KB	Output is correct
6	Correct	48 ms	82652 KB	Output is correct
7	Correct	46 ms	82620 KB	Output is correct
8	Correct	45 ms	82628 KB	Output is correct
9	Correct	45 ms	82624 KB	Output is correct
10	Correct	44 ms	82628 KB	Output is correct
11	Correct	45 ms	82580 KB	Output is correct
12	Correct	46 ms	82624 KB	Output is correct
13	Correct	45 ms	82608 KB	Output is correct
14	Correct	45 ms	82576 KB	Output is correct
15	Correct	45 ms	82624 KB	Output is correct
16	Correct	47 ms	82628 KB	Output is correct
17	Correct	45 ms	82608 KB	Output is correct
18	Correct	44 ms	82596 KB	Output is correct
19	Correct	57 ms	83252 KB	Output is correct
20	Correct	59 ms	83328 KB	Output is correct
21	Correct	58 ms	83256 KB	Output is correct
22	Correct	59 ms	83264 KB	Output is correct
23	Correct	57 ms	83316 KB	Output is correct
24	Correct	58 ms	83268 KB	Output is correct
25	Correct	57 ms	83276 KB	Output is correct
26	Correct	57 ms	83268 KB	Output is correct
27	Correct	59 ms	83280 KB	Output is correct
28	Correct	61 ms	83276 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	84164 KB	Output is correct
2	Correct	91 ms	85668 KB	Output is correct
3	Correct	128 ms	87064 KB	Output is correct
4	Correct	130 ms	87080 KB	Output is correct
5	Correct	132 ms	87072 KB	Output is correct
6	Correct	126 ms	87128 KB	Output is correct
7	Correct	128 ms	87228 KB	Output is correct
8	Correct	128 ms	87100 KB	Output is correct
9	Correct	132 ms	87108 KB	Output is correct
10	Correct	109 ms	87228 KB	Output is correct
11	Correct	110 ms	87148 KB	Output is correct
12	Correct	113 ms	87172 KB	Output is correct
13	Correct	115 ms	87268 KB	Output is correct
14	Correct	129 ms	87200 KB	Output is correct
15	Correct	113 ms	87128 KB	Output is correct
16	Correct	105 ms	87232 KB	Output is correct
17	Correct	103 ms	87224 KB	Output is correct
18	Correct	102 ms	87132 KB	Output is correct

Subtask #4
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	42 ms	82480 KB	Output is correct
2	Correct	43 ms	82520 KB	Output is correct
3	Correct	45 ms	82692 KB	Output is correct
4	Correct	46 ms	82656 KB	Output is correct
5	Correct	47 ms	82576 KB	Output is correct
6	Correct	48 ms	82652 KB	Output is correct
7	Correct	46 ms	82620 KB	Output is correct
8	Correct	45 ms	82628 KB	Output is correct
9	Correct	45 ms	82624 KB	Output is correct
10	Correct	44 ms	82628 KB	Output is correct
11	Correct	45 ms	82580 KB	Output is correct
12	Correct	46 ms	82624 KB	Output is correct
13	Correct	45 ms	82608 KB	Output is correct
14	Correct	45 ms	82576 KB	Output is correct
15	Correct	45 ms	82624 KB	Output is correct
16	Correct	47 ms	82628 KB	Output is correct
17	Correct	45 ms	82608 KB	Output is correct
18	Correct	44 ms	82596 KB	Output is correct
19	Correct	57 ms	83252 KB	Output is correct
20	Correct	59 ms	83328 KB	Output is correct
21	Correct	58 ms	83256 KB	Output is correct
22	Correct	59 ms	83264 KB	Output is correct
23	Correct	57 ms	83316 KB	Output is correct
24	Correct	58 ms	83268 KB	Output is correct
25	Correct	57 ms	83276 KB	Output is correct
26	Correct	57 ms	83268 KB	Output is correct
27	Correct	59 ms	83280 KB	Output is correct
28	Correct	61 ms	83276 KB	Output is correct
29	Correct	57 ms	84164 KB	Output is correct
30	Correct	91 ms	85668 KB	Output is correct
31	Correct	128 ms	87064 KB	Output is correct
32	Correct	130 ms	87080 KB	Output is correct
33	Correct	132 ms	87072 KB	Output is correct
34	Correct	126 ms	87128 KB	Output is correct
35	Correct	128 ms	87228 KB	Output is correct
36	Correct	128 ms	87100 KB	Output is correct
37	Correct	132 ms	87108 KB	Output is correct
38	Correct	109 ms	87228 KB	Output is correct
39	Correct	110 ms	87148 KB	Output is correct
40	Correct	113 ms	87172 KB	Output is correct
41	Correct	115 ms	87268 KB	Output is correct
42	Correct	129 ms	87200 KB	Output is correct
43	Correct	113 ms	87128 KB	Output is correct
44	Correct	105 ms	87232 KB	Output is correct
45	Correct	103 ms	87224 KB	Output is correct
46	Correct	102 ms	87132 KB	Output is correct
47	Correct	547 ms	98680 KB	Output is correct
48	Correct	1925 ms	130988 KB	Output is correct
49	Correct	2089 ms	136452 KB	Output is correct
50	Correct	2182 ms	136588 KB	Output is correct
51	Correct	2306 ms	136372 KB	Output is correct
52	Correct	2191 ms	136592 KB	Output is correct
53	Correct	2122 ms	136476 KB	Output is correct
54	Correct	1963 ms	136588 KB	Output is correct
55	Correct	2079 ms	136644 KB	Output is correct
56	Correct	1976 ms	136564 KB	Output is correct
57	Correct	2074 ms	136760 KB	Output is correct
58	Correct	1966 ms	136572 KB	Output is correct
59	Correct	1842 ms	135340 KB	Output is correct
60	Correct	1851 ms	135340 KB	Output is correct
61	Correct	1844 ms	135240 KB	Output is correct
62	Correct	1753 ms	135112 KB	Output is correct
63	Correct	1752 ms	135136 KB	Output is correct
64	Correct	1783 ms	135108 KB	Output is correct
65	Correct	1690 ms	135140 KB	Output is correct
66	Correct	1702 ms	134956 KB	Output is correct
67	Correct	1715 ms	135280 KB	Output is correct

답안 #448237

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