제출 #215928

#제출 시각아이디문제언어결과실행 시간메모리
215928balbitBubble Sort 2 (JOI18_bubblesort2)C++14
38 / 100
83 ms95992 KiB
#include "bubblesort2.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define int ll #define SZ(x) (int)(x.size()) #define ALL(x) x.begin(),x.end() #define pb push_back #define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end())))) #ifdef BALBIT #define bug(...) cerr<<"#"<<__LINE__<<" "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__) template<typename T> void _do(T && x){cerr<<x<<endl;} template<typename T, typename ...S> void _do(T && x, S&&...y){cerr<<x<<", "; _do(y...);} #define IOS() #else #define bug(...) #define IOS() ios::sync_with_stdio(0),cin.tie(0) #define endl '\n' #endif // BALBIT const int maxn = 2e6+5; multiset <int> pos[maxn]; int tag[maxn*4], s[maxn*4]; void push(int o, int l, int r){ if (!tag[o]) return; s[o]+=tag[o]; if (l!=r){ tag[o*2+1]+=tag[o]; tag[o*2+2]+=tag[o]; } tag[o]=0; } int MX; void MO(int L, int R, int v, int o=0, int l=0, int r=MX-1){ push(o,l,r); if (l>R||r<L) return; if (l>=L&&r<=R) { tag[o]+=v; push(o,l,r); return; } int mid = (l+r)/2; MO(L,R,v, o*2+1,l,mid); MO(L,R,v, o*2+2,mid+1,r); s[o]=min(s[o*2+1],s[o*2+2]); } inline int big(multiset<int> & ms) { return SZ(ms)?-*(ms.rbegin()):0; } vector<signed> countScans(vector<signed> A,vector<signed> X,vector<signed> V){ int Q=X.size(); vector<signed> answer(Q); int n = SZ(A); vector<signed> tmp = A; for (int x : V) tmp.pb(x); SORT_UNIQUE(tmp); MX = SZ(tmp); for (int i = 0; i<n; ++i) { A[i] = lower_bound(ALL(tmp), A[i]) - tmp.begin(); pos[A[i]].insert(i); MO(A[i]+1, MX-1,1); } for (int i = 0; i<Q; ++i) { V[i] = lower_bound(ALL(tmp), V[i]) - tmp.begin(); } for (int i = 0; i<n; ++i) { if (big(pos[A[i]]) == -i) { MO(A[i],A[i],-i); } } bug(s[0]); for (int cnt = 0; cnt<Q; ++cnt) { int i = X[cnt]; MO(A[i]+1, MX-1, -1); MO(A[i], A[i],-big(pos[A[i]])); bug(A[i], i); pos[A[i]].erase(pos[A[i]].find(i)); MO(A[i],A[i], big(pos[A[i]])); A[i] = V[cnt]; bug("insert",A[i],i); MO(A[i]+1, MX-1, 1); MO(A[i],A[i], -big(pos[A[i]])); pos[A[i]].insert(i); MO(A[i], A[i],big(pos[A[i]])); answer[cnt] = max(-s[0],0ll); } return answer; } #ifdef BALBIT signed main(){ IOS(); vector<int> mo = (countScans({1,2,3,4},{0,2},{3,1})); for (int x : mo) bug(x); } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...