oj.uz

Submission #69331

# Submission time Handle Problem Language Result Execution time Memory
69331 2018-08-20T13:07:46 Z ekrem Bubble Sort 2 (JOI18_bubblesort2) C++17
100 / 100
 8940 ms 395664 KB 
#include <bits/stdc++.h>
#include "bubblesort2.h"
#define orta ((bas + son)/2)
#define sol (k+k)
#define sag (k+k+1)
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define N 1000005
using namespace std;

typedef vector < int > vi;
int n, m, q, yer[4*N], yerl[4*N], cvp[4*N], cvpl[4*N];
set < int > s[N];
map < int , int > ek;
unordered_map < int , int > ne;
map < int , int > :: iterator it;

void yerput(int k, int bas, int son, int l);

void yerpush(int k, int bas, int son);

void yerset(int k, int bas, int son, int x, int y);

void yerup(int k, int bas, int son, int x, int y, int z);

int yerqu(int k, int bas, int son, int x);

int yersor(int k, int bas, int son, int x, int y);

void cvpput(int k, int bas, int son, int l);

void cvppush(int k, int bas, int son);

void cvpset(int k, int bas, int son, int x, int y);

void cvpup(int k, int bas, int son, int x, int y, int z);

int cvpqu(int k, int bas, int son, int x);


vi countScans(vi a, vi b, vi c){
	vi ans;
	n = a.size();
	q = b.size();
	for(int i = 0; i < n; i++)
		ek[a[i]] = 1;
	for(int i = 0; i < q; i++)
		ek[c[i]] = 1;
	for(it = ek.begin(); it != ek.end(); it++)
		ne[it->st] = ++m;
	for(int i = 0; i < n; i++)
		s[ne[a[i]]].insert(i);
	vi d = a;
	sort(d.begin(), d.end());
	for(int i = 0; i < n; i++){
		if(i + 1 != n and d[i + 1] == d[i])
			continue;
		yerset(1, 1, m, ne[d[i]], i);
	}
	for(int i = 0; i < n; i++){
		int son = *s[ne[a[i]]].rbegin();
		int yr = yerqu(1, 1, m, ne[a[i]]);
		cvpset(1, 1, m, ne[a[i]], son - yr);
	}
	for(int i = 0; i < q; i++){
		int yr = b[i];
		int yeni = ne[c[i]];
		int eski = ne[a[b[i]]];
		a[yr] = c[i];
		if(yeni == eski){
			ans.pb(cvp[1]);
			continue;
		}
		s[eski].erase(yr);
		s[yeni].insert(yr);
		if(eski < yeni){
			yerup(1, 1, m, eski, yeni - 1, -1);
			cvpup(1, 1, m, eski + 1, yeni - 1, 1);
			if(!s[eski].empty())
				cvpset(1, 1, m, eski, *s[eski].rbegin() - yerqu(1, 1, m, eski) );
			else{
				// yerset(1, 1, m, eski, -1);
				cvpset(1, 1, m, eski, 0);
			}
			if(s[yeni].size() == 1)
				yerset(1, 1, m, yeni, yersor(1, 1, m, 1, yeni - 1) + 1);
			cvpset(1, 1, m, yeni, *s[yeni].rbegin() - yerqu(1, 1, m, yeni) );
		}
		if(eski > yeni){
			yerup(1, 1, m, yeni, eski - 1, 1);
			cvpup(1, 1, m, yeni + 1, eski - 1, -1);
			if(!s[eski].empty())
				cvpset(1, 1, m, eski, *s[eski].rbegin() - yerqu(1, 1, m, eski) );
			else{
				// yerset(1, 1, m, eski, -1);
				cvpset(1, 1, m, eski, 0);
			}
			if(s[yeni].size() == 1)
				yerset(1, 1, m, yeni, yersor(1, 1, m, 1, yeni - 1) + 1);
			cvpset(1, 1, m, yeni, *s[yeni].rbegin() - yerqu(1, 1, m, yeni) );
		}
		ans.pb(cvp[1]);
	}
	return ans;
}

// int main(){
// 	freopen("in.txt", "r", stdin);
// 	freopen("out.txt", "w", stdout);
// 	int n,q;
// 	scanf("%d %d",&n ,&q);	
// 	vi a(n);
// 	for(int i=0;i<n;i++)
// 		scanf("%d",&a[i]);
// 	vi b(q), c(q);
// 	for(int j=0;j<q;j++){
// 		scanf("%d %d",&b[j], &c[j]);
// 	}
// 	vi cvp = countScans(a, b, c);
// 	for(int j=0;j<int(cvp.size());j++)
// 		printf("%d\n",cvp[j]);
// }

void yerput(int k, int l){
	yer[k] += l;
	yerl[k] += l;
}

void yerpush(int k){
	yerput(sol, yerl[k]);
	yerput(sag, yerl[k]);
	yerl[k] = 0;
}

void yerset(int k, int bas, int son, int x, int y){
	if(bas == son){
		yer[k] = y;
		return;
	}
	yerpush(k);
	if(x <= orta)
		yerset(sol, bas, orta, x, y);
	else
		yerset(sag, orta + 1, son, x, y);
	yer[k] = max(yer[sol] , yer[sag]);
}

void yerup(int k, int bas, int son, int x, int y, int z){
	if(bas > y or son < x)
		return;
	if(bas >= x and son <= y){
		yerput(k, z);
		return;
	}
	yerpush(k);
	yerup(sol, bas, orta, x, y, z);
	yerup(sag, orta + 1, son, x, y, z);
	yer[k] = max(yer[sol] , yer[sag]);
}

int yerqu(int k, int bas, int son, int x){
	if(bas == son)
		return yer[k];
	yerpush(k);
	if(x <= orta)
		return yerqu(sol, bas, orta, x);
	return yerqu(sag, orta + 1, son, x);
}

int yersor(int k, int bas, int son, int x, int y){
	if(bas > y or son < x)
		return -1;
	if(bas >= x and son <= y)
		return yer[k];
	return max(yersor(sol, bas, orta , x, y), yersor(sag, orta + 1, son, x, y));
}

void cvpput(int k, int l){
	cvp[k] += l;
	cvpl[k] += l;
}

void cvppush(int k){
	cvpput(sol, cvpl[k]);
	cvpput(sag, cvpl[k]);
	cvpl[k] = 0;
}

void cvpset(int k, int bas, int son, int x, int y){
	if(bas == son){
		cvp[k] = y;
		return;
	}
	cvppush(k);
	if(x <= orta)
		cvpset(sol, bas, orta, x, y);
	else
		cvpset(sag, orta + 1, son, x, y);
	cvp[k] = max(cvp[sol] , cvp[sag]);
}

void cvpup(int k, int bas, int son, int x, int y, int z){
	if(bas > y or son < x)
		return;
	if(bas >= x and son <= y){
		cvpput(k, z);
		return;
	}
	cvppush(k);
	cvpup(sol, bas, orta, x, y, z);
	cvpup(sag, orta + 1, son, x, y, z);
	cvp[k] = max(cvp[sol] , cvp[sag]);
}

int cvpqu(int k, int bas, int son, int x){
	if(bas == son)
		return cvp[k];
	cvppush(k);
	if(x <= orta)
		return cvpqu(sol, bas, orta, x);
	return cvpqu(sag, orta + 1, son, x);
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47480 KB Output is correct
2 Correct 46 ms 47736 KB Output is correct
3 Correct 49 ms 48012 KB Output is correct
4 Correct 49 ms 48060 KB Output is correct
5 Correct 50 ms 48204 KB Output is correct
6 Correct 50 ms 48204 KB Output is correct
7 Correct 51 ms 48204 KB Output is correct
8 Correct 49 ms 48204 KB Output is correct
9 Correct 59 ms 48288 KB Output is correct
10 Correct 49 ms 48288 KB Output is correct
11 Correct 50 ms 48288 KB Output is correct
12 Correct 59 ms 48288 KB Output is correct
13 Correct 49 ms 48288 KB Output is correct
14 Correct 52 ms 48288 KB Output is correct
15 Correct 50 ms 48288 KB Output is correct
16 Correct 50 ms 48288 KB Output is correct
17 Correct 52 ms 48288 KB Output is correct
18 Correct 82 ms 48288 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47480 KB Output is correct
2 Correct 46 ms 47736 KB Output is correct
3 Correct 49 ms 48012 KB Output is correct
4 Correct 49 ms 48060 KB Output is correct
5 Correct 50 ms 48204 KB Output is correct
6 Correct 50 ms 48204 KB Output is correct
7 Correct 51 ms 48204 KB Output is correct
8 Correct 49 ms 48204 KB Output is correct
9 Correct 59 ms 48288 KB Output is correct
10 Correct 49 ms 48288 KB Output is correct
11 Correct 50 ms 48288 KB Output is correct
12 Correct 59 ms 48288 KB Output is correct
13 Correct 49 ms 48288 KB Output is correct
14 Correct 52 ms 48288 KB Output is correct
15 Correct 50 ms 48288 KB Output is correct
16 Correct 50 ms 48288 KB Output is correct
17 Correct 52 ms 48288 KB Output is correct
18 Correct 82 ms 48288 KB Output is correct
19 Correct 79 ms 50008 KB Output is correct
20 Correct 98 ms 50272 KB Output is correct
21 Correct 92 ms 50272 KB Output is correct
22 Correct 97 ms 50336 KB Output is correct
23 Correct 93 ms 50336 KB Output is correct
24 Correct 101 ms 50336 KB Output is correct
25 Correct 92 ms 50336 KB Output is correct
26 Correct 91 ms 50336 KB Output is correct
27 Correct 98 ms 50336 KB Output is correct
28 Correct 76 ms 50336 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 50336 KB Output is correct
2 Correct 125 ms 50616 KB Output is correct
3 Correct 255 ms 51756 KB Output is correct
4 Correct 225 ms 51812 KB Output is correct
5 Correct 265 ms 51880 KB Output is correct
6 Correct 232 ms 51880 KB Output is correct
7 Correct 204 ms 51880 KB Output is correct
8 Correct 258 ms 51880 KB Output is correct
9 Correct 248 ms 51880 KB Output is correct
10 Correct 122 ms 51880 KB Output is correct
11 Correct 119 ms 51884 KB Output is correct
12 Correct 129 ms 51884 KB Output is correct
13 Correct 137 ms 51884 KB Output is correct
14 Correct 125 ms 51884 KB Output is correct
15 Correct 140 ms 51884 KB Output is correct
16 Correct 149 ms 51884 KB Output is correct
17 Correct 140 ms 51884 KB Output is correct
18 Correct 133 ms 51884 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47480 KB Output is correct
2 Correct 46 ms 47736 KB Output is correct
3 Correct 49 ms 48012 KB Output is correct
4 Correct 49 ms 48060 KB Output is correct
5 Correct 50 ms 48204 KB Output is correct
6 Correct 50 ms 48204 KB Output is correct
7 Correct 51 ms 48204 KB Output is correct
8 Correct 49 ms 48204 KB Output is correct
9 Correct 59 ms 48288 KB Output is correct
10 Correct 49 ms 48288 KB Output is correct
11 Correct 50 ms 48288 KB Output is correct
12 Correct 59 ms 48288 KB Output is correct
13 Correct 49 ms 48288 KB Output is correct
14 Correct 52 ms 48288 KB Output is correct
15 Correct 50 ms 48288 KB Output is correct
16 Correct 50 ms 48288 KB Output is correct
17 Correct 52 ms 48288 KB Output is correct
18 Correct 82 ms 48288 KB Output is correct
19 Correct 79 ms 50008 KB Output is correct
20 Correct 98 ms 50272 KB Output is correct
21 Correct 92 ms 50272 KB Output is correct
22 Correct 97 ms 50336 KB Output is correct
23 Correct 93 ms 50336 KB Output is correct
24 Correct 101 ms 50336 KB Output is correct
25 Correct 92 ms 50336 KB Output is correct
26 Correct 91 ms 50336 KB Output is correct
27 Correct 98 ms 50336 KB Output is correct
28 Correct 76 ms 50336 KB Output is correct
29 Correct 70 ms 50336 KB Output is correct
30 Correct 125 ms 50616 KB Output is correct
31 Correct 255 ms 51756 KB Output is correct
32 Correct 225 ms 51812 KB Output is correct
33 Correct 265 ms 51880 KB Output is correct
34 Correct 232 ms 51880 KB Output is correct
35 Correct 204 ms 51880 KB Output is correct
36 Correct 258 ms 51880 KB Output is correct
37 Correct 248 ms 51880 KB Output is correct
38 Correct 122 ms 51880 KB Output is correct
39 Correct 119 ms 51884 KB Output is correct
40 Correct 129 ms 51884 KB Output is correct
41 Correct 137 ms 51884 KB Output is correct
42 Correct 125 ms 51884 KB Output is correct
43 Correct 140 ms 51884 KB Output is correct
44 Correct 149 ms 51884 KB Output is correct
45 Correct 140 ms 51884 KB Output is correct
46 Correct 133 ms 51884 KB Output is correct
47 Correct 2004 ms 103988 KB Output is correct
48 Correct 8076 ms 202952 KB Output is correct
49 Correct 8259 ms 214428 KB Output is correct
50 Correct 8680 ms 214428 KB Output is correct
51 Correct 8316 ms 227304 KB Output is correct
52 Correct 7953 ms 240136 KB Output is correct
53 Correct 8210 ms 253108 KB Output is correct
54 Correct 7737 ms 266072 KB Output is correct
55 Correct 8940 ms 279112 KB Output is correct
56 Correct 7595 ms 291976 KB Output is correct
57 Correct 7351 ms 305204 KB Output is correct
58 Correct 7127 ms 318152 KB Output is correct
59 Correct 5765 ms 318152 KB Output is correct
60 Correct 6023 ms 324804 KB Output is correct
61 Correct 6370 ms 336388 KB Output is correct
62 Correct 5475 ms 343152 KB Output is correct
63 Correct 6462 ms 354656 KB Output is correct
64 Correct 5492 ms 366168 KB Output is correct
65 Correct 5435 ms 372704 KB Output is correct
66 Correct 5368 ms 384056 KB Output is correct
67 Correct 5870 ms 395664 KB Output is correct