oj.uz

답안 #221549

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
221549 2020-04-10T13:30:39 Z balbit Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
 9000 ms 47736 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define SZ(x) (int)(x.size())
#define ALL(x) x.begin(),x.end()
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<" "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y){cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define endl '\n'
#endif // BALBIT

const int maxn = 1e6+5;

multiset <int> pos[maxn];

int tag[maxn*4], s[maxn*4];

void push(int o, int l, int r){
    if (!tag[o]) return;
    s[o]+=tag[o];
    if (l!=r){
        tag[o*2+1]+=tag[o];
        tag[o*2+2]+=tag[o];
    }
    tag[o]=0;
}

int MX;

void MO(int L, int R, int v, int o=0, int l=0, int r=MX-1){
    push(o,l,r);
    if (l>R||r<L) return;
    if (l>=L&&r<=R) {
        tag[o]+=v; push(o,l,r); return;
    }
    int mid = (l+r)/2;
    MO(L,R,v, o*2+1,l,mid);
    MO(L,R,v, o*2+2,mid+1,r);
    s[o]=min(s[o*2+1],s[o*2+2]);
}

inline int big(multiset<int> & ms) {
    return SZ(ms)?-*(ms.begin()):1000000000;
}

vector<signed> stupid(vector<signed> A,vector<signed> X, vector<signed> V) {
    int Q = X.size();
    vector<signed> re(Q,-1);
    for (int i = 0; i<Q; ++i) {
        A[X[i]] = V[i];
        bool sp = 1;
        vector<signed> a = A;
        while (sp) {
            sp=0;
            ++re[i];
            for (int j = 0; j<SZ(a)-1; ++j) {
                if (a[j] > a[j+1]) {
                    swap(a[j], a[j+1]); sp=1;
                }
            }
        }
    }
    return re;
}

vector<signed> countScans(vector<signed> A,vector<signed> X,vector<signed> V){
	int Q=X.size();
	vector<signed> answer(Q);
	vector<signed> stp = stupid(A,X,V);
	int n = SZ(A);
	vector<signed> tmp = A;
	for (int x : V) tmp.pb(x);
	SORT_UNIQUE(tmp);
	MX = SZ(tmp);

	for (int i = 0; i<n; ++i) {
        A[i] = lower_bound(ALL(tmp), A[i]) - tmp.begin();
        pos[A[i]].insert(i);
        MO(A[i]+1, MX-1,1);
	}
	for (int i = 0; i<Q; ++i) {
        V[i] = lower_bound(ALL(tmp), V[i]) - tmp.begin();
	}
    vector<int> done(MX);
    for (int i = 0; i<n; ++i) {
        if (big(pos[A[i]]) == -i) {
            done[A[i]] = 1;
            MO(A[i],A[i],-i);
        }
    }
    for (int i = 0; i<MX; ++i) {
        if (!done[i]) MO(i,i,1000000000);
    }
    bug(s[0]);
    for (int cnt = 0; cnt<Q; ++cnt) {
        int i = X[cnt];
        MO(A[i]+1, MX-1, -1);
        MO(A[i], A[i],-big(pos[A[i]]));
        bug(A[i], i);
        pos[A[i]].erase(pos[A[i]].find(i));
        MO(A[i],A[i], big(pos[A[i]]));

        A[i] = V[cnt];
        bug("insert",A[i],i);
        MO(A[i]+1, MX-1, 1);
        MO(A[i],A[i], -big(pos[A[i]]));
        pos[A[i]].insert(i);
        MO(A[i], A[i],big(pos[A[i]]));


        answer[cnt] = max(-s[0],0ll);

    }
    for (int i = 0; i<SZ(stp); ++i) {
        if (answer[i] < stp[i]) {
            assert(0);
        }
        if (answer[i] > stp[i]) {
            while (1);
        }
    }
	return answer;
}


#ifdef BALBIT
signed main(){
    IOS();
    vector<signed> mo = (countScans({1,2,3,4},{2,0,2},{5,3,1}));
    for (int x : mo) bug(x);
}
#endif

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 309 ms 47480 KB Output is correct
2 Correct 1037 ms 47480 KB Output is correct
3 Execution timed out 9074 ms 47352 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 309 ms 47480 KB Output is correct
2 Correct 1037 ms 47480 KB Output is correct
3 Execution timed out 9074 ms 47352 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 9054 ms 47736 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 309 ms 47480 KB Output is correct
2 Correct 1037 ms 47480 KB Output is correct
3 Execution timed out 9074 ms 47352 KB Time limit exceeded
4 Halted 0 ms 0 KB -