Submission #158966

# Submission time Handle Problem Language Result Execution time Memory
158966 2019-10-19T17:02:42 Z janchomath Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
9000 ms 74420 KB
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
#define N 500005
using namespace std;
ll n,m,pown=1,a[N],b[N],c[N],t[10*N],save[10*N],l,r,ad;
vector<ll>v;
map<ll,ll>mp;
set<ll>st[3 * N];
void updd(ll x){
    if(!x)return;
    t[x] = max(t[2 * x] , t[2 * x + 1]);
    updd(x / 2);
}
void upd(ll x,ll L,ll R){
    if(L > r || R < l)return;
    if(L >= l && R <= r){
        save[x] += ad;
        t[x] += ad;
        return;
    }
    if(save[x]){
        save[2 * x] += save[x];
        save[2 * x + 1] += save[x];
        t[2 * x] += save[x];
        t[2 * x + 1] += save[x];
        save[x] = 0;
    }
    upd(2 * x, L , (L + R) / 2);
    upd(2 * x + 1 , (L + R) / 2 + 1, R);
    t[x] = max(t[2 * x] , t[2 * x + 1]);
}
vector<int> countScans(vector<int>ff ,vector<int>uu,vector<int>vv){
    n = ff.size();
    m = uu.size();
    for(int i=1; i<=n; i++)
        a[i] = ff[i - 1],
        v.pb(a[i]);
    for(int i=1; i<=n; i++){
        b[i] = uu[i - 1] + 1;
        c[i] = vv[i - 1];
        v.pb(c[i]);
    }
    
    sort(v.begin() , v.end());
    ll p = 0;
    for(int i=0; i<v.size(); i++){
        if(!i || v[i] != v[i - 1])p++;
        mp[v[i]] = p;
    }
    
    for(int i=1; i<=n; i++){
        a[i] = mp[a[i]];
        st[a[i]].insert(-i);
    }
    for(int i=1; i<=m; i++)
        c[i] = mp[c[i]];
    
    while(pown <= n + m)
        pown *= 2;
    for(int i=1; i<=n; i++){
        t[pown + i - 1] = -(*st[a[i]].begin());
        save[pown + i - 1] = -(*st[a[i]].begin());
        l = a[i],r = n + m;
        ad = -1;
        upd(1 , 1 , pown);
        updd((pown + i - 1) / 2);
    }
    vector<int>ans;
    
    for(int q=1; q<=m; q++){
        ll x,y;
        x = b[q];
        y = c[q];
        l = a[x],r = a[x];
        ad = (*st[a[x]].begin());
        st[a[x]].erase(st[a[x]].find(-x));
        if(st[a[x]].size())ad -= (*st[a[x]].begin());
        upd(1 , 1 , pown);
        ad = 1;
        l = a[x],r = n + m;
        upd(1 , 1 , pown);
        a[x] = y;
        l = a[x],r = a[x];
        ad = (*st[a[x]].begin());
        st[a[x]].insert(-x);
        ad -= (*st[a[x]].begin());
        upd(1 , 1 , pown);
        ad = -1;
        l = a[x] , r = n + m;
        upd(1 , 1 , pown);
        ans.pb(t[1]);
        //cout << t[1] << " ";
    }
    return ans;
}
/*
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    vector<ll>aa,xx,yy;
    for(int i=1; i<=n; i++){
        ll x;
        cin >> x;
        aa.pb(x);
    }
    for(int i=1; i<=m; i++){
        ll x,y;
        cin >> x >> y;
        xx.pb(x);
        yy.pb(y);
    }
    
    countScans(aa , xx , yy);
    
    
    return 0;
}
*/

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:49:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<v.size(); i++){
                  ~^~~~~~~~~
# Verdict Execution time Memory Grader output
1 Execution timed out 9090 ms 71160 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 9090 ms 71160 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 74420 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 9090 ms 71160 KB Time limit exceeded
2 Halted 0 ms 0 KB -