답안 #496082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
496082	2021-12-20T15:07:14 Z	600Mihnea	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	3873 ms	130904 KB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 7;
const int NAX = (int) 1e6 + 7;
int N;
int coef[NAX];
int value[NAX];
bool valid[NAX];

int lazy[4 * NAX];
int tree[4 * NAX];

void add(int v, int tl, int tr, int l, int r, int x) {
  if (lazy[v]) {
    tree[v] += lazy[v];
    if (tl < tr) {
      lazy[2 * v] += lazy[v];
      lazy[2 * v + 1] += lazy[v];
    }
    lazy[v] = 0;
  }
  if (tr < l || r < tl) {
    return;
  }
  if (l <= tl && tr <= r) {
    lazy[v] += x;
    tree[v] += lazy[v];
    if (tl < tr) {
      lazy[2 * v] += lazy[v];
      lazy[2 * v + 1] += lazy[v];
    }
    lazy[v] = 0;
    return;
  }
  int tm = (tl + tr) / 2;
  add(2 * v, tl, tm, l, r, x);
  add(2 * v + 1, tm + 1, tr, l, r, x);
  tree[v] = max(tree[2 * v], tree[2 * v + 1]);
}

void add(int l, int r, int x) {
  add(1, 1, N, l, r, x);
}

int getMax() {
  return tree[1];
}

vector<int> innterCountScans(vector<ll> a, vector<int> pos, vector<ll> ChangeValue) {
  int n = (int) a.size();
  int q = (int) pos.size();

  for (int i = 0; i < n; i++) {
    a[i] = a[i] * (ll) (n + 1) + i;
  }


  for (int it = 0; it < q; it++) {
    ChangeValue[it] = ChangeValue[it] * (ll) (n + 1) + pos[it];
  }

  map<ll, int> mp;
  for (auto &x : a) {
    mp[x] = 0;
  }
  for (auto &x : ChangeValue) {
    mp[x] = 0;
  }

  {
    int ij = 0;
    for (auto &it : mp) {
      it.second = ++ij;
    }
    N = ij;
    assert(N <= n + q);
  }

  for (auto &x : a) {
    x = mp[x];
  }
  for (auto &x : ChangeValue) {
    x = mp[x];
  }

  for (int i = 1; i <= N; i++) {
    coef[i] = -INF;
  }
  add(1, N, -INF);


  for (int i = 0; i < n; i++) {
    valid[a[i]] = 1;
    add(a[i], a[i], i - coef[a[i]]);

    coef[a[i]] += i - coef[a[i]];
    add(a[i], N, -1);
  }


  vector<int> sol;

  for (int it = 0; it < q; it++) {
    if (1) {
      valid[a[pos[it]]] = 0;
      add(a[pos[it]], N, +1);
      add(a[pos[it]], a[pos[it]], -(coef[a[pos[it]]] + INF));
      coef[a[pos[it]]] += -(coef[a[pos[it]]] + INF);

      a[pos[it]] = ChangeValue[it];

      valid[a[pos[it]]] = 1;
      add(a[pos[it]], N, -1);
      add(a[pos[it]], a[pos[it]], pos[it] - coef[a[pos[it]]]);
      coef[a[pos[it]]] += pos[it] - coef[a[pos[it]]];
    }

    sol.push_back(getMax() + 1);
  }

  return sol;
}


vector<int> countScans(vector<int> a, vector<int> b, vector<int> c) {
  vector<ll> X, Z;
  for (auto &it : a) {
    X.push_back(it);
  }
  for (auto &it : c) {
    Z.push_back(it);
  }
  return innterCountScans(X, b, Z);
}

Subtask #1
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	460 KB	Output is correct
2	Correct	3 ms	460 KB	Output is correct
3	Correct	5 ms	716 KB	Output is correct
4	Correct	5 ms	716 KB	Output is correct
5	Correct	5 ms	716 KB	Output is correct
6	Correct	7 ms	716 KB	Output is correct
7	Correct	6 ms	792 KB	Output is correct
8	Correct	5 ms	716 KB	Output is correct
9	Correct	6 ms	776 KB	Output is correct
10	Correct	5 ms	716 KB	Output is correct
11	Correct	5 ms	716 KB	Output is correct
12	Correct	5 ms	716 KB	Output is correct
13	Correct	5 ms	724 KB	Output is correct
14	Correct	5 ms	716 KB	Output is correct
15	Correct	5 ms	716 KB	Output is correct
16	Correct	4 ms	716 KB	Output is correct
17	Correct	4 ms	716 KB	Output is correct
18	Correct	4 ms	716 KB	Output is correct

Subtask #2
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	460 KB	Output is correct
2	Correct	3 ms	460 KB	Output is correct
3	Correct	5 ms	716 KB	Output is correct
4	Correct	5 ms	716 KB	Output is correct
5	Correct	5 ms	716 KB	Output is correct
6	Correct	7 ms	716 KB	Output is correct
7	Correct	6 ms	792 KB	Output is correct
8	Correct	5 ms	716 KB	Output is correct
9	Correct	6 ms	776 KB	Output is correct
10	Correct	5 ms	716 KB	Output is correct
11	Correct	5 ms	716 KB	Output is correct
12	Correct	5 ms	716 KB	Output is correct
13	Correct	5 ms	724 KB	Output is correct
14	Correct	5 ms	716 KB	Output is correct
15	Correct	5 ms	716 KB	Output is correct
16	Correct	4 ms	716 KB	Output is correct
17	Correct	4 ms	716 KB	Output is correct
18	Correct	4 ms	716 KB	Output is correct
19	Correct	18 ms	1948 KB	Output is correct
20	Correct	22 ms	2140 KB	Output is correct
21	Correct	22 ms	2124 KB	Output is correct
22	Correct	23 ms	2156 KB	Output is correct
23	Correct	20 ms	2092 KB	Output is correct
24	Correct	20 ms	2056 KB	Output is correct
25	Correct	19 ms	2008 KB	Output is correct
26	Correct	24 ms	1996 KB	Output is correct
27	Correct	20 ms	1864 KB	Output is correct
28	Correct	20 ms	1876 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	3576 KB	Output is correct
2	Correct	97 ms	7680 KB	Output is correct
3	Correct	236 ms	12396 KB	Output is correct
4	Correct	213 ms	12528 KB	Output is correct
5	Correct	159 ms	12364 KB	Output is correct
6	Correct	179 ms	12284 KB	Output is correct
7	Correct	198 ms	12276 KB	Output is correct
8	Correct	181 ms	12308 KB	Output is correct
9	Correct	188 ms	12236 KB	Output is correct
10	Correct	166 ms	8384 KB	Output is correct
11	Correct	112 ms	8296 KB	Output is correct
12	Correct	127 ms	8288 KB	Output is correct
13	Correct	119 ms	8304 KB	Output is correct
14	Correct	114 ms	8296 KB	Output is correct
15	Correct	114 ms	8360 KB	Output is correct
16	Correct	108 ms	8384 KB	Output is correct
17	Correct	110 ms	8412 KB	Output is correct
18	Correct	106 ms	8436 KB	Output is correct

Subtask #4
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	460 KB	Output is correct
2	Correct	3 ms	460 KB	Output is correct
3	Correct	5 ms	716 KB	Output is correct
4	Correct	5 ms	716 KB	Output is correct
5	Correct	5 ms	716 KB	Output is correct
6	Correct	7 ms	716 KB	Output is correct
7	Correct	6 ms	792 KB	Output is correct
8	Correct	5 ms	716 KB	Output is correct
9	Correct	6 ms	776 KB	Output is correct
10	Correct	5 ms	716 KB	Output is correct
11	Correct	5 ms	716 KB	Output is correct
12	Correct	5 ms	716 KB	Output is correct
13	Correct	5 ms	724 KB	Output is correct
14	Correct	5 ms	716 KB	Output is correct
15	Correct	5 ms	716 KB	Output is correct
16	Correct	4 ms	716 KB	Output is correct
17	Correct	4 ms	716 KB	Output is correct
18	Correct	4 ms	716 KB	Output is correct
19	Correct	18 ms	1948 KB	Output is correct
20	Correct	22 ms	2140 KB	Output is correct
21	Correct	22 ms	2124 KB	Output is correct
22	Correct	23 ms	2156 KB	Output is correct
23	Correct	20 ms	2092 KB	Output is correct
24	Correct	20 ms	2056 KB	Output is correct
25	Correct	19 ms	2008 KB	Output is correct
26	Correct	24 ms	1996 KB	Output is correct
27	Correct	20 ms	1864 KB	Output is correct
28	Correct	20 ms	1876 KB	Output is correct
29	Correct	31 ms	3576 KB	Output is correct
30	Correct	97 ms	7680 KB	Output is correct
31	Correct	236 ms	12396 KB	Output is correct
32	Correct	213 ms	12528 KB	Output is correct
33	Correct	159 ms	12364 KB	Output is correct
34	Correct	179 ms	12284 KB	Output is correct
35	Correct	198 ms	12276 KB	Output is correct
36	Correct	181 ms	12308 KB	Output is correct
37	Correct	188 ms	12236 KB	Output is correct
38	Correct	166 ms	8384 KB	Output is correct
39	Correct	112 ms	8296 KB	Output is correct
40	Correct	127 ms	8288 KB	Output is correct
41	Correct	119 ms	8304 KB	Output is correct
42	Correct	114 ms	8296 KB	Output is correct
43	Correct	114 ms	8360 KB	Output is correct
44	Correct	108 ms	8384 KB	Output is correct
45	Correct	110 ms	8412 KB	Output is correct
46	Correct	106 ms	8436 KB	Output is correct
47	Correct	881 ms	38732 KB	Output is correct
48	Correct	3489 ms	121268 KB	Output is correct
49	Correct	3674 ms	130496 KB	Output is correct
50	Correct	3728 ms	130572 KB	Output is correct
51	Correct	3779 ms	130684 KB	Output is correct
52	Correct	3873 ms	130476 KB	Output is correct
53	Correct	3796 ms	130580 KB	Output is correct
54	Correct	3503 ms	130560 KB	Output is correct
55	Correct	3720 ms	130904 KB	Output is correct
56	Correct	3391 ms	130852 KB	Output is correct
57	Correct	3662 ms	130804 KB	Output is correct
58	Correct	3254 ms	130820 KB	Output is correct
59	Correct	2820 ms	120988 KB	Output is correct
60	Correct	2973 ms	120880 KB	Output is correct
61	Correct	2948 ms	120948 KB	Output is correct
62	Correct	2871 ms	116520 KB	Output is correct
63	Correct	2873 ms	116700 KB	Output is correct
64	Correct	2881 ms	116644 KB	Output is correct
65	Correct	2673 ms	112120 KB	Output is correct
66	Correct	2703 ms	112076 KB	Output is correct
67	Correct	2652 ms	112228 KB	Output is correct

답안 #496082

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