답안 #58916 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58916	2018-07-19T19:51:20 Z	egorlifar	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	3819 ms	50864 KB

bubblesort2

/*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#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;


int n;
vector<int> mod;
vector<int> d;
int ss;
int where[MAXN * 2];


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


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


int border[MAXN * 2];
int a[MAXN * 2];
	vector<pair<int, int> > st;

void add(int val) {
	add(1, 1, ss, where[val], where[val], 1000000000);
	add(1, 1, ss, border[where[val] - 1] + 1, sz(st), -1);
}


void del(int val) {
	add(1, 1, ss, where[val], where[val], -1000000000);
	add(1, 1, ss, border[where[val] - 1] + 1, sz(st), 1);
}


vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
	n = sz(A);
	for (int i = 0; i < n; i++) {
		st.pb({A[i], i});
		a[i] = i;
	}
	for (int i = 0; i < sz(X); i++) {
		st.pb({V[i], n + i});
	}
	sort(all(st));
	ss = 1;
	while (ss < sz(st)) {
		ss <<= 1;
	}
	d.resize(2 * ss);
	mod.resize(2 * ss);
	for (int i = 0; i < sz(st); i++) {
		where[st[i].second] = i + 1;
		add(1, 1, ss, i + 1, i + 1, -1000000000 + (st[i].second >= n ? X[st[i].second - n]: st[i].second) + 1);
	}
	int uk = sz(st);
	for (int i = sz(st) - 1; i >= 0; i--) {
		while (uk - 1 >= 0 && st[uk - 1].first >= st[i].first) {
			uk--;
		}
		border[i] = uk;
	}	
	for (int i = 0; i < n; i++) {
		add(a[i]);
	}
	vector<int> answer;
	for (int i = 0; i < sz(X); i++) {
		del(a[X[i]]);
		a[X[i]] = n + i;
		add(a[X[i]]);
		answer.pb(d[1] + mod[1]);
	}
	return answer;
}

Subtask #1
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	376 KB	Output is correct
2	Correct	7 ms	484 KB	Output is correct
3	Correct	11 ms	632 KB	Output is correct
4	Correct	8 ms	632 KB	Output is correct
5	Correct	9 ms	632 KB	Output is correct
6	Correct	7 ms	784 KB	Output is correct
7	Correct	7 ms	800 KB	Output is correct
8	Correct	7 ms	800 KB	Output is correct
9	Correct	8 ms	800 KB	Output is correct
10	Correct	9 ms	800 KB	Output is correct
11	Correct	8 ms	800 KB	Output is correct
12	Correct	8 ms	800 KB	Output is correct
13	Correct	8 ms	800 KB	Output is correct
14	Correct	7 ms	864 KB	Output is correct
15	Correct	7 ms	864 KB	Output is correct
16	Correct	7 ms	864 KB	Output is correct
17	Correct	8 ms	864 KB	Output is correct
18	Correct	8 ms	864 KB	Output is correct

Subtask #2
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	376 KB	Output is correct
2	Correct	7 ms	484 KB	Output is correct
3	Correct	11 ms	632 KB	Output is correct
4	Correct	8 ms	632 KB	Output is correct
5	Correct	9 ms	632 KB	Output is correct
6	Correct	7 ms	784 KB	Output is correct
7	Correct	7 ms	800 KB	Output is correct
8	Correct	7 ms	800 KB	Output is correct
9	Correct	8 ms	800 KB	Output is correct
10	Correct	9 ms	800 KB	Output is correct
11	Correct	8 ms	800 KB	Output is correct
12	Correct	8 ms	800 KB	Output is correct
13	Correct	8 ms	800 KB	Output is correct
14	Correct	7 ms	864 KB	Output is correct
15	Correct	7 ms	864 KB	Output is correct
16	Correct	7 ms	864 KB	Output is correct
17	Correct	8 ms	864 KB	Output is correct
18	Correct	8 ms	864 KB	Output is correct
19	Correct	25 ms	1412 KB	Output is correct
20	Correct	28 ms	1412 KB	Output is correct
21	Correct	26 ms	1424 KB	Output is correct
22	Correct	29 ms	1568 KB	Output is correct
23	Correct	25 ms	1568 KB	Output is correct
24	Correct	25 ms	1568 KB	Output is correct
25	Correct	28 ms	1568 KB	Output is correct
26	Correct	24 ms	1568 KB	Output is correct
27	Correct	27 ms	1568 KB	Output is correct
28	Correct	25 ms	1572 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	40 ms	2104 KB	Output is correct
2	Correct	118 ms	3764 KB	Output is correct
3	Correct	235 ms	6136 KB	Output is correct
4	Correct	226 ms	6168 KB	Output is correct
5	Correct	229 ms	6304 KB	Output is correct
6	Correct	243 ms	6304 KB	Output is correct
7	Correct	233 ms	6316 KB	Output is correct
8	Correct	235 ms	6316 KB	Output is correct
9	Correct	229 ms	6316 KB	Output is correct
10	Correct	193 ms	6316 KB	Output is correct
11	Correct	191 ms	6316 KB	Output is correct
12	Correct	200 ms	6316 KB	Output is correct
13	Correct	199 ms	6316 KB	Output is correct
14	Correct	187 ms	6316 KB	Output is correct
15	Correct	212 ms	6316 KB	Output is correct
16	Correct	201 ms	6316 KB	Output is correct
17	Correct	176 ms	6316 KB	Output is correct
18	Correct	214 ms	6316 KB	Output is correct

Subtask #4
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	376 KB	Output is correct
2	Correct	7 ms	484 KB	Output is correct
3	Correct	11 ms	632 KB	Output is correct
4	Correct	8 ms	632 KB	Output is correct
5	Correct	9 ms	632 KB	Output is correct
6	Correct	7 ms	784 KB	Output is correct
7	Correct	7 ms	800 KB	Output is correct
8	Correct	7 ms	800 KB	Output is correct
9	Correct	8 ms	800 KB	Output is correct
10	Correct	9 ms	800 KB	Output is correct
11	Correct	8 ms	800 KB	Output is correct
12	Correct	8 ms	800 KB	Output is correct
13	Correct	8 ms	800 KB	Output is correct
14	Correct	7 ms	864 KB	Output is correct
15	Correct	7 ms	864 KB	Output is correct
16	Correct	7 ms	864 KB	Output is correct
17	Correct	8 ms	864 KB	Output is correct
18	Correct	8 ms	864 KB	Output is correct
19	Correct	25 ms	1412 KB	Output is correct
20	Correct	28 ms	1412 KB	Output is correct
21	Correct	26 ms	1424 KB	Output is correct
22	Correct	29 ms	1568 KB	Output is correct
23	Correct	25 ms	1568 KB	Output is correct
24	Correct	25 ms	1568 KB	Output is correct
25	Correct	28 ms	1568 KB	Output is correct
26	Correct	24 ms	1568 KB	Output is correct
27	Correct	27 ms	1568 KB	Output is correct
28	Correct	25 ms	1572 KB	Output is correct
29	Correct	40 ms	2104 KB	Output is correct
30	Correct	118 ms	3764 KB	Output is correct
31	Correct	235 ms	6136 KB	Output is correct
32	Correct	226 ms	6168 KB	Output is correct
33	Correct	229 ms	6304 KB	Output is correct
34	Correct	243 ms	6304 KB	Output is correct
35	Correct	233 ms	6316 KB	Output is correct
36	Correct	235 ms	6316 KB	Output is correct
37	Correct	229 ms	6316 KB	Output is correct
38	Correct	193 ms	6316 KB	Output is correct
39	Correct	191 ms	6316 KB	Output is correct
40	Correct	200 ms	6316 KB	Output is correct
41	Correct	199 ms	6316 KB	Output is correct
42	Correct	187 ms	6316 KB	Output is correct
43	Correct	212 ms	6316 KB	Output is correct
44	Correct	201 ms	6316 KB	Output is correct
45	Correct	176 ms	6316 KB	Output is correct
46	Correct	214 ms	6316 KB	Output is correct
47	Correct	934 ms	19224 KB	Output is correct
48	Correct	3338 ms	48116 KB	Output is correct
49	Correct	3539 ms	50744 KB	Output is correct
50	Correct	3774 ms	50744 KB	Output is correct
51	Correct	3819 ms	50864 KB	Output is correct
52	Correct	3732 ms	50864 KB	Output is correct
53	Correct	3393 ms	50864 KB	Output is correct
54	Correct	2972 ms	50864 KB	Output is correct
55	Correct	3080 ms	50864 KB	Output is correct
56	Correct	3275 ms	50864 KB	Output is correct
57	Correct	3308 ms	50864 KB	Output is correct
58	Correct	3465 ms	50864 KB	Output is correct
59	Correct	3107 ms	50864 KB	Output is correct
60	Correct	2885 ms	50864 KB	Output is correct
61	Correct	2678 ms	50864 KB	Output is correct
62	Correct	3036 ms	50864 KB	Output is correct
63	Correct	3136 ms	50864 KB	Output is correct
64	Correct	2810 ms	50864 KB	Output is correct
65	Correct	2861 ms	50864 KB	Output is correct
66	Correct	2678 ms	50864 KB	Output is correct
67	Correct	3029 ms	50864 KB	Output is correct

답안 #58916

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 21.0 / 21.0

Subtask #3 22.0 / 22.0

Subtask #4 40.0 / 40.0

Subtask #1
17.0 / 17.0

Subtask #2
21.0 / 21.0

Subtask #3
22.0 / 22.0

Subtask #4
40.0 / 40.0