Submission #389626

#	Time	Username	Problem	Language	Result	Execution time	Memory
389626		maximath_1	Bubble Sort 2 (JOI18_bubblesort2)	C++11	100 / 100	3484 ms	69896 KiB

bubblesort2

#include "bubblesort2.h"
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>
using namespace std;

#define ll long long
const int MX = 1000005;
const ll inf = 696969696969ll;

ll st[MX * 4], lz[MX * 4];

void prop(int nd, int cl, int cr){
	if(lz[nd]){
		st[nd] += lz[nd];
		if(cl != cr)
			lz[nd * 2] += lz[nd],
			lz[nd * 2 + 1] += lz[nd];
		lz[nd] = 0;
	}
}

void upd(int nd, int cl, int cr, int lf, int rg, ll val){
	prop(nd, cl, cr);
	if(rg < cl || cr < lf || lf > rg || cl > cr) return;
	if(lf <= cl && cr <= rg){
		lz[nd] += val;
		prop(nd, cl, cr);
		return;
	}

	upd(nd * 2, cl, (cl + cr) / 2, lf, rg, val);
	upd(nd * 2 + 1, (cl + cr) / 2 + 1, cr, lf, rg, val);
	st[nd] = max(st[nd * 2], st[nd * 2 + 1]);
}

int que(int nd, int cl, int cr, int lf, int rg){
	prop(nd, cl, cr);
	if(cl > cr || lf > rg || rg < cl || cr < lf) return 0;
	if(lf <= cl && cr <= rg) return st[nd];

	return max(
		que(nd * 2, cl, (cl + cr) / 2, lf, rg),
		que(nd * 2 + 1, (cl + cr) / 2 + 1, cr, lf, rg)
	);
}

vector<pair<int, int> > cc;

void ins(int ps, int val){
	int i = lower_bound(cc.begin(), cc.end(), make_pair(val, ps)) - cc.begin();
	upd(1, 0, cc.size() - 1, i, i, inf + ps);
	upd(1, 0, cc.size() - 1, i + 1, cc.size() - 1, -1);
}

void del(int ps, int val){
	int i = lower_bound(cc.begin(), cc.end(), make_pair(val, ps)) - cc.begin();
	upd(1, 0, cc.size() - 1, i, i, -(inf + ps));
	upd(1, 0, cc.size() - 1, i + 1, cc.size() - 1, 1);
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
	for(int i = 0; i < A.size(); i ++)
		cc.push_back({A[i], i});
	sort(cc.begin(), cc.end());
	for(int i = 0; i < X.size(); i ++)		
		cc.push_back({V[i], X[i]});
	sort(cc.begin(), cc.end());
	cc.erase(unique(cc.begin(), cc.end()), cc.end());

	upd(1, 0, cc.size() - 1, 0, cc.size() - 1, -inf);

	for(int i = 0; i < A.size(); i ++)
		ins(i, A[i]);

	vector<int> ans;
	for(int i = 0; i < X.size(); i ++){
		del(X[i], A[X[i]]);
		A[X[i]] = V[i];
		ins(X[i], A[X[i]]);
		ans.push_back(que(1, 0, cc.size() - 1, 0, cc.size() - 1));
	}

	return ans;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for(int i = 0; i < A.size(); i ++)
      |                 ~~^~~~~~~~~~
bubblesort2.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for(int i = 0; i < X.size(); i ++)
      |                 ~~^~~~~~~~~~
bubblesort2.cpp:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |  for(int i = 0; i < A.size(); i ++)
      |                 ~~^~~~~~~~~~
bubblesort2.cpp:78:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for(int i = 0; i < X.size(); i ++){
      |                 ~~^~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40