oj.uz

Submission #367317

# Submission time Handle Problem Language Result Execution time Memory
367317 2021-02-16T20:48:42 Z cheissmart Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
 156 ms 52860 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1e6 + 7;

struct node {
	int mx, add, lz;
	node(int x = 0) {
		mx = x;
		add = lz = 0;		
	}
} t[N * 4];

int n;

void apply(int v, int x) {
	t[v].mx += x;
	t[v].add += x;
	t[v].lz += x;
}

void push(int v) {
	apply(v * 2, t[v].lz);
	apply(v * 2 + 1, t[v].lz);
	t[v].lz = 0;
}

void pull(int v) {
	t[v].mx = max(t[v * 2].mx, t[v * 2 + 1].mx);
}

void build(int v = 1, int tl = 0, int tr = n) {
	if(tr - tl == 1) {
		t[v] = node(-INF);
		return;
	}
	int tm = (tl + tr) / 2;
	build(v * 2, tl, tm);
	build(v * 2 + 1, tm, tr);
	pull(v);
}

void add(int l, int r, int x, int v = 1, int tl = 0, int tr = n) {
	if(l <= tl && tr <= r) {
		apply(v, x);
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	if(l < tm) add(l, r, x, v * 2, tl, tm);
	if(r > tm) add(l, r, x, v * 2 + 1, tm, tr);
	pull(v);
}

void set_val(int pos, int x, int v = 1, int tl = 0, int tr = n) {
	if(tr - tl == 1) {
		t[v] = node(x);
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	if(pos < tm) set_val(pos, x, v * 2, tl, tm);
	else set_val(pos, x, v * 2 + 1, tm, tr);
	pull(v);
}

int get_add(int pos, int v = 1, int tl = 0, int tr = n) {
	if(tr - tl == 1)
		return t[v].add;
	push(v);
	int tm = (tl + tr) / 2;
	if(pos < tm) return get_add(pos, v * 2, tl, tm);
	else return get_add(pos, v * 2 + 1, tm, tr);
}

vi countScans(vi A, vi X, vi Y) {
	int Q = X.size(), N = A.size();
	V<pi> v;
	for(int i = 0; i < N; i++) v.EB(A[i], i);
	for(int i = 0; i < Q; i++) v.EB(Y[i], X[i]);
	map<pi, int> id;
	sort(ALL(v));
	v.resize(unique(ALL(v)) - v.begin());
	for(int i = 0; i < v.size(); i++)
		id[v[i]] = i;
	n = v.size();
	build();
	for(int i = 0; i < N; i++) {
		int x = id[{A[i], i}];
		A[i] = x;
		set_val(x, i);
	}
	for(int i = 0; i < N; i++)
		if(A[i] + 1 < n)
			add(A[i] + 1, n, -1);
	vi ans(Q);
	for(int i = 0; i < Q; i++) {
		int pos = X[i], val = Y[i], old_val = A[pos];
		val = id[{val, pos}];
		A[pos] = val;
		// old_val -> val
		if(old_val + 1 < n)
			add(old_val + 1, n, 1);
		set_val(old_val, -INF);
		int added = get_add(val);
		set_val(val, added + pos);
		if(val + 1 < n)
			add(val + 1, n, -1);
		ans[i] = t[1].mx;
	}
	return ans;
}

Compilation message

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

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47340 KB Output is correct
2 Correct 36 ms 47468 KB Output is correct
3 Correct 42 ms 47724 KB Output is correct
4 Correct 36 ms 47724 KB Output is correct
5 Correct 36 ms 47724 KB Output is correct
6 Correct 36 ms 47724 KB Output is correct
7 Correct 36 ms 47724 KB Output is correct
8 Correct 37 ms 47724 KB Output is correct
9 Correct 42 ms 47724 KB Output is correct
10 Incorrect 36 ms 47596 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47340 KB Output is correct
2 Correct 36 ms 47468 KB Output is correct
3 Correct 42 ms 47724 KB Output is correct
4 Correct 36 ms 47724 KB Output is correct
5 Correct 36 ms 47724 KB Output is correct
6 Correct 36 ms 47724 KB Output is correct
7 Correct 36 ms 47724 KB Output is correct
8 Correct 37 ms 47724 KB Output is correct
9 Correct 42 ms 47724 KB Output is correct
10 Incorrect 36 ms 47596 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 49768 KB Output is correct
2 Incorrect 156 ms 52860 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47340 KB Output is correct
2 Correct 36 ms 47468 KB Output is correct
3 Correct 42 ms 47724 KB Output is correct
4 Correct 36 ms 47724 KB Output is correct
5 Correct 36 ms 47724 KB Output is correct
6 Correct 36 ms 47724 KB Output is correct
7 Correct 36 ms 47724 KB Output is correct
8 Correct 37 ms 47724 KB Output is correct
9 Correct 42 ms 47724 KB Output is correct
10 Incorrect 36 ms 47596 KB Output isn't correct
11 Halted 0 ms 0 KB -