Submission #915070

#	Time	Username	Problem	Language	Result	Execution time	Memory
915070		manizare	Bubble Sort 2 (JOI18_bubblesort2)	C++14	22 / 100	69 ms	95580 KiB

bubblesort2

#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
using namespace std ;   
const int maxn = 1e6 + 10 , inf= 2e9 , mod = 1e9 + 7 , sq = 360 ,MX = 20000 ;
set <int> s[maxn] ;
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
    int n = sz(A) , q = sz(X);
    rep(i , 0 , n-1){
        s[A[i]].insert(i);
    }
    vector <int> res ;
    rep(i , 0 , q-1){
        s[A[X[i]]].erase(X[i]) ;
        A[X[i]] = V[i] ;
        s[A[X[i]]].insert(X[i]) ;
        int ans = 0 , ted =0 ;
        rep(i , 1, 100){
            ted += sz(s[i]) ;
            if(sz(s[i])){
                ans = max(ans , (*s[i].rbegin()) - ted + 1) ;
            }
        }
        res.pb(ans) ;
    }
    return res; 
}
/*
signed main(){
    ios::sync_with_stdio(0);cin.tie(0); 
    int n , q ;
    cin >> n >> q;
    vector <int> a ;
    rep(i , 1, n){
        int x;
        cin >> x ;
        a.pb(x);
    }
    vector <int> X , V ;
    rep(i , 1, q){
        int x, v;
        cin >>x>> v ;
        X.pb(x);V.pb(v);
    }
    vector <int> ans = countScans(a,X,V) ;
    for(int x : ans){
        cout << x << "\n" ;
    }
    return 0;   
}

*/

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