제출 #915102

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
915102		manizare	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	2464 ms	126840 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 ,  mod = 1e9 + 7 , inf =1e9  ;
vector <int> cm ;
set <int> s[maxn] ;
int seg[4*maxn] , lz[4*maxn]  , w[maxn] ;

void shi(int p , int l , int r){
    int mid =(l+r)/2 , pl =p<<1 , pr = p<<1|1;
    seg[pl] += lz[p] ;
    seg[pr] += lz[p] ;
    lz[pl] += lz[p] ;
    lz[pr] += lz[p] ;
    lz[p] = 0;
}
void upd(int le ,int ri , int w, int p =1 , int l = 0 , int r =sz(cm)-1){
    int mid = (l+r)/2 ,pl =p<<1 ,pr =p<<1|1 ;
    if(le > r || l > ri)return ;
    if(le <= l && r <= ri){
        seg[p] += w ;
        lz[p] += w; 
        return ;
    }
    if(l!=r)shi(p,l,r);
    upd(le,ri,w,pl,l,mid);
    upd(le,ri,w,pr,mid+1,r);
    seg[p] = max(seg[pl] , seg[pr]) ;
}

int val(int x){
    if(sz(s[x]) == 0)return -inf ;
    return (*s[x].rbegin()) ;
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
    int n = sz(A) , q = sz(X);
    rep(i , 0 , n-1){
        cm.pb(A[i]) ;
    }
    rep(i,0,sz(X)-1){
        cm.pb(V[i]);
    }
    sort(all(cm));
    cm.resize(unique(all(cm)) - cm.begin()) ;
    rep(i , 0, n-1){
        A[i] =lower_bound(all(cm) , A[i]) - cm.begin() ;
        s[A[i]].insert(i) ;
        upd(A[i] , sz(cm)-1 , -1);
    }
    rep(i , 0 , sz(V)-1){
        V[i] = lower_bound(all(cm) , V[i]) - cm.begin();
    }
    rep(i , 0 , sz(cm)-1){
        w[i] = val(i) ;
        upd(i , i , w[i]) ;
    }
    vector <int> res ;
    rep(i , 0 , q-1){
        int f=  A[X[i]]; 
        upd(f , f , -w[f]) ;
        upd(V[i] , V[i] , -w[V[i]]);
        upd(f , sz(cm)-1 , 1);
        s[f].erase(X[i]) ;
        s[V[i]].insert(X[i]) ;
        w[f] = val(f);
        w[V[i]] = val(V[i]) ;
        upd(V[i] , V[i] , w[V[i]]) ;
        upd(f ,  f , w[f]);
        A[X[i]] =V[i] ;
        upd(V[i] , sz(cm)-1 , -1) ;
        res.pb(seg[1]+1) ;
    }
    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;   
}

*/

컴파일 시 표준 에러 (stderr) 메시지

bubblesort2.cpp: In function 'void shi(int, int, int)':
bubblesort2.cpp:20:9: warning: unused variable 'mid' [-Wunused-variable]
   20 |     int mid =(l+r)/2 , pl =p<<1 , pr = p<<1|1;
      |         ^~~

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