oj.uz

답안 #121606

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
121606 2019-06-26T20:30:54 Z wilwxk Bubble Sort 2 (JOI18_bubblesort2) C++11
0 / 100
 5058 ms 524288 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;

struct node {
	int lz, mx, l, r;
};

const int MAXN=5e5+5;
const int MAIOR=1e9;
int v[MAXN];
vector<node> seg;
int n, q;

int novo() {
	node cur;
	cur.lz=cur.mx=cur.l=cur.r=0;
	seg.push_back(cur);
	return seg.size()-1;
}

void refresh(int sind, int ini, int fim) {
	seg[sind].mx+=seg[sind].lz;
	// printf("modifica mx[%d; %d] >> %d\n", ini, fim, seg[sind].mx);
	if(ini==fim) {
		seg[sind].lz=0;
		return;
	}
	if(!seg[sind].l) { int aux=novo(); seg[sind].l=aux; }
	if(!seg[sind].r) { int aux=novo(); seg[sind].r=aux; }
	seg[seg[sind].l].lz+=seg[sind].lz;
	seg[seg[sind].r].lz+=seg[sind].lz;
	seg[sind].lz=0;
}

void update(int sind, int ini, int fim, int qini, int qfim, int val) {
	refresh(sind, ini, fim);
	if(qini>fim||qfim<ini) return;
	if(qini<=ini&&qfim>=fim) {
		seg[sind].lz+=val;
		refresh(sind, ini, fim);
		return;
	}
	int e=seg[sind].l; int d=seg[sind].r;
	int m=(ini+fim)/2;
	update(e, ini, m, qini, qfim, val);
	update(d, m+1, fim, qini, qfim, val);
	seg[sind].mx=max(seg[e].mx, seg[d].mx);
}

void query(int sind, int ini, int fim) {
	refresh(sind, ini, fim);
	if(ini==fim) {
		// printf("%d [%d]: %d %d\n", sind, ini, seg[sind].mx, seg[sind].lz);
		return;
	}
	int e=seg[sind].l; int d=seg[sind].r;
	int m=(ini+fim)/2;
	query(e, ini, m); query(d, m+1, fim);
}

vector<int> countScans(vector<int> A, vector<int> qi, vector<int> qv){
	vector<int> respf;
	n=A.size(); q=qi.size();
	novo(); novo();
	for(int i=0; i<n; i++) {
		v[i]=A[i];
		update(1, 1, MAIOR, v[i]+1, MAIOR, -1);
		update(1, 1, MAIOR, v[i], v[i], i);
	}
	query(1, 1, MAIOR);

	for(int i=0; i<q; i++) {
		int ind=qi[i]; int val=qv[i];
		// printf("query %d %d\n", ind, val); 	
		update(1, 1, MAIOR, v[ind]+1, MAIOR, 1);
		update(1, 1, MAIOR, v[ind], v[ind], ind);
		query(1, 1, MAIOR);
		v[ind]=val;
		update(1, 1, MAIOR, v[ind]+1, MAIOR, -1);
		update(1, 1, MAIOR, v[ind], v[ind], ind);
		int resp=seg[1].mx;
		respf.push_back(resp);
		// printf("ok %d\n", resp);
	}
	return respf;
}

Subtask #1
0 / 17.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

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