oj.uz

Submission #210777

# Submission time Handle Problem Language Result Execution time Memory
210777 2020-03-18T10:45:19 Z eric_xiao Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
 30 ms 1524 KB 
#include "bubblesort2.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int N,Q,sz;
int ST[4000009],tag[4000009];
void push(int p,int l,int r)
{
    if(r == l+1) return;
    tag[p*2] += tag[p];
    tag[p*2+1] += tag[p];
    ST[p*2] += tag[p];
    ST[p*2] += tag[p];
    tag[p] = 0;
    return;
}
void Build(int p,int l,int r)
{
    ST[p] = 0;
    if(r == l + 1) return;
    int mid = (l + r)/2;
    Build(p*2,l,mid);
    Build(p*2+1,mid,r);
}
void Modify(int p,int l,int r,int ql,int qr,int k)
{
    if(l >= ql && r <= qr)
    {
        tag[p] += k;
        ST[p] += k;
        return;
    }
    if(l >= qr || r <= ql) return;
    push(p,l,r);
    int mid = (l + r)/2;
    Modify(p*2,l,mid,ql,qr,k);
    Modify(p*2+1,mid,r,ql,qr,k);
    ST[p*2] = max(ST[p],ST[p*2]);
}
void chg(int p,int l,int r,int w,int k)
{
    if(r == l + 1 && l == w)
    {
        ST[p] = k;
        return;
    }
    push(p,l,r);
    int mid = (l + r)/2;
    if(w < mid)
    {
        chg(p*2,l,mid,w,k);
    }
    else
    {
        chg(p*2+1,mid,r,w,k);
    }
    ST[p] = max(ST[p*2],ST[p*2+1]);
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V)
{
    int i;
    vector<int> ans;
    N = A.size();
    Q = X.size();
    vector<ll> v;
    for(i = 0;i < N;i++) v.push_back((ll)A[i]*(ll)1000000007 + (ll)i);
    for(i = 0;i < Q;i++) v.push_back((ll)V[i]*(ll)1000000007 + (ll)i);
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    sz = v.size() + 5;
    for(i = 0;i < N;i++)
    {
        A[i] = lower_bound(v.begin(),v.end(),(ll)A[i]*(ll)1000000007 + (ll)i) - v.begin() + 1;
    }
    for(i = 0;i < Q;i++)
    {
        V[i] = lower_bound(v.begin(),v.end(),(ll)V[i]*(ll)1000000007 + (ll)i) - v.begin() + 1;
    }
    Build(1,0,sz);
    for(i = 0;i < N;i++)
    {
        Modify(1,0,sz,A[i],A[i]+1,i);
    }
    for(i = 0;i < N;i++)
    {
        Modify(1,0,sz,A[i]+1,sz,-1);
    }
    for(i = 0;i < Q;i++)
    {
        int x = X[i],v = V[i];
        Modify(1,0,sz,A[x]+1,sz,1);
        Modify(1,0,sz,v+1,sz,-1);
        Modify(1,0,sz,A[x],A[x]+1,-x);
        Modify(1,0,sz,v,v+1,x);
        A[x] = v;
        //cout << ST[1] << endl;
        ans.push_back(ST[1]);
    }
    return ans;
}

Subtask #1
0 / 17.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

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