제출 #1323322

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1323322		StefanSebez	Bubble Sort Machine (JOI25_bubble)	C++20	100 / 100	1923 ms	999916 KiB

bubble

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#pragma GCC optimize("Ofast,unroll-loops")
const int N=5e5+50,inf=1e9,lg=20;
int n,q,a[N];
struct Wavelet{
    int root,nc,lc[N*lg],rc[N*lg];
    vector<int>a[N*lg];
    vector<ll>prefL[N*lg],pref[N*lg];
    void Build(int &c,int ss,int se,vector<int>A,vector<int>A1){
        if(A.empty()||ss>se)return;
        c=++nc;
        //printf("%i: %i %i\n",c,ss,se);
        a[c].resize(A.size()+1);
        prefL[c].resize(A.size()+1);
        pref[c].resize(A.size()+1);
        int mid=ss+se>>1;
        vector<int>B,B1,C,C1;
        for(int i=0;i<A.size();i++){
            a[c][i+1]=a[c][i];
            prefL[c][i+1]=prefL[c][i];
            pref[c][i+1]=pref[c][i]+A1[i];
            if(A[i]<=mid){
                B.pb(A[i]);
                B1.pb(A1[i]);
                a[c][i+1]++;
                prefL[c][i+1]+=A1[i];
            }
            else{
                C.pb(A[i]);
                C1.pb(A1[i]);
            }
        }
        if(ss==se)return;
        Build(lc[c],ss,mid,B,B1);
        Build(rc[c],mid+1,se,C,C1);
    }
    ll Get(int c,int ss,int se,int l,int r,int k){
        if(!c||l>r||k==0)return 0;
        if(ss==se)return pref[c][l+k]-pref[c][l];
        int mid=ss+se>>1;
        if(a[c][r+1]-a[c][l]>=k)return Get(lc[c],ss,mid,a[c][l],a[c][r+1]-1,k);
        return Get(rc[c],mid+1,se,l-a[c][l],r-a[c][r+1],k-(a[c][r+1]-a[c][l]))+prefL[c][r+1]-prefL[c][l];
    }
}ST;
int M,K;
ll Calc(int l){
    int k=min(K,n-l);
    return ST.Get(ST.root,0,M,0,l+k-1,l);
}
int main(){
    scanf("%i",&n);
    for(int i=1;i<=n;i++)scanf("%i",&a[i]);
    vector<int>A,vals;
    for(int i=1;i<=n;i++)A.pb(a[i]),vals.pb(a[i]);
    sort(vals.begin(),vals.end());
    vals.resize(unique(vals.begin(),vals.end())-vals.begin());
    vector<int>A1;
    for(auto i:A)A1.pb(lower_bound(vals.begin(),vals.end(),i)-vals.begin());
    M=vals.size()-1;
    ST.Build(ST.root,0,M,A1,A);
    scanf("%i",&q);
    while(q--){
        int type;scanf("%i",&type);
        if(type==1)K++;
        else{
            int l,r;scanf("%i%i",&l,&r);
            ll res=Calc(r)-Calc(l-1);
            printf("%lld\n",res);
        }
    }
    return 0;
}

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

bubble.cpp: In function 'int main()':
bubble.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
bubble.cpp:57:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     for(int i=1;i<=n;i++)scanf("%i",&a[i]);
      |                          ~~~~~^~~~~~~~~~~~
bubble.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     scanf("%i",&q);
      |     ~~~~~^~~~~~~~~
bubble.cpp:68:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         int type;scanf("%i",&type);
      |                  ~~~~~^~~~~~~~~~~~
bubble.cpp:71:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |             int l,r;scanf("%i%i",&l,&r);
      |                     ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 29 / 29
• Subtask 6: 17 / 17