oj.uz

답안 #69324

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
69324 2018-08-20T12:47:32 Z ekrem Bubble Sort 2 (JOI18_bubblesort2) C++
22 / 100
 232 ms 104104 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];

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();
	m = 102;
	q = b.size();
	for(int i = 0; i < n; i++)
		s[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, d[i], i);
	}
	for(int i = 0; i < n; i++){
		int son = *s[a[i]].rbegin();
		int yr = yerqu(1, 1, m, a[i]);
		cvpset(1, 1, m, a[i], son - yr);
	}
	for(int i = 0; i < q; i++){
		int yr = b[i];
		int yeni = c[i];
		int eski = a[b[i]];
		a[yr] = yeni;
		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
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 87 ms 94420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 87 ms 94420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 96200 KB Output is correct
2 Correct 142 ms 97548 KB Output is correct
3 Correct 232 ms 98752 KB Output is correct
4 Correct 218 ms 98808 KB Output is correct
5 Correct 206 ms 98896 KB Output is correct
6 Correct 188 ms 98896 KB Output is correct
7 Correct 190 ms 98944 KB Output is correct
8 Correct 179 ms 98944 KB Output is correct
9 Correct 164 ms 98992 KB Output is correct
10 Correct 132 ms 98992 KB Output is correct
11 Correct 112 ms 99520 KB Output is correct
12 Correct 110 ms 100228 KB Output is correct
13 Correct 140 ms 100900 KB Output is correct
14 Correct 137 ms 101528 KB Output is correct
15 Correct 138 ms 102204 KB Output is correct
16 Correct 135 ms 102832 KB Output is correct
17 Correct 142 ms 103568 KB Output is correct
18 Correct 128 ms 104104 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 87 ms 94420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -