oj.uz

Submission #392207

# Submission time Handle Problem Language Result Execution time Memory
392207 2021-04-20T16:00:43 Z muhammad_hokimiyon Bubble Sort 2 (JOI18_bubblesort2) C++14
100 / 100
 4412 ms 314096 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1000500;

int G;
int a[maxn];
set<int> s[4 * maxn];
int f[4 * maxn];
int t[4 * maxn];
int lz[4 * maxn];

void push(int x)
{
    lz[x + x] += lz[x];
    lz[x + x + 1] += lz[x];
    t[x + x] += lz[x];
    t[x + x + 1] += lz[x];
    lz[x] = 0;
}

void upd(int x, int l, int r, int p, int val)
{
    if(l == r){
        t[x] -= f[x];
        if(val > 0)s[x].insert(val);
        else s[x].erase(-val);
        if(s[x].empty())f[x] = 0;
        else f[x] = *--s[x].end();
        t[x] += f[x];
        return;
    }
    push(x);
    int m = (l + r) / 2;
    if(p <= m)upd(x + x, l, m, p, val);
    else upd(x + x + 1, m + 1, r, p, val);
    t[x] = max(t[x + x], t[x + x + 1]);
}

void upd(int x, int l, int r, int tl, int tr, int val)
{
    if(tl > tr)return;
    if(l == tl && r == tr){
        t[x] += val;
        lz[x] += val;
        return;
    }
    int m = (l + r) / 2;
    push(x);
    upd(x + x, l, m, tl, min(tr, m), val);
    upd(x + x + 1, m + 1, r, max(tl, m + 1), tr, val);
    t[x] = max(t[x + x], t[x + x + 1]);
}

vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
	int Q=X.size();
	vector<int> answer;
	int n = (int)A.size();
	vector<int> g;
	for(int i = 0; i < Q; i++){
        g.push_back(V[i]);
	}
	for(int i = 0; i < n; i++){
        g.push_back(A[i]);
	}
	map<int, int> m;
	sort(g.begin(), g.end());
    for(auto x : g){
        if(m.find(x) == m.end()){
            m[x] = ++G;
        }
    }
    for(int i = 0; i < n; i++){
        A[i] = m[A[i]];
        upd(1, 1, G, A[i], G, -1);
        upd(1, 1, G, A[i], i + 1);
	}
    for(int i = 0; i < Q; i++){
        V[i] = m[V[i]];
        upd(1, 1, G, A[X[i]], -(X[i] + 1));
        upd(1, 1, G, A[X[i]], G, 1);
        A[X[i]] = V[i];
        upd(1, 1, G, A[X[i]], (X[i] + 1));
        upd(1, 1, G, A[X[i]], G, -1);
        answer.push_back(t[1]);
    }
    return answer;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 188420 KB Output is correct
2 Correct 112 ms 188432 KB Output is correct
3 Correct 116 ms 188668 KB Output is correct
4 Correct 116 ms 188664 KB Output is correct
5 Correct 114 ms 188740 KB Output is correct
6 Correct 116 ms 188764 KB Output is correct
7 Correct 118 ms 188748 KB Output is correct
8 Correct 120 ms 188752 KB Output is correct
9 Correct 115 ms 188680 KB Output is correct
10 Correct 115 ms 188800 KB Output is correct
11 Correct 118 ms 188736 KB Output is correct
12 Correct 115 ms 188716 KB Output is correct
13 Correct 120 ms 188620 KB Output is correct
14 Correct 117 ms 188608 KB Output is correct
15 Correct 116 ms 188724 KB Output is correct
16 Correct 115 ms 188612 KB Output is correct
17 Correct 113 ms 188616 KB Output is correct
18 Correct 116 ms 188772 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 188420 KB Output is correct
2 Correct 112 ms 188432 KB Output is correct
3 Correct 116 ms 188668 KB Output is correct
4 Correct 116 ms 188664 KB Output is correct
5 Correct 114 ms 188740 KB Output is correct
6 Correct 116 ms 188764 KB Output is correct
7 Correct 118 ms 188748 KB Output is correct
8 Correct 120 ms 188752 KB Output is correct
9 Correct 115 ms 188680 KB Output is correct
10 Correct 115 ms 188800 KB Output is correct
11 Correct 118 ms 188736 KB Output is correct
12 Correct 115 ms 188716 KB Output is correct
13 Correct 120 ms 188620 KB Output is correct
14 Correct 117 ms 188608 KB Output is correct
15 Correct 116 ms 188724 KB Output is correct
16 Correct 115 ms 188612 KB Output is correct
17 Correct 113 ms 188616 KB Output is correct
18 Correct 116 ms 188772 KB Output is correct
19 Correct 133 ms 189976 KB Output is correct
20 Correct 137 ms 190184 KB Output is correct
21 Correct 135 ms 190276 KB Output is correct
22 Correct 144 ms 190324 KB Output is correct
23 Correct 137 ms 190148 KB Output is correct
24 Correct 137 ms 190044 KB Output is correct
25 Correct 133 ms 190020 KB Output is correct
26 Correct 135 ms 190096 KB Output is correct
27 Correct 135 ms 190020 KB Output is correct
28 Correct 130 ms 190020 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 190028 KB Output is correct
2 Correct 182 ms 191584 KB Output is correct
3 Correct 211 ms 193216 KB Output is correct
4 Correct 207 ms 193212 KB Output is correct
5 Correct 223 ms 193196 KB Output is correct
6 Correct 206 ms 193212 KB Output is correct
7 Correct 212 ms 193340 KB Output is correct
8 Correct 207 ms 193212 KB Output is correct
9 Correct 208 ms 193308 KB Output is correct
10 Correct 194 ms 193348 KB Output is correct
11 Correct 212 ms 193208 KB Output is correct
12 Correct 189 ms 193316 KB Output is correct
13 Correct 188 ms 193212 KB Output is correct
14 Correct 193 ms 193212 KB Output is correct
15 Correct 188 ms 193340 KB Output is correct
16 Correct 180 ms 193204 KB Output is correct
17 Correct 183 ms 193172 KB Output is correct
18 Correct 185 ms 193340 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 188420 KB Output is correct
2 Correct 112 ms 188432 KB Output is correct
3 Correct 116 ms 188668 KB Output is correct
4 Correct 116 ms 188664 KB Output is correct
5 Correct 114 ms 188740 KB Output is correct
6 Correct 116 ms 188764 KB Output is correct
7 Correct 118 ms 188748 KB Output is correct
8 Correct 120 ms 188752 KB Output is correct
9 Correct 115 ms 188680 KB Output is correct
10 Correct 115 ms 188800 KB Output is correct
11 Correct 118 ms 188736 KB Output is correct
12 Correct 115 ms 188716 KB Output is correct
13 Correct 120 ms 188620 KB Output is correct
14 Correct 117 ms 188608 KB Output is correct
15 Correct 116 ms 188724 KB Output is correct
16 Correct 115 ms 188612 KB Output is correct
17 Correct 113 ms 188616 KB Output is correct
18 Correct 116 ms 188772 KB Output is correct
19 Correct 133 ms 189976 KB Output is correct
20 Correct 137 ms 190184 KB Output is correct
21 Correct 135 ms 190276 KB Output is correct
22 Correct 144 ms 190324 KB Output is correct
23 Correct 137 ms 190148 KB Output is correct
24 Correct 137 ms 190044 KB Output is correct
25 Correct 133 ms 190020 KB Output is correct
26 Correct 135 ms 190096 KB Output is correct
27 Correct 135 ms 190020 KB Output is correct
28 Correct 130 ms 190020 KB Output is correct
29 Correct 134 ms 190028 KB Output is correct
30 Correct 182 ms 191584 KB Output is correct
31 Correct 211 ms 193216 KB Output is correct
32 Correct 207 ms 193212 KB Output is correct
33 Correct 223 ms 193196 KB Output is correct
34 Correct 206 ms 193212 KB Output is correct
35 Correct 212 ms 193340 KB Output is correct
36 Correct 207 ms 193212 KB Output is correct
37 Correct 208 ms 193308 KB Output is correct
38 Correct 194 ms 193348 KB Output is correct
39 Correct 212 ms 193208 KB Output is correct
40 Correct 189 ms 193316 KB Output is correct
41 Correct 188 ms 193212 KB Output is correct
42 Correct 193 ms 193212 KB Output is correct
43 Correct 188 ms 193340 KB Output is correct
44 Correct 180 ms 193204 KB Output is correct
45 Correct 183 ms 193172 KB Output is correct
46 Correct 185 ms 193340 KB Output is correct
47 Correct 1075 ms 230820 KB Output is correct
48 Correct 4025 ms 304308 KB Output is correct
49 Correct 4300 ms 313788 KB Output is correct
50 Correct 4280 ms 313804 KB Output is correct
51 Correct 4329 ms 313940 KB Output is correct
52 Correct 4315 ms 313828 KB Output is correct
53 Correct 4412 ms 313912 KB Output is correct
54 Correct 3866 ms 314020 KB Output is correct
55 Correct 4137 ms 314028 KB Output is correct
56 Correct 3787 ms 313916 KB Output is correct
57 Correct 4057 ms 314036 KB Output is correct
58 Correct 3792 ms 314096 KB Output is correct
59 Correct 3609 ms 306816 KB Output is correct
60 Correct 3728 ms 306708 KB Output is correct
61 Correct 3501 ms 306724 KB Output is correct
62 Correct 3395 ms 303620 KB Output is correct
63 Correct 3382 ms 303716 KB Output is correct
64 Correct 3471 ms 303612 KB Output is correct
65 Correct 3321 ms 300576 KB Output is correct
66 Correct 3344 ms 300708 KB Output is correct
67 Correct 3238 ms 300736 KB Output is correct