oj.uz

Submission #467697

# Submission time Handle Problem Language Result Execution time Memory
467697 2021-08-24T05:59:17 Z ETK Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
 113 ms 4164 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;
int s;
vi mx,lz;
void init(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+1,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();
    init(s);
    Add(0,s,-inf);
    const auto insert = [&](int p,int r){
        int i=lower_bound(ALL(lsh),pii(p,r))-lsh.begin();
        Add(i,i+1,inf+r);Add(i+1,s,-1);
    };
    const auto erase = [&](int p,int r){
        int i=lower_bound(ALL(lsh),pii(p,r))-lsh.begin();
        Add(i,i+1,-(inf+r));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]=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
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 2232 KB Output is correct
2 Incorrect 113 ms 4164 KB Output isn't correct
3 Halted 0 ms 0 KB -

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 -