oj.uz

Submission #69327

# Submission time Handle Problem Language Result Execution time Memory
69327 2018-08-20T12:54:22 Z ekrem Bubble Sort 2 (JOI18_bubblesort2) C++
60 / 100
 9000 ms 219388 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;
map < int , int > ne;
map < int , int > :: iterator it;

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

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 yerbu(int k, int bas, int son){
	if(bas == son)
		yer[k] = -1;
	yerbu(sol, bas, orta);
	yerbu(sag, orta + 1, son);
}

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 47 ms 47480 KB Output is correct
2 Correct 48 ms 47716 KB Output is correct
3 Correct 63 ms 48208 KB Output is correct
4 Correct 57 ms 48408 KB Output is correct
5 Correct 52 ms 48420 KB Output is correct
6 Correct 51 ms 48420 KB Output is correct
7 Correct 58 ms 48424 KB Output is correct
8 Correct 63 ms 48640 KB Output is correct
9 Correct 60 ms 48640 KB Output is correct
10 Correct 58 ms 48676 KB Output is correct
11 Correct 56 ms 48676 KB Output is correct
12 Correct 58 ms 48852 KB Output is correct
13 Correct 63 ms 48852 KB Output is correct
14 Correct 52 ms 48852 KB Output is correct
15 Correct 58 ms 49000 KB Output is correct
16 Correct 62 ms 49000 KB Output is correct
17 Correct 53 ms 49000 KB Output is correct
18 Correct 60 ms 49000 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 47480 KB Output is correct
2 Correct 48 ms 47716 KB Output is correct
3 Correct 63 ms 48208 KB Output is correct
4 Correct 57 ms 48408 KB Output is correct
5 Correct 52 ms 48420 KB Output is correct
6 Correct 51 ms 48420 KB Output is correct
7 Correct 58 ms 48424 KB Output is correct
8 Correct 63 ms 48640 KB Output is correct
9 Correct 60 ms 48640 KB Output is correct
10 Correct 58 ms 48676 KB Output is correct
11 Correct 56 ms 48676 KB Output is correct
12 Correct 58 ms 48852 KB Output is correct
13 Correct 63 ms 48852 KB Output is correct
14 Correct 52 ms 48852 KB Output is correct
15 Correct 58 ms 49000 KB Output is correct
16 Correct 62 ms 49000 KB Output is correct
17 Correct 53 ms 49000 KB Output is correct
18 Correct 60 ms 49000 KB Output is correct
19 Correct 94 ms 50936 KB Output is correct
20 Correct 99 ms 51672 KB Output is correct
21 Correct 101 ms 51728 KB Output is correct
22 Correct 101 ms 51828 KB Output is correct
23 Correct 116 ms 51896 KB Output is correct
24 Correct 135 ms 52060 KB Output is correct
25 Correct 95 ms 52224 KB Output is correct
26 Correct 89 ms 52224 KB Output is correct
27 Correct 93 ms 52416 KB Output is correct
28 Correct 104 ms 52444 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 52444 KB Output is correct
2 Correct 158 ms 53120 KB Output is correct
3 Correct 245 ms 54188 KB Output is correct
4 Correct 218 ms 54304 KB Output is correct
5 Correct 217 ms 54304 KB Output is correct
6 Correct 273 ms 54404 KB Output is correct
7 Correct 221 ms 54404 KB Output is correct
8 Correct 211 ms 54404 KB Output is correct
9 Correct 210 ms 54404 KB Output is correct
10 Correct 152 ms 54404 KB Output is correct
11 Correct 134 ms 54404 KB Output is correct
12 Correct 139 ms 54404 KB Output is correct
13 Correct 133 ms 54404 KB Output is correct
14 Correct 126 ms 54404 KB Output is correct
15 Correct 119 ms 54404 KB Output is correct
16 Correct 136 ms 54404 KB Output is correct
17 Correct 134 ms 54404 KB Output is correct
18 Correct 146 ms 54404 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 47480 KB Output is correct
2 Correct 48 ms 47716 KB Output is correct
3 Correct 63 ms 48208 KB Output is correct
4 Correct 57 ms 48408 KB Output is correct
5 Correct 52 ms 48420 KB Output is correct
6 Correct 51 ms 48420 KB Output is correct
7 Correct 58 ms 48424 KB Output is correct
8 Correct 63 ms 48640 KB Output is correct
9 Correct 60 ms 48640 KB Output is correct
10 Correct 58 ms 48676 KB Output is correct
11 Correct 56 ms 48676 KB Output is correct
12 Correct 58 ms 48852 KB Output is correct
13 Correct 63 ms 48852 KB Output is correct
14 Correct 52 ms 48852 KB Output is correct
15 Correct 58 ms 49000 KB Output is correct
16 Correct 62 ms 49000 KB Output is correct
17 Correct 53 ms 49000 KB Output is correct
18 Correct 60 ms 49000 KB Output is correct
19 Correct 94 ms 50936 KB Output is correct
20 Correct 99 ms 51672 KB Output is correct
21 Correct 101 ms 51728 KB Output is correct
22 Correct 101 ms 51828 KB Output is correct
23 Correct 116 ms 51896 KB Output is correct
24 Correct 135 ms 52060 KB Output is correct
25 Correct 95 ms 52224 KB Output is correct
26 Correct 89 ms 52224 KB Output is correct
27 Correct 93 ms 52416 KB Output is correct
28 Correct 104 ms 52444 KB Output is correct
29 Correct 83 ms 52444 KB Output is correct
30 Correct 158 ms 53120 KB Output is correct
31 Correct 245 ms 54188 KB Output is correct
32 Correct 218 ms 54304 KB Output is correct
33 Correct 217 ms 54304 KB Output is correct
34 Correct 273 ms 54404 KB Output is correct
35 Correct 221 ms 54404 KB Output is correct
36 Correct 211 ms 54404 KB Output is correct
37 Correct 210 ms 54404 KB Output is correct
38 Correct 152 ms 54404 KB Output is correct
39 Correct 134 ms 54404 KB Output is correct
40 Correct 139 ms 54404 KB Output is correct
41 Correct 133 ms 54404 KB Output is correct
42 Correct 126 ms 54404 KB Output is correct
43 Correct 119 ms 54404 KB Output is correct
44 Correct 136 ms 54404 KB Output is correct
45 Correct 134 ms 54404 KB Output is correct
46 Correct 146 ms 54404 KB Output is correct
47 Correct 2539 ms 111012 KB Output is correct
48 Execution timed out 9081 ms 219388 KB Time limit exceeded
49 Halted 0 ms 0 KB -