oj.uz

답안 #884107

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
884107 2023-12-06T15:56:14 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
0 / 100
 9000 ms 23720 KB 
#include<bits/stdc++.h>
#include <bubblesort2.h>
using namespace std;
const int N = 5e5 + 10;
const int M = 110;
vector <int> a;
vector <int> v2;
vector <int> x;
class fenwick{
    int fen[N];
    int n;
public:
    void init(int sz){
        n = sz;
        for(int i = 0;i < n;i++)fen[i] = 0;
    }
    void add(int pos){
        for(int i = pos;i >= 0;i&=(i + 1),i--){
            fen[i]++;
        }
    }
    int get(int pos){
        int r = 0;
        for(int i = pos;i < n;i|=(i + 1)){
            r+=fen[i];
        }
        return r;
    }
};
int fen2[N][M];
int n,q;
void add(int x,int y,int nr){
    //cout<<"add:"<<x<<' '<<y<<' '<<nr<<'\n';
    for(int i = x;i < n;i|=(i + 1)){
        for(int j = y;j >= 0;j&=(j + 1),j--){
            fen2[i][j]+=nr;
        }
    }
}
int get(int x,int y){
    //cout<<"get:"<<x<<' '<<y<<' ';
    int r = 0;
    for(int i = x;i >= 0;i&=(i + 1),i--){
        for(int j = y;j < M;j|=(j + 1)){
            r+=fen2[i][j];
        }
    }
    //cout<<r<<'\n';
    return r;
}
set <int> last[M];
int p[N];
fenwick fen;
int cnt = 0;
vector <int> countScans(vector <int> v,vector <int> q1,vector <int> q2){
    n = v.size();
    q = q1.size();
    bool ok = 0;
    for(int i = 0;i < q;i++){
        q2[i]--;
    }
    for(int i = 0;i < n;i++){
        v[i]--;
        if(v[i] >= 100)ok = 1;
        last[v[i]].insert(i);
    }
    vector<int>ans;
    if(ok || n >= 50000){
        for(int i = 0;i < q;i++){
            v[q1[i]] = q2[i];
            fen.init(n);
            int ans2 = 0;
            for(int i = 0;i < n;i++){
                ans2 = max(ans2,fen.get(v[i]));
                fen.add(v[i]);
            }
            ans.push_back(ans2);
            //cout<<ans2<<' ';
        }
    }else{
        for(int i = 0;i < n;i++){
            add(i,v[i],1);
        }
        for(int i = 0;i < q;i++){
            add(q1[i],v[q1[i]],-1);
            last[v[q1[i]]].erase(q1[i]);
            v[q1[i]] = q2[i];
            last[v[q1[i]]].insert(q1[i]);
            add(q1[i],v[q1[i]],1);
            int ans2 = 0;
            /*for(int j = 0;j < n;j++){
                ans2 = max(ans2,get(j - 1,v[j] + 1));
            }*/
            for(int j = 0;j < M;j++){
                if(!last[j].empty()){
                    int x = *last[j].rbegin();
                    ans2 = max(ans2,get(x - 1,v[x] + 1));
                }
            }
            ans.push_back(ans2);
            //cout<<ans2<<'\n';
        }
    }
    return ans;
}
/*
int main(){
    int n,q;
    cin>>n>>q;
    for(int i = 0;i < n;i++){
        int b;
        cin>>b;
        a.push_back(b);
    }
    for(int i=  0;i < q;i++){
        int b,c;
        cin>>b>>c;
        v2.push_back(c);
        x.push_back(b);
    }
    countScans(a,x,v2);
    return 0;
}
*/
/**
4 2
1 2 3 4
0 3
2 1
**/

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 4700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 4700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 16220 KB Output is correct
2 Correct 121 ms 23720 KB Output is correct
3 Execution timed out 9052 ms 8264 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 4700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -