oj.uz

Submission #467705

# Submission time Handle Problem Language Result Execution time Memory
467705 2021-08-24T06:10:51 Z ETK Bubble Sort 2 (JOI18_bubblesort2) C++14
22 / 100
 251 ms 4536 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 b,int e,int v,int l,int r,int i){
		if(e<=l||r<=b)return;
		if(b<=l&&r<=e){
			lz[i]+=v;
			return;
		}
        pushdown(i);
		Add(b,e,v,l,(l+r)/2,i*2);
		Add(b,e,v,(l+r)/2,r,i*2+1);
		mx[i]=max(Q(i*2),Q(i*2+1));
	}
	void Add(int b,int e,int v){
		if(b<e)
			Add(b,e,v,0,s,1);
	}
};
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 50 ms 2120 KB Output is correct
2 Correct 138 ms 3792 KB Output is correct
3 Correct 242 ms 4500 KB Output is correct
4 Correct 228 ms 4496 KB Output is correct
5 Correct 226 ms 4500 KB Output is correct
6 Correct 216 ms 4500 KB Output is correct
7 Correct 251 ms 4408 KB Output is correct
8 Correct 229 ms 4436 KB Output is correct
9 Correct 245 ms 4536 KB Output is correct
10 Correct 173 ms 3412 KB Output is correct
11 Correct 185 ms 3400 KB Output is correct
12 Correct 189 ms 3396 KB Output is correct
13 Correct 180 ms 3384 KB Output is correct
14 Correct 187 ms 3428 KB Output is correct
15 Correct 194 ms 3412 KB Output is correct
16 Correct 175 ms 3384 KB Output is correct
17 Correct 176 ms 3384 KB Output is correct
18 Correct 180 ms 3396 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 -