oj.uz

Submission #597546

# Submission time Handle Problem Language Result Execution time Memory
597546 2022-07-16T09:50:04 Z urosk Bubble Sort 2 (JOI18_bubblesort2) C++14
100 / 100
 4162 ms 225592 KB 
#include "bubblesort2.h"
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
using namespace __gnu_pbds;

typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define maxn 2000005
ll n,q;
pll a[maxn];
ll b[maxn];
ll x[maxn];
ll v[maxn];
ll t[4*maxn];
ll lazy[4*maxn];
void push(ll v,ll tl,ll tr){
    t[v]+=lazy[v];
    if(tl<tr){
        lazy[2*v]+=lazy[v];
        lazy[2*v+1]+=lazy[v];
    }
    lazy[v] = 0;
}
void upd(ll v,ll tl,ll tr,ll l,ll r,ll x){
    push(v,tl,tr);
    if(l>r) return;
    if(tl==l&&tr==r){
        lazy[v]+=x;
        push(v,tl,tr);
        return;
    }
    ll mid = (tl+tr)/2;
    upd(2*v,tl,mid,l,min(mid,r),x);
    upd(2*v+1,mid+1,tr,max(mid+1,l),r,x);
    t[v] = max(t[2*v],t[2*v+1]);
}
ll get(ll v,ll tl,ll tr,ll l,ll r){
    push(v,tl,tr);
    if(l>r) return 0;
    if(tl==l&&tr==r) return t[v];
    ll mid = (tl+tr)/2;
    return max(get(2*v,tl,mid,l,min(mid,r)),get(2*v+1,mid+1,tr,max(mid+1,l),r));
}
void init(ll v,ll tl,ll tr){
    if(tl==tr){
        t[v] = b[tl];
        return;
    }
    ll mid = (tl+tr)/2;
    init(2*v,tl,mid);
    init(2*v+1,mid+1,tr);
    t[v] = max(t[2*v],t[2*v+1]);
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
	n = sz(A);
	q = sz(X);
	set<pll> s;
	map<pll,ll> mp;
    for(ll i = 1;i<=n;i++) a[i] = {A[i-1],i};
    for(ll i = 1;i<=q;i++) x[i] = X[i-1]+1;
    for(ll i = 1;i<=q;i++) v[i] = V[i-1];
    for(ll i = 1;i<=n;i++) s.insert(a[i]);
    for(ll i = 1;i<=q;i++) s.insert({v[i],x[i]});
    ll it = 1;
    ll m = it-1;
    ll mx = maxn-5;
    for(pll p : s) mp[p] = it++;
    for(ll i = 1;i<=n;i++) a[i].fi = mp[a[i]];
    for(ll i = 1;i<=n;i++) b[a[i].fi] = i;
    for(ll i = 1;i<=q;i++) v[i] = mp[{v[i],x[i]}];
    init(1,1,mx);
    for(ll i = 1;i<=n;i++) upd(1,1,mx,a[i].fi+1,mx,-1);
    vector<int> ans;
    for(ll j = 1;j<=q;j++){
        ll i = x[j];
        ll val = v[j];
        ll z = a[i].fi;
        upd(1,1,mx,z+1,mx,1);
        upd(1,1,mx,z,z,-i);
        upd(1,1,mx,val,val,i);
        upd(1,1,mx,val+1,mx,-1);
        ans.pb(t[1]-1);
        a[i].fi = val;
    }
    return ans;
}
/*
4 2
1 2 3 4
0 3
2 1
*/

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:82:8: warning: unused variable 'm' [-Wunused-variable]
   82 |     ll m = it-1;
      |        ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 33364 KB Output is correct
2 Correct 25 ms 33484 KB Output is correct
3 Correct 28 ms 33916 KB Output is correct
4 Correct 29 ms 34000 KB Output is correct
5 Correct 29 ms 33988 KB Output is correct
6 Correct 28 ms 33996 KB Output is correct
7 Correct 38 ms 34020 KB Output is correct
8 Correct 36 ms 33940 KB Output is correct
9 Correct 40 ms 34028 KB Output is correct
10 Correct 29 ms 33856 KB Output is correct
11 Correct 29 ms 33876 KB Output is correct
12 Correct 31 ms 34052 KB Output is correct
13 Correct 29 ms 33916 KB Output is correct
14 Correct 31 ms 33852 KB Output is correct
15 Correct 29 ms 33876 KB Output is correct
16 Correct 29 ms 33868 KB Output is correct
17 Correct 30 ms 33876 KB Output is correct
18 Correct 30 ms 33844 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 33364 KB Output is correct
2 Correct 25 ms 33484 KB Output is correct
3 Correct 28 ms 33916 KB Output is correct
4 Correct 29 ms 34000 KB Output is correct
5 Correct 29 ms 33988 KB Output is correct
6 Correct 28 ms 33996 KB Output is correct
7 Correct 38 ms 34020 KB Output is correct
8 Correct 36 ms 33940 KB Output is correct
9 Correct 40 ms 34028 KB Output is correct
10 Correct 29 ms 33856 KB Output is correct
11 Correct 29 ms 33876 KB Output is correct
12 Correct 31 ms 34052 KB Output is correct
13 Correct 29 ms 33916 KB Output is correct
14 Correct 31 ms 33852 KB Output is correct
15 Correct 29 ms 33876 KB Output is correct
16 Correct 29 ms 33868 KB Output is correct
17 Correct 30 ms 33876 KB Output is correct
18 Correct 30 ms 33844 KB Output is correct
19 Correct 49 ms 35956 KB Output is correct
20 Correct 48 ms 36328 KB Output is correct
21 Correct 47 ms 36264 KB Output is correct
22 Correct 49 ms 36336 KB Output is correct
23 Correct 47 ms 36016 KB Output is correct
24 Correct 46 ms 36032 KB Output is correct
25 Correct 45 ms 35784 KB Output is correct
26 Correct 53 ms 35788 KB Output is correct
27 Correct 60 ms 35632 KB Output is correct
28 Correct 57 ms 35656 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 38480 KB Output is correct
2 Correct 128 ms 45028 KB Output is correct
3 Correct 313 ms 51804 KB Output is correct
4 Correct 211 ms 51712 KB Output is correct
5 Correct 225 ms 51572 KB Output is correct
6 Correct 241 ms 51428 KB Output is correct
7 Correct 222 ms 51408 KB Output is correct
8 Correct 216 ms 51408 KB Output is correct
9 Correct 220 ms 51468 KB Output is correct
10 Correct 162 ms 45156 KB Output is correct
11 Correct 173 ms 45120 KB Output is correct
12 Correct 167 ms 45172 KB Output is correct
13 Correct 160 ms 45160 KB Output is correct
14 Correct 198 ms 45176 KB Output is correct
15 Correct 168 ms 45140 KB Output is correct
16 Correct 147 ms 45116 KB Output is correct
17 Correct 148 ms 45120 KB Output is correct
18 Correct 160 ms 45156 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 33364 KB Output is correct
2 Correct 25 ms 33484 KB Output is correct
3 Correct 28 ms 33916 KB Output is correct
4 Correct 29 ms 34000 KB Output is correct
5 Correct 29 ms 33988 KB Output is correct
6 Correct 28 ms 33996 KB Output is correct
7 Correct 38 ms 34020 KB Output is correct
8 Correct 36 ms 33940 KB Output is correct
9 Correct 40 ms 34028 KB Output is correct
10 Correct 29 ms 33856 KB Output is correct
11 Correct 29 ms 33876 KB Output is correct
12 Correct 31 ms 34052 KB Output is correct
13 Correct 29 ms 33916 KB Output is correct
14 Correct 31 ms 33852 KB Output is correct
15 Correct 29 ms 33876 KB Output is correct
16 Correct 29 ms 33868 KB Output is correct
17 Correct 30 ms 33876 KB Output is correct
18 Correct 30 ms 33844 KB Output is correct
19 Correct 49 ms 35956 KB Output is correct
20 Correct 48 ms 36328 KB Output is correct
21 Correct 47 ms 36264 KB Output is correct
22 Correct 49 ms 36336 KB Output is correct
23 Correct 47 ms 36016 KB Output is correct
24 Correct 46 ms 36032 KB Output is correct
25 Correct 45 ms 35784 KB Output is correct
26 Correct 53 ms 35788 KB Output is correct
27 Correct 60 ms 35632 KB Output is correct
28 Correct 57 ms 35656 KB Output is correct
29 Correct 57 ms 38480 KB Output is correct
30 Correct 128 ms 45028 KB Output is correct
31 Correct 313 ms 51804 KB Output is correct
32 Correct 211 ms 51712 KB Output is correct
33 Correct 225 ms 51572 KB Output is correct
34 Correct 241 ms 51428 KB Output is correct
35 Correct 222 ms 51408 KB Output is correct
36 Correct 216 ms 51408 KB Output is correct
37 Correct 220 ms 51468 KB Output is correct
38 Correct 162 ms 45156 KB Output is correct
39 Correct 173 ms 45120 KB Output is correct
40 Correct 167 ms 45172 KB Output is correct
41 Correct 160 ms 45160 KB Output is correct
42 Correct 198 ms 45176 KB Output is correct
43 Correct 168 ms 45140 KB Output is correct
44 Correct 147 ms 45116 KB Output is correct
45 Correct 148 ms 45120 KB Output is correct
46 Correct 160 ms 45156 KB Output is correct
47 Correct 949 ms 90628 KB Output is correct
48 Correct 3651 ms 208808 KB Output is correct
49 Correct 4127 ms 225168 KB Output is correct
50 Correct 4123 ms 225140 KB Output is correct
51 Correct 4162 ms 225204 KB Output is correct
52 Correct 4128 ms 225140 KB Output is correct
53 Correct 3984 ms 225184 KB Output is correct
54 Correct 3472 ms 225592 KB Output is correct
55 Correct 4048 ms 225484 KB Output is correct
56 Correct 3598 ms 225432 KB Output is correct
57 Correct 3806 ms 225336 KB Output is correct
58 Correct 3585 ms 225308 KB Output is correct
59 Correct 3325 ms 205332 KB Output is correct
60 Correct 3630 ms 205384 KB Output is correct
61 Correct 3593 ms 205388 KB Output is correct
62 Correct 3411 ms 196000 KB Output is correct
63 Correct 3298 ms 195896 KB Output is correct
64 Correct 3341 ms 195844 KB Output is correct
65 Correct 3289 ms 186468 KB Output is correct
66 Correct 3237 ms 186464 KB Output is correct
67 Correct 3242 ms 186456 KB Output is correct