oj.uz

Submission #467704

# Submission time Handle Problem Language Result Execution time Memory
467704 2021-08-24T06:08:57 Z ETK Bubble Sort 2 (JOI18_bubblesort2) C++14
22 / 100
 243 ms 4512 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int inf=INT_MAX/2;
struct SegTree{
    int s;
    vi mx,lz;
    SegTree(int n){
        s=1;
        while(s<n)s*=2;
        mx.resize(2*s,0),lz.resize(2*s,0);
    }
    #define ls (p<<1)
    #define rs (p<<1|1)
    void pushdown(int p){
        mx[p]+=lz[p],lz[ls]+=lz[p],lz[rs]+=lz[p];
        lz[p]=0;
    }
    int Q(int p){return mx[p]+lz[p];}
    void Add(int p,int L,int R,int l,int r,int v){
        if(r<=L||R<=l)return;
        if(l<=L&&R<=r){
            lz[p]+=v;
            return;
        }
        pushdown(p);
        int mid=(L+R)>>1;
        Add(ls,L,mid,l,r,v);
        Add(rs,mid,R,l,r,v);
        mx[p]=max(Q(ls),Q(rs));
    }
    void Add(int l,int r,int v){
        if(l<r)Add(1,0,s,l,r,v);
    }
};
vi countScans(vi a,vi x,vi v){
    int n=a.size(),q=x.size();
    vector<pii> lsh;
    rep(i,0,n-1)lsh.pb(pii(a[i],i));
    rep(i,0,n-1)lsh.pb(pii(v[i],x[i]));
    sort(ALL(lsh));
    lsh.erase(unique(ALL(lsh)),lsh.end());
    int s=lsh.size();
    SegTree seg(s);
    seg.Add(0,s,-inf);
    const auto insert = [&](int p,int r){
        int i=lower_bound(ALL(lsh),pii(p,r))-lsh.begin();
        seg.Add(i,i+1,inf+r);
        seg.Add(i+1,s,-1);
    };
    const auto erase = [&](int p,int r){
        int i=lower_bound(ALL(lsh),pii(p,r))-lsh.begin();
        seg.Add(i,i+1,-(inf+r));
        seg.Add(i+1,s,1);
    };
    rep(i,0,n-1)insert(a[i],i);
    vi res(q);
    rep(i,0,q-1){
        erase(a[x[i]],x[i]);
        insert(v[i],x[i]);
        a[x[i]]=v[i];res[i]=seg.Q(1);
    }
    return res;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 2132 KB Output is correct
2 Correct 138 ms 3784 KB Output is correct
3 Correct 243 ms 4436 KB Output is correct
4 Correct 237 ms 4500 KB Output is correct
5 Correct 225 ms 4416 KB Output is correct
6 Correct 216 ms 4504 KB Output is correct
7 Correct 226 ms 4496 KB Output is correct
8 Correct 220 ms 4452 KB Output is correct
9 Correct 234 ms 4512 KB Output is correct
10 Correct 175 ms 3492 KB Output is correct
11 Correct 187 ms 3408 KB Output is correct
12 Correct 190 ms 3404 KB Output is correct
13 Correct 211 ms 3384 KB Output is correct
14 Correct 184 ms 3408 KB Output is correct
15 Correct 193 ms 3384 KB Output is correct
16 Correct 162 ms 3336 KB Output is correct
17 Correct 180 ms 3448 KB Output is correct
18 Correct 178 ms 3404 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -