oj.uz

Submission #925083

# Submission time Handle Problem Language Result Execution time Memory
925083 2024-02-10T17:56:12 Z myst6 Bubble Sort 2 (JOI18_bubblesort2) C++14
100 / 100
 4906 ms 216544 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>

using namespace std;

struct Tag {
  int add;
  Tag(int _add) : add(_add) {}
  Tag() : add(0) {}
  void apply(Tag &tag) { add += tag.add; }
};

struct Info {
  int hi;
  Info(int _hi) : hi(_hi) {}
  Info() : hi(0) {}
  void apply(Tag &tag) { hi += tag.add; }
  Info combine(Info &other) { return {max(hi, other.hi)}; }
};

struct Tree {
  vector<Tag> tag;
  vector<Info> info;
  Tree(int size) {
    tag.resize(size*4);
    info.resize(size*4);
  }
  void build(vector<Info> &base, int x, int xl, int xr) {
    if (xl == xr) {
      info[x] = base[xl];
    } else {
      int xm = (xl + xr) / 2;
      build(base, x*2, xl, xm);
      build(base, x*2+1, xm+1, xr);
      info[x] = info[x*2].combine(info[x*2+1]);
    }
  }
  void pushdown(int x) {
    info[x].apply(tag[x]);
    if (x*2 < (int) tag.size()) tag[x*2].apply(tag[x]);
    if (x*2+1 < (int) tag.size()) tag[x*2+1].apply(tag[x]);
    tag[x] = {};
  }
  void update(int l, int r, int x, int xl, int xr, Tag delta) {
    if (l > r) return;
    pushdown(x);
    if (l == xl && r == xr) {
      tag[x].apply(delta);
    } else {
      int xm = (xl + xr) / 2;
      update(l, min(r, xm), x*2, xl, xm, delta);
      update(max(l, xm+1), r, x*2+1, xm+1, xr, delta);
      pushdown(x); pushdown(x*2); pushdown(x*2+1);
      info[x] = info[x*2].combine(info[x*2+1]);
    }
  }
  Info query(int l, int r, int x, int xl, int xr) {
    if (l > r) return {};
    pushdown(x);
    if (l == xl && r == xr) {
      return info[x];
    } else {
      int xm = (xl + xr) / 2;
      Info left = query(l, min(r, xm), x*2, xl, xm);
      Info right = query(max(l, xm+1), r, x*2+1, xm+1, xr);
      return left.combine(right);
    }
  }
};

// need to only query from a number if it is smaller than everything
// to the right of it
// i.e. pick the rightmost item, then the next smallest and next and so on

// if it is smaller than everything to the right, then i can 
// count the number of items above it and subtract it from how much stuff is
// on the right, to get it ans 

// in other words, this can be done if we use a segment tree to count number below x
// we can update one of these important values

// now we just need to be able to identify and track how these values change
// for now let's just see if i can get 60 points

// ok for 100 points it shouldnt be too tricky
// i need max segment tree of the following statistic:
// - amount of numbers above this value minus this index
// - but we can do a segment tree on the values themselves
// - sgt[v] = (number of values > v) - N + 1 + highest 'j'


vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
	int N = A.size();
	int Q = X.size();
	set<int> AV;
	for (int a : A) AV.insert(a);
	for (int v : V) AV.insert(v);
	map<int,int> idxmap; int T = 0;
	for (int av : AV) idxmap[av] = T++;
	Tree tree(T);
	vector<set<int>> idx(T);
	for (int i=0; i<N; i++) {
		A[i] = idxmap[A[i]];
		idx[A[i]].insert(i);
		if (A[i] > 0) tree.update(0, A[i]-1, 1, 0, T-1, {+1});
	}
	auto updJ = [&](int i, int mul) -> void {
		int j = idx[i].empty() ? -1'000'000 : *idx[i].rbegin();
		tree.update(i, i, 1, 0, T-1, {mul * j});
	};	
	for (int i=0; i<T; i++) {
		updJ(i, +1);
	}
	vector<int> ans(Q);
	for (int i=0; i<Q; i++) {
		updJ(A[X[i]], -1);
		idx[A[X[i]]].erase(X[i]);
		updJ(A[X[i]], +1);

		if (A[X[i]] > 0) tree.update(0, A[X[i]]-1, 1, 0, T-1, {-1});
		A[X[i]] = idxmap[V[i]];
		if (A[X[i]] > 0) tree.update(0, A[X[i]]-1, 1, 0, T-1, {+1});
		
		updJ(A[X[i]], -1);
		idx[A[X[i]]].insert(X[i]);
		updJ(A[X[i]], +1);

		ans[i] = tree.query(0, T-1, 1, 0, T-1).hi - N + 1;
	}
	return ans;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 3 ms 600 KB Output is correct
3 Correct 6 ms 1116 KB Output is correct
4 Correct 6 ms 1116 KB Output is correct
5 Correct 6 ms 1116 KB Output is correct
6 Correct 6 ms 1116 KB Output is correct
7 Correct 6 ms 1112 KB Output is correct
8 Correct 6 ms 1116 KB Output is correct
9 Correct 8 ms 1112 KB Output is correct
10 Correct 5 ms 1116 KB Output is correct
11 Correct 6 ms 1116 KB Output is correct
12 Correct 6 ms 1368 KB Output is correct
13 Correct 5 ms 1116 KB Output is correct
14 Correct 5 ms 1116 KB Output is correct
15 Correct 5 ms 1116 KB Output is correct
16 Correct 5 ms 972 KB Output is correct
17 Correct 7 ms 972 KB Output is correct
18 Correct 5 ms 968 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 3 ms 600 KB Output is correct
3 Correct 6 ms 1116 KB Output is correct
4 Correct 6 ms 1116 KB Output is correct
5 Correct 6 ms 1116 KB Output is correct
6 Correct 6 ms 1116 KB Output is correct
7 Correct 6 ms 1112 KB Output is correct
8 Correct 6 ms 1116 KB Output is correct
9 Correct 8 ms 1112 KB Output is correct
10 Correct 5 ms 1116 KB Output is correct
11 Correct 6 ms 1116 KB Output is correct
12 Correct 6 ms 1368 KB Output is correct
13 Correct 5 ms 1116 KB Output is correct
14 Correct 5 ms 1116 KB Output is correct
15 Correct 5 ms 1116 KB Output is correct
16 Correct 5 ms 972 KB Output is correct
17 Correct 7 ms 972 KB Output is correct
18 Correct 5 ms 968 KB Output is correct
19 Correct 26 ms 3160 KB Output is correct
20 Correct 29 ms 3676 KB Output is correct
21 Correct 30 ms 3928 KB Output is correct
22 Correct 29 ms 3736 KB Output is correct
23 Correct 27 ms 3420 KB Output is correct
24 Correct 27 ms 3420 KB Output is correct
25 Correct 26 ms 3164 KB Output is correct
26 Correct 26 ms 3160 KB Output is correct
27 Correct 25 ms 3084 KB Output is correct
28 Correct 25 ms 3108 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1880 KB Output is correct
2 Correct 44 ms 3000 KB Output is correct
3 Correct 86 ms 4156 KB Output is correct
4 Correct 78 ms 3928 KB Output is correct
5 Correct 77 ms 3920 KB Output is correct
6 Correct 77 ms 3928 KB Output is correct
7 Correct 79 ms 4164 KB Output is correct
8 Correct 77 ms 4184 KB Output is correct
9 Correct 76 ms 3928 KB Output is correct
10 Correct 65 ms 3928 KB Output is correct
11 Correct 66 ms 4152 KB Output is correct
12 Correct 65 ms 4180 KB Output is correct
13 Correct 68 ms 4176 KB Output is correct
14 Correct 63 ms 3968 KB Output is correct
15 Correct 67 ms 4432 KB Output is correct
16 Correct 63 ms 3932 KB Output is correct
17 Correct 61 ms 3920 KB Output is correct
18 Correct 59 ms 4156 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 3 ms 600 KB Output is correct
3 Correct 6 ms 1116 KB Output is correct
4 Correct 6 ms 1116 KB Output is correct
5 Correct 6 ms 1116 KB Output is correct
6 Correct 6 ms 1116 KB Output is correct
7 Correct 6 ms 1112 KB Output is correct
8 Correct 6 ms 1116 KB Output is correct
9 Correct 8 ms 1112 KB Output is correct
10 Correct 5 ms 1116 KB Output is correct
11 Correct 6 ms 1116 KB Output is correct
12 Correct 6 ms 1368 KB Output is correct
13 Correct 5 ms 1116 KB Output is correct
14 Correct 5 ms 1116 KB Output is correct
15 Correct 5 ms 1116 KB Output is correct
16 Correct 5 ms 972 KB Output is correct
17 Correct 7 ms 972 KB Output is correct
18 Correct 5 ms 968 KB Output is correct
19 Correct 26 ms 3160 KB Output is correct
20 Correct 29 ms 3676 KB Output is correct
21 Correct 30 ms 3928 KB Output is correct
22 Correct 29 ms 3736 KB Output is correct
23 Correct 27 ms 3420 KB Output is correct
24 Correct 27 ms 3420 KB Output is correct
25 Correct 26 ms 3164 KB Output is correct
26 Correct 26 ms 3160 KB Output is correct
27 Correct 25 ms 3084 KB Output is correct
28 Correct 25 ms 3108 KB Output is correct
29 Correct 13 ms 1880 KB Output is correct
30 Correct 44 ms 3000 KB Output is correct
31 Correct 86 ms 4156 KB Output is correct
32 Correct 78 ms 3928 KB Output is correct
33 Correct 77 ms 3920 KB Output is correct
34 Correct 77 ms 3928 KB Output is correct
35 Correct 79 ms 4164 KB Output is correct
36 Correct 77 ms 4184 KB Output is correct
37 Correct 76 ms 3928 KB Output is correct
38 Correct 65 ms 3928 KB Output is correct
39 Correct 66 ms 4152 KB Output is correct
40 Correct 65 ms 4180 KB Output is correct
41 Correct 68 ms 4176 KB Output is correct
42 Correct 63 ms 3968 KB Output is correct
43 Correct 67 ms 4432 KB Output is correct
44 Correct 63 ms 3932 KB Output is correct
45 Correct 61 ms 3920 KB Output is correct
46 Correct 59 ms 4156 KB Output is correct
47 Correct 981 ms 62868 KB Output is correct
48 Correct 4167 ms 196452 KB Output is correct
49 Correct 4689 ms 216140 KB Output is correct
50 Correct 4642 ms 216104 KB Output is correct
51 Correct 4733 ms 216356 KB Output is correct
52 Correct 4881 ms 216404 KB Output is correct
53 Correct 4906 ms 216544 KB Output is correct
54 Correct 4288 ms 216240 KB Output is correct
55 Correct 4552 ms 215948 KB Output is correct
56 Correct 4177 ms 216120 KB Output is correct
57 Correct 4394 ms 216148 KB Output is correct
58 Correct 4102 ms 216276 KB Output is correct
59 Correct 3776 ms 194420 KB Output is correct
60 Correct 3825 ms 194304 KB Output is correct
61 Correct 3828 ms 194336 KB Output is correct
62 Correct 3477 ms 183636 KB Output is correct
63 Correct 3548 ms 183632 KB Output is correct
64 Correct 3484 ms 183476 KB Output is correct
65 Correct 3226 ms 172372 KB Output is correct
66 Correct 3304 ms 172696 KB Output is correct
67 Correct 3358 ms 172832 KB Output is correct