oj.uz

Submission #1013275

# Submission time Handle Problem Language Result Execution time Memory
1013275 2024-07-03T11:12:14 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
22 / 100
 4821 ms 59504 KB 
#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
#define pb push_back
#define P pair
#define F first
#define S second

struct segtree{
private:
    struct node{
        vector<int>count;
    };
    static node make_neutral(){
        vector<int>A;
        A.assign(101,0);
        return{A};
    }
    static node single(int v){
        vector<int>A;
        A.assign(101,0);
        A[v]++;
        return{A};
    }
    static node merge(node &a,node &b){
        node c{};
        c.count.assign(101,0);
        for(int i=0;i<101;i++){
            c.count[i]=a.count[i]+b.count[i];
        }
        return c;
    }
public:
    int size;
    vector<node>query;
    void init(int n){
        size=1;
        while(size<n)size*=2;
        query.assign(2*size,make_neutral());
    }
    void set(int i,int v,int x,int lx,int rx){
        if(rx-lx==1){
            query[x]=single(v);
            return;
        }
        int m=(lx+rx)/2;
        if(i<m)
            set(i,v,2*x+1,lx,m);
        else
            set(i,v,2*x+2,m,rx);
        query[x]=merge(query[2*x+1],query[2*x+2]);
    }
    void set(int i,int v){
        set(i,v,0,0,size);
    }
    node calc(int l,int r,int x,int lx,int rx){
        if(lx>=r || rx<=l)
            return make_neutral();
        if(l<=lx && rx<=r)
            return query[x];
        int m=(lx+rx)/2;
        node a=calc(l,r,2*x+1,lx,m);
        node b=calc(l,r,2*x+2,m,rx);
        return merge(a,b);
    }
    vector<int>  calc(int l,int r){
        return calc(l,r,0,0,size).count;
    }
};
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
    int Q=X.size();
    std::vector<int> answer;
    int n=A.size();
    stack<P<int,int>> best[101];
    segtree tree;
    tree.init(n);
    for(int i=0;i<n;i++)
        tree.set(i,A[i]);
    for(int i=0;i<n;i++){
        vector<int>c=tree.calc(0,i+1);
        int calc=0;
        for(int j=A[i]+1;j<=100;j++){
            calc+=c[j];
        }
        best[A[i]].push({i,calc});
    }
    for(int i=0;i<Q;i++){
        int prev=A[X[i]];
        int nex=V[i];
        int ind=X[i];
        tree.set(ind,nex);
        A[ind]=nex;
        if(ind==best[prev].top().F){
            best[prev].pop();
            if(!best[prev].empty()){
                vector<int>c=tree.calc(0,best[prev].top().F+1);
                int calc=0;
                for(int j=prev+1;j<=100;j++){
                    calc+=c[j];
                }
                best[prev].top().S=calc;
            }
        }
        else{
            stack<P<int,int>>st;
            while(!best[prev].empty()){
                if(best[prev].top().F==ind){
                    best[prev].pop();
                    break;
                }
                else{
                    st.push(best[prev].top());
                    best[prev].pop();
                }
            }
            while(!st.empty()){
                best[prev].push(st.top());
                st.pop();
            }
        }
        if(best[nex].empty()){
            vector<int>c=tree.calc(0,ind+1);
            int calc=0;
            for(int j=nex+1;j<=100;j++){
                calc+=c[j];
            }
            best[nex].push({ind,calc});
        }
        else {
            vector<int> c = tree.calc(0, ind+1);
            int calc = 0;
            for (int j = nex + 1; j <= 100; j++) {
                calc += c[j];
            }
            stack<P<int,int>>st;
            while(true){
                if(best[nex].empty()){
                    best[nex].push({ind,calc});
                    break;
                }
                if(ind>=best[nex].top().F){
                    best[nex].push({ind,calc});
                    break;
                }
                st.push(best[nex].top());
                best[nex].pop();
            }
            while(!st.empty()){
                best[nex].push(st.top());
                st.pop();
            }
        }
        for(int j=1;j<=100;j++){
            if(!best[j].empty()) {
                if (best[j].top().F > ind) {
                    if (nex > A[best[j].top().F] && A[best[j].top().F] >= prev) {
                        best[j].top().S++;
                    }
                    if (nex <= A[best[j].top().F] && A[best[j].top().F] < prev) {
                        best[j].top().S--;
                    }
                }
            }
        }
        int max_d=0;
        for(int j=1;j<=100;j++){
            if(!best[j].empty()) {
                max_d = max(max_d, best[j].top().S);
            }
        }
        answer.pb(max_d);
    }
    return answer;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 2392 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 2 ms 2392 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 29060 KB Output is correct
2 Correct 424 ms 58372 KB Output is correct
3 Correct 713 ms 59392 KB Output is correct
4 Correct 737 ms 59348 KB Output is correct
5 Correct 792 ms 59356 KB Output is correct
6 Correct 748 ms 59356 KB Output is correct
7 Correct 800 ms 59392 KB Output is correct
8 Correct 829 ms 59476 KB Output is correct
9 Correct 874 ms 59316 KB Output is correct
10 Correct 4821 ms 59472 KB Output is correct
11 Correct 4794 ms 59452 KB Output is correct
12 Correct 4379 ms 59392 KB Output is correct
13 Correct 2468 ms 59448 KB Output is correct
14 Correct 2484 ms 59472 KB Output is correct
15 Correct 2480 ms 59424 KB Output is correct
16 Correct 580 ms 59504 KB Output is correct
17 Correct 580 ms 59376 KB Output is correct
18 Correct 603 ms 59476 KB Output is correct

Subtask #4
0 / 40.0

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