oj.uz

Submission #467698

# Submission time Handle Problem Language Result Execution time Memory
467698 2021-08-24T05:59:55 Z ETK Bubble Sort 2 (JOI18_bubblesort2) C++14
22 / 100
 226 ms 5140 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,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 3 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 3 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 39 ms 2132 KB Output is correct
2 Correct 116 ms 3700 KB Output is correct
3 Correct 205 ms 5072 KB Output is correct
4 Correct 220 ms 5076 KB Output is correct
5 Correct 193 ms 5140 KB Output is correct
6 Correct 198 ms 5016 KB Output is correct
7 Correct 195 ms 5080 KB Output is correct
8 Correct 226 ms 5088 KB Output is correct
9 Correct 216 ms 5012 KB Output is correct
10 Correct 149 ms 4024 KB Output is correct
11 Correct 172 ms 4152 KB Output is correct
12 Correct 174 ms 4024 KB Output is correct
13 Correct 218 ms 4152 KB Output is correct
14 Correct 169 ms 4052 KB Output is correct
15 Correct 165 ms 4024 KB Output is correct
16 Correct 165 ms 4044 KB Output is correct
17 Correct 170 ms 4048 KB Output is correct
18 Correct 172 ms 4040 KB Output is correct

Subtask #4
0 / 40.0

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