답안 #813153

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
813153	2023-08-07T13:56:46 Z	SlavicG	Bubble Sort 2 (JOI18_bubblesort2)	C++17	38 / 100	1066 ms	118644 KB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;

#define ll int64_t

const ll inf = 1e9;
const int N = 4e6 + 5;
ll t[4 * N], lazy[4 * N];
void push(int i, int l, int r) {
	if(!lazy[i]) return;
	t[i] += lazy[i];
	if(l != r) {
		lazy[2 * i] += lazy[i];
		lazy[2 * i + 1] += lazy[i];
	}
	lazy[i] = 0;
}
void modif(int i, int l, int r, int tl, int tr, ll val) {
	push(i, l, r);
	if(l > tr || r < tl) return;
	if(l >= tl && r <= tr) {
		lazy[i] += val;
		push(i, l,r);
		return;
	}
	int mid = l + r >> 1;
	modif(2 * i, l, mid, tl, tr, val);
	modif(2 * i + 1, mid + 1, r, tl, tr, val);
	t[i] = max(t[2 * i], t[2 * i + 1]);
}
std::vector<int> countScans(vector<int> a, vector<int> X, vector<int> V){
	int n = a.size();
	int q = X.size();
	vector<int> ans(q);
	vector<int> cnt(n, 0);
	vector<ll> c(n);
	vector<ll> vals;
	//compresam coordonatele si ne asiguram sa nu avem duplicate
	for(int i = 0; i < n; ++i) {
		vals.push_back(inf * (ll)a[i] + i); 
	}
	for(int k = 0; k < q; ++k) {
		int i = X[k];
		ll newval = inf * V[k] + i;
		vals.push_back(newval);
	}
	sort(vals.begin(), vals.end());
	vals.erase(unique(vals.begin(), vals.end()), vals.end());
	for(int i = 0; i < n; ++i) {
		a[i] = lower_bound(vals.begin(), vals.end(), (ll)a[i] * (ll)inf + i) - vals.begin();
	}
	for(int k = 0; k < q; ++k) {
		int i = X[k];
		ll newval = inf * V[k] + i;
		V[k] = lower_bound(vals.begin(), vals.end(), newval) - vals.begin();
	}


	//acum rezolvam problema dupa ce am compresat tot
	for(int i = 0; i < N; ++i) modif(1, 0, N - 1, i, i, -inf);

	for(int i = 0; i < n; ++i) {
		modif(1, 0, N - 1, a[i], a[i], inf + i);
	}
	for(int i = 0; i < n; ++i) {
		modif(1, 0, N - 1, a[i] + 1, N - 1, -1);
	}
	for(int k = 0; k < q; ++k) {
		int i = X[k], newval = V[k];
		modif(1, 0, N - 1, a[i] + 1, N - 1, +1);
		modif(1, 0, N - 1, a[i], a[i], -2 * inf - i);
		a[i] = newval;
		modif(1, 0, N - 1, a[i], a[i], inf + i);
		modif(1, 0, N - 1, a[i] + 1, N - 1, -1);
		ans[k] = t[1]; 
	}


	return ans;
}
/*
4 2
1 2 3 4
0 3
2 1
*/

Compilation message

bubblesort2.cpp: In function 'void modif(int, int, int, int, int, int64_t)':
bubblesort2.cpp:27:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |  int mid = l + r >> 1;
      |            ~~^~~

Subtask #1
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	917 ms	115236 KB	Output is correct
2	Correct	952 ms	115256 KB	Output is correct
3	Correct	959 ms	115352 KB	Output is correct
4	Correct	984 ms	115328 KB	Output is correct
5	Correct	951 ms	115332 KB	Output is correct
6	Correct	935 ms	115420 KB	Output is correct
7	Correct	932 ms	115436 KB	Output is correct
8	Correct	956 ms	115368 KB	Output is correct
9	Correct	940 ms	115496 KB	Output is correct
10	Correct	953 ms	115440 KB	Output is correct
11	Correct	938 ms	115448 KB	Output is correct
12	Correct	975 ms	115404 KB	Output is correct
13	Correct	933 ms	115436 KB	Output is correct
14	Correct	964 ms	115388 KB	Output is correct
15	Correct	934 ms	115440 KB	Output is correct
16	Correct	955 ms	115424 KB	Output is correct
17	Correct	932 ms	115348 KB	Output is correct
18	Correct	934 ms	115460 KB	Output is correct

Subtask #2
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	917 ms	115236 KB	Output is correct
2	Correct	952 ms	115256 KB	Output is correct
3	Correct	959 ms	115352 KB	Output is correct
4	Correct	984 ms	115328 KB	Output is correct
5	Correct	951 ms	115332 KB	Output is correct
6	Correct	935 ms	115420 KB	Output is correct
7	Correct	932 ms	115436 KB	Output is correct
8	Correct	956 ms	115368 KB	Output is correct
9	Correct	940 ms	115496 KB	Output is correct
10	Correct	953 ms	115440 KB	Output is correct
11	Correct	938 ms	115448 KB	Output is correct
12	Correct	975 ms	115404 KB	Output is correct
13	Correct	933 ms	115436 KB	Output is correct
14	Correct	964 ms	115388 KB	Output is correct
15	Correct	934 ms	115440 KB	Output is correct
16	Correct	955 ms	115424 KB	Output is correct
17	Correct	932 ms	115348 KB	Output is correct
18	Correct	934 ms	115460 KB	Output is correct
19	Correct	1008 ms	115852 KB	Output is correct
20	Correct	955 ms	115920 KB	Output is correct
21	Correct	972 ms	115896 KB	Output is correct
22	Correct	953 ms	115840 KB	Output is correct
23	Correct	948 ms	115896 KB	Output is correct
24	Correct	945 ms	115956 KB	Output is correct
25	Correct	943 ms	115824 KB	Output is correct
26	Correct	933 ms	115948 KB	Output is correct
27	Correct	948 ms	115824 KB	Output is correct
28	Correct	937 ms	115904 KB	Output is correct

Subtask #3
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1012 ms	116324 KB	Output is correct
2	Correct	1010 ms	117348 KB	Output is correct
3	Correct	1049 ms	118600 KB	Output is correct
4	Correct	1066 ms	118580 KB	Output is correct
5	Correct	1042 ms	118616 KB	Output is correct
6	Correct	1048 ms	118460 KB	Output is correct
7	Correct	1041 ms	118644 KB	Output is correct
8	Correct	1043 ms	118532 KB	Output is correct
9	Correct	1046 ms	118520 KB	Output is correct
10	Incorrect	1025 ms	118328 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #4
0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	917 ms	115236 KB	Output is correct
2	Correct	952 ms	115256 KB	Output is correct
3	Correct	959 ms	115352 KB	Output is correct
4	Correct	984 ms	115328 KB	Output is correct
5	Correct	951 ms	115332 KB	Output is correct
6	Correct	935 ms	115420 KB	Output is correct
7	Correct	932 ms	115436 KB	Output is correct
8	Correct	956 ms	115368 KB	Output is correct
9	Correct	940 ms	115496 KB	Output is correct
10	Correct	953 ms	115440 KB	Output is correct
11	Correct	938 ms	115448 KB	Output is correct
12	Correct	975 ms	115404 KB	Output is correct
13	Correct	933 ms	115436 KB	Output is correct
14	Correct	964 ms	115388 KB	Output is correct
15	Correct	934 ms	115440 KB	Output is correct
16	Correct	955 ms	115424 KB	Output is correct
17	Correct	932 ms	115348 KB	Output is correct
18	Correct	934 ms	115460 KB	Output is correct
19	Correct	1008 ms	115852 KB	Output is correct
20	Correct	955 ms	115920 KB	Output is correct
21	Correct	972 ms	115896 KB	Output is correct
22	Correct	953 ms	115840 KB	Output is correct
23	Correct	948 ms	115896 KB	Output is correct
24	Correct	945 ms	115956 KB	Output is correct
25	Correct	943 ms	115824 KB	Output is correct
26	Correct	933 ms	115948 KB	Output is correct
27	Correct	948 ms	115824 KB	Output is correct
28	Correct	937 ms	115904 KB	Output is correct
29	Correct	1012 ms	116324 KB	Output is correct
30	Correct	1010 ms	117348 KB	Output is correct
31	Correct	1049 ms	118600 KB	Output is correct
32	Correct	1066 ms	118580 KB	Output is correct
33	Correct	1042 ms	118616 KB	Output is correct
34	Correct	1048 ms	118460 KB	Output is correct
35	Correct	1041 ms	118644 KB	Output is correct
36	Correct	1043 ms	118532 KB	Output is correct
37	Correct	1046 ms	118520 KB	Output is correct
38	Incorrect	1025 ms	118328 KB	Output isn't correct
39	Halted	0 ms	0 KB	-

답안 #813153

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 21.0 / 21.0

Subtask #3 0 / 22.0

Subtask #4 0 / 40.0

Subtask #1
17.0 / 17.0

Subtask #2
21.0 / 21.0

Subtask #3
0 / 22.0

Subtask #4
0 / 40.0