oj.uz

Submission #57637

# Submission time Handle Problem Language Result Execution time Memory
57637 2018-07-15T15:45:32 Z egorlifar Bubble Sort 2 (JOI18_bubblesort2) C++17
60 / 100
 9000 ms 46860 KB 
/*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#pragma GCC target("sse4,tune=native")
#pragma GCC optimize("O3","unroll-loops")
#include "bubblesort2.h"
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <iomanip>
#include <deque>
    
     
using namespace std;
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define next next228
#define rank rank228
#define prev prev228
#define y1 y1228                                                         
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define x first
#define y second
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; } 
const string FILENAME = "input";
const int MAXN = 500228;
const int block = 750;


int n;
int id[MAXN * 2];
int who[MAXN * 2];
vector<pair<int, int> > st[MAXN];
vector<int> mod[MAXN];
vector<int> d[MAXN];
int ss[MAXN];
int pos[MAXN * 2];



inline void push(const int &i, const int &v) {
	if (mod[i][v]) {
		d[i][v] += mod[i][v];
		if (v < ss[i]) {
			mod[i][v << 1] += mod[i][v];
			mod[i][(v << 1) + 1] += mod[i][v];
		}
		mod[i][v] = 0;
	}
}


void add(const int &i, int v, int vl, int vr, const int &l, const int &r, const int &x) {
	if (vl > r || vr < l) {
		push(i, v);
		return;
	}
	if (l <= vl && vr <= r) {
		mod[i][v] += x;
		push(i, v);
		return;
	}
	push(i, v);
	int vn = v << 1;
	int vm = (vl + vr) >> 1; 
	add(i, vn, vl, vm, l, r, x);
	add(i, vn + 1, vm + 1, vr, l, r, x);
	d[i][v] = max(d[i][vn], d[i][vn + 1]);
}


bool need = false;


void add(int i) {
	int cnt = 1000000000;
	for (int j = i - 1; j >= i - (i % block); j--) {
		if (who[id[j]] > who[id[i]]) {
			cnt++;
		}
	}
	int ids = i / block;
	add((ids), 1, 1, ss[(ids)], pos[id[i]], pos[id[i]], cnt);
	for (int j = (ids) + 1; j <= (n - 1) / block; j++) {
		int t = lower_bound(all(st[j]), make_pair(who[id[i]], 0)) - st[j].begin();
		if (t) {
			add(j, 1, 1, ss[j], 1, t, 1);
		}
	}
}



int res[MAXN * 2];


void deladd(int i, int nid) {
	int ids = i / block;
	int bmax = min(i - (i % block) + block - 1, n - 1);
	for (int j = 1; j < 2 * ss[ids]; j++) {
		push(ids, j);
	}
	for (int j = 0; j < sz(st[ids]); j++) {
		res[st[ids][j].second] = d[ids][ss[ids] + j];
	}
	st[ids].pb({who[nid], nid});
	int cur = sz(st[ids]) - 1;
	while (cur && st[ids][cur] < st[ids][cur - 1]) {
		swap(st[ids][cur], st[ids][cur - 1]);
		cur--;
	}
	for (int j = i + 1; j <= bmax; j++) {
		int cnt = 0;
		if (who[id[j]] < who[id[i]]) {
			cnt--;
		}
		if (who[id[j]] < who[nid]) {
			cnt++;
		}
		if (cnt != 0) {
			res[id[j]] += cnt;
		}
	}
	int cnt = 0;
	for (int j = i - 1; j >= i - (i % block); j--) {
		if (who[id[j]] > who[nid]) {
			cnt++;
		}
	}
	res[nid] = cnt;
	for (int j = (ids) - 1; j >= 0; j--) {
		int t = upper_bound(all(st[j]), make_pair(who[nid], 1000000000)) - st[j].begin();
		res[nid] += sz(st[j]) - t;
	}
	int pos = 0;
	for (int j = 0; j < sz(st[ids]); j++) {
		if (st[ids][j].second == id[i]) {
			swap(st[ids][j], st[ids].back());
			pos = j;
			break;
		}
	}
	st[ids].pop_back();
	while (pos < sz(st[ids]) - 1) {
		swap(st[ids][pos], st[ids][pos + 1]);
		pos++;
	}
	for (int j = 0; j < sz(st[ids]); j++) {
		d[ids][ss[ids] + j] = res[st[ids][j].second];
		mod[ids][ss[ids] + j] = 0;
	}
	for (int j = ss[ids] - 1; j >= 1; j--) {
		d[ids][j] = max(d[ids][j * 2], d[ids][j * 2 + 1]);
		mod[ids][j] = 0;
	}
	for (int j = (ids) + 1; j <= (n - 1) / block; j++) {
		int t = lower_bound(all(st[j]), make_pair(who[id[i]], 0)) - st[j].begin();
		int t1 = lower_bound(all(st[j]), make_pair(who[nid], 0)) - st[j].begin();
		//1 - t === -1
		//1 - t1 == +1;
		if (t != t1) {
			if (t == 0 && t1 != 0) {
				add(j, 1, 1, ss[j], 1, t1, 1);
			} else if (t1 == 0 && t != 0) {
				add(j, 1, 1, ss[j], 1, t, -1);
			} else {
				if (t < t1) {
					add(j, 1, 1, ss[j], t + 1, t1, 1);
				} else {
					add(j, 1, 1, ss[j], t1 + 1, t, -1);
				}
			}
		}
	}
}




std::vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
	n = sz(A);
	for (int i = 0; i < n; i++) {
		st[(i / block)].pb({A[i], i});
		id[i] = i;
		who[i] = A[i];
	}
	vector<int> answer;
	for (int i = 0; i <= (n - 1) / block; i++) {
		sort(all(st[i]));
		ss[i] = 1;
		while (ss[i] < sz(st[i])) {
			ss[i] <<= 1;
		}
		d[i].resize(2 * ss[i]);
		mod[i].resize(2 * ss[i]);
		for (int j = 0; j < sz(st[i]); j++) {
			pos[st[i][j].second] = j + 1;
		}
		for (int j = 0; j < 2 * ss[i]; j++) {
			d[i][j] = -1e9;
			mod[i][j] = 0;
		}
	}
	for (int i = 0; i < n; i++) {
		add(i);
	}
	need = true;
	//exit(0);
	for (int i = 0; i < sz(X); i++) {
		who[n + i] = V[i];
		deladd(X[i], n + i);
		id[X[i]] = n + i;
		int res = 0;
		for (int j = 0; j <= (n - 1) / block; j++) {
			chkmax(res, d[j][1] + mod[j][1]);
		}
		answer.pb(res);
	}
	return answer;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 35704 KB Output is correct
2 Correct 61 ms 35704 KB Output is correct
3 Correct 70 ms 35736 KB Output is correct
4 Correct 82 ms 35992 KB Output is correct
5 Correct 67 ms 35992 KB Output is correct
6 Correct 68 ms 35992 KB Output is correct
7 Correct 69 ms 35992 KB Output is correct
8 Correct 65 ms 35992 KB Output is correct
9 Correct 63 ms 35992 KB Output is correct
10 Correct 75 ms 35992 KB Output is correct
11 Correct 60 ms 35992 KB Output is correct
12 Correct 76 ms 35992 KB Output is correct
13 Correct 71 ms 36064 KB Output is correct
14 Correct 56 ms 36112 KB Output is correct
15 Correct 56 ms 36112 KB Output is correct
16 Correct 52 ms 36112 KB Output is correct
17 Correct 63 ms 36156 KB Output is correct
18 Correct 72 ms 36156 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 35704 KB Output is correct
2 Correct 61 ms 35704 KB Output is correct
3 Correct 70 ms 35736 KB Output is correct
4 Correct 82 ms 35992 KB Output is correct
5 Correct 67 ms 35992 KB Output is correct
6 Correct 68 ms 35992 KB Output is correct
7 Correct 69 ms 35992 KB Output is correct
8 Correct 65 ms 35992 KB Output is correct
9 Correct 63 ms 35992 KB Output is correct
10 Correct 75 ms 35992 KB Output is correct
11 Correct 60 ms 35992 KB Output is correct
12 Correct 76 ms 35992 KB Output is correct
13 Correct 71 ms 36064 KB Output is correct
14 Correct 56 ms 36112 KB Output is correct
15 Correct 56 ms 36112 KB Output is correct
16 Correct 52 ms 36112 KB Output is correct
17 Correct 63 ms 36156 KB Output is correct
18 Correct 72 ms 36156 KB Output is correct
19 Correct 248 ms 36516 KB Output is correct
20 Correct 233 ms 36692 KB Output is correct
21 Correct 191 ms 36692 KB Output is correct
22 Correct 225 ms 36692 KB Output is correct
23 Correct 202 ms 36692 KB Output is correct
24 Correct 210 ms 36780 KB Output is correct
25 Correct 267 ms 36780 KB Output is correct
26 Correct 183 ms 36780 KB Output is correct
27 Correct 144 ms 36788 KB Output is correct
28 Correct 168 ms 36788 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 37548 KB Output is correct
2 Correct 1791 ms 38972 KB Output is correct
3 Correct 3561 ms 40420 KB Output is correct
4 Correct 3848 ms 40420 KB Output is correct
5 Correct 2894 ms 40488 KB Output is correct
6 Correct 3025 ms 40488 KB Output is correct
7 Correct 2534 ms 40488 KB Output is correct
8 Correct 2747 ms 40488 KB Output is correct
9 Correct 2639 ms 40488 KB Output is correct
10 Correct 743 ms 40488 KB Output is correct
11 Correct 870 ms 40488 KB Output is correct
12 Correct 680 ms 40488 KB Output is correct
13 Correct 591 ms 40488 KB Output is correct
14 Correct 550 ms 40488 KB Output is correct
15 Correct 598 ms 40488 KB Output is correct
16 Correct 513 ms 40488 KB Output is correct
17 Correct 512 ms 40488 KB Output is correct
18 Correct 605 ms 40488 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 35704 KB Output is correct
2 Correct 61 ms 35704 KB Output is correct
3 Correct 70 ms 35736 KB Output is correct
4 Correct 82 ms 35992 KB Output is correct
5 Correct 67 ms 35992 KB Output is correct
6 Correct 68 ms 35992 KB Output is correct
7 Correct 69 ms 35992 KB Output is correct
8 Correct 65 ms 35992 KB Output is correct
9 Correct 63 ms 35992 KB Output is correct
10 Correct 75 ms 35992 KB Output is correct
11 Correct 60 ms 35992 KB Output is correct
12 Correct 76 ms 35992 KB Output is correct
13 Correct 71 ms 36064 KB Output is correct
14 Correct 56 ms 36112 KB Output is correct
15 Correct 56 ms 36112 KB Output is correct
16 Correct 52 ms 36112 KB Output is correct
17 Correct 63 ms 36156 KB Output is correct
18 Correct 72 ms 36156 KB Output is correct
19 Correct 248 ms 36516 KB Output is correct
20 Correct 233 ms 36692 KB Output is correct
21 Correct 191 ms 36692 KB Output is correct
22 Correct 225 ms 36692 KB Output is correct
23 Correct 202 ms 36692 KB Output is correct
24 Correct 210 ms 36780 KB Output is correct
25 Correct 267 ms 36780 KB Output is correct
26 Correct 183 ms 36780 KB Output is correct
27 Correct 144 ms 36788 KB Output is correct
28 Correct 168 ms 36788 KB Output is correct
29 Correct 322 ms 37548 KB Output is correct
30 Correct 1791 ms 38972 KB Output is correct
31 Correct 3561 ms 40420 KB Output is correct
32 Correct 3848 ms 40420 KB Output is correct
33 Correct 2894 ms 40488 KB Output is correct
34 Correct 3025 ms 40488 KB Output is correct
35 Correct 2534 ms 40488 KB Output is correct
36 Correct 2747 ms 40488 KB Output is correct
37 Correct 2639 ms 40488 KB Output is correct
38 Correct 743 ms 40488 KB Output is correct
39 Correct 870 ms 40488 KB Output is correct
40 Correct 680 ms 40488 KB Output is correct
41 Correct 591 ms 40488 KB Output is correct
42 Correct 550 ms 40488 KB Output is correct
43 Correct 598 ms 40488 KB Output is correct
44 Correct 513 ms 40488 KB Output is correct
45 Correct 512 ms 40488 KB Output is correct
46 Correct 605 ms 40488 KB Output is correct
47 Execution timed out 9028 ms 46860 KB Time limit exceeded
48 Halted 0 ms 0 KB -