oj.uz

답안 #69306

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
69306 2018-08-20T11:53:17 Z ekrem Bubble Sort 2 (JOI18_bubblesort2) C++
0 / 100
 247 ms 104008 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 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 = 100;
	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);
	}
	// cout << cvp[1] << endl;
	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;
		}
		// cout << s[eski].size() << " " << s[yeni].size() << endl;
		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
				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) );
			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 0;
	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 98 ms 94584 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 98 ms 94584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 96372 KB Output is correct
2 Correct 119 ms 98016 KB Output is correct
3 Correct 181 ms 99916 KB Output is correct
4 Correct 220 ms 100412 KB Output is correct
5 Correct 191 ms 100980 KB Output is correct
6 Correct 247 ms 101556 KB Output is correct
7 Correct 225 ms 102104 KB Output is correct
8 Correct 182 ms 102748 KB Output is correct
9 Correct 166 ms 103380 KB Output is correct
10 Incorrect 111 ms 104008 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

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