oj.uz

Submission #421517

# Submission time Handle Problem Language Result Execution time Memory
421517 2021-06-09T08:38:20 Z 조영욱(#7654) Bubble Sort 2 (JOI18_bubblesort2) C++17
0 / 100
 9000 ms 116192 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;

const int sz=65536;
const int INF=1e9;
vector<int> pr;

struct SegmentTree {
    int seg[sz*2];
    int lazy[sz*2];
    void init() {
        for(int i=0;i<sz*2;i++) {
            seg[i]=-INF;
        }
    }
    void propagate(int node){
        if (lazy[node]!=0) {
            seg[node]+=lazy[node];
            if (node<sz) {
                lazy[node*2]+=lazy[node];
                lazy[node*2+1]+=lazy[node];
            }
            lazy[node]=0;
        }
    }
    int sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
        propagate(node);
        if (r<nodel||l>noder) {
            return -INF;
        }
        if (l<=nodel&&noder<=r) {
            return seg[node];
        }
        int mid=(nodel+noder)/2;
        return max(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,mid+1,noder));
    }
    void update(int l,int r,int val,int node=1,int nodel=0,int noder=sz-1) {
        propagate(node);
        if (r<nodel||l>noder) {
            return;
        }
        if (l<=nodel&&noder<=r) {
            lazy[node]+=val;
            propagate(node);
            return;
        }
        int mid=(nodel+noder)/2;
        update(l,r,val,node*2,nodel,mid);
        update(l,r,val,node*2+1,mid+1,noder);
        seg[node]=max(seg[node*2],seg[node*2+1]);
    }
};

SegmentTree st[101];

struct FenwickTree {
    int tree[sz];
    int sum(int i) {
        int ret=0;
        while (i>0){
            ret+=tree[i];
            i-=(i&-i);
        }
        return ret;
    }
    void update(int i,int val) {
        while (i<sz) {
            tree[i]+=val;
            i+=(i&-i);
        }
    }
};

FenwickTree ft[101];

vector<int> countScans(vector<int> A,vector<int> X,vector<int> V) {
    int n=A.size();
    int q=V.size();
    for(int i=0;i<=100;i++) {
        st[i].init();
    }
    for(int i=0;i<n;i++) {
        ft[A[i]].update(i+1,1);
    }
    for(int i=0;i<n;i++) {
        int sum=0;
        for(int j=A[i]+1;j<=100;j++) {
            sum+=ft[j].sum(i);
        }
        st[A[i]].update(i+1,i+1,-st[A[i]].sum(i+1,i+1)+sum);
    }
    vector<int> ret(q);
    for(int i=0;i<q;i++) {
        int pos=X[i]+1;
        for(int j=0;j<A[X[i]];j++) {
            st[j].update(pos+1,n,-1);
        }
        ft[A[X[i]]].update(pos,-1);
        st[A[X[i]]].update(pos,pos,-st[A[X[i]]].sum(pos,pos)-INF);
        A[X[i]]=V[i];
        for(int j=0;j<A[X[i]];j++) {
            st[j].update(pos+1,n,1);
        }
        ft[A[X[i]]].update(pos,1);
        int sum=0;
        for(int j=A[X[i]]+1;j<=100;j++) {
            sum+=ft[j].sum(X[i]);
        }
        //printf("%d\n",st[A[X[i]]].sum(pos,pos));
        st[A[X[i]]].update(pos,pos,-st[A[X[i]]].sum(pos,pos)+sum);
        //printf("%d %d\n",sum,st[A[X[i]]].sum(pos,pos));
        int val=0;
        for(int j=0;j<=100;j++) {
            val=max(val,st[j].sum(1,n));
        }
        ret[i]=val;
    }
    return ret;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 93 ms 106436 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 93 ms 106436 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 89056 KB Output is correct
2 Correct 5290 ms 103608 KB Output is correct
3 Execution timed out 9100 ms 116192 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 93 ms 106436 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -