Submission #141307

#	Time	Username	Problem	Language	Result	Execution time	Memory
141307		ngot23	Bubble Sort 2 (JOI18_bubblesort2)	C++11	0 / 100	6 ms	632 KiB

bubblesort2

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i=(a) ; i<=(b) ; ++i)
#define mp make_pair
#define pii pair<int, int>
#define PB push_back
#define F first
#define S second
#define Task ""
using namespace std;
template <typename T > inline void MIN(T &a, T b) { if(a>b) a=b; }
template <typename T > inline void MAX(T &a, T b) { if(a<b) a=b; }
const int N=8005;
vector <int > A, X, V;
int n, Q, sz, t[N*2];
vector <pii > rr;

int get(int x) {
    int ret=0;
    while(x<N*2) {
        ret+=t[x];
        x+=x&(-x);
    }
    return ret;
}

void update(int x) {
    while(x>0) {
        ++t[x];
        x-=x&(-x);
    }
}


vector <int > countScans(vector <int > A, vector <int > X, vector <int > V) {
    for(int i=0 ; i<n ; ++i) rr.PB(mp(A[i], i));
    for(int i=0 ; i<Q ; ++i) rr.PB(mp(V[i], X[i]));
    sort(rr.begin(), rr.end());
    rr.resize(unique(rr.begin(), rr.end())-rr.begin());

    vector <int > ret;
    for(int j=0 ; j<Q ; ++j) {
        for(int i=0 ; i<N*2 ; ++i) t[i]=0;
        A[X[j]]=V[j];
        int mx=0;
        for(int i=0 ; i<n ; ++i) {
            int xx=lower_bound(rr.begin(), rr.end(), mp(A[i], i))-rr.begin()+1;
            MAX(mx, get(xx+1));
            update(xx);
        }
        ret.PB(mx);
    }
    return ret;
}
vector <int > ans;
#ifdef FUCK
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(Task".inp", "r", stdin);
    //freopen(Task".out", "w", stdout);
    cin >> n >> Q;
    A.resize(n); X.resize(Q); V.resize(Q);
    for(int i=0 ; i<n ; ++i) cin >> A[i];
    for(int i=0 ; i<Q ; ++i) cin >> X[i] >> V[i];
    ans=countScans(A, X, V);
    for(int e:ans) cout << e << '\n';
    return 0;
}
#endif // FUCK

• Subtask 1: 0 / 17
• Subtask 2: 0 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40