Submission #121607

#	Time	Username	Problem	Language	Result	Execution time	Memory
121607		wilwxk	Bubble Sort 2 (JOI18_bubblesort2)	C++11	0 / 100	52 ms	2520 KiB

bubblesort2

#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+7;
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
• Subtask 2: 0 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40