제출 #852221

#제출 시각아이디문제언어결과실행 시간메모리
852221LucaIlieBubble Sort 2 (JOI18_bubblesort2)C++17
0 / 100
33 ms68176 KiB
#include "bubblesort2.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; const int MAX_N = 5e5; const int MAX_AINT = 2 * MAX_N; const int INF = 1e9; struct AINT { struct info { int minn, maxx; info operator + ( info x ) { return { min( minn, x.minn ), max( maxx, x.maxx ) }; } }; info aint[4 * MAX_AINT]; set<int> poses[MAX_AINT + 1]; void update( int v, int l, int r, int pos, int val ) { if ( l > pos || r < pos ) return; if ( l == r ) { if ( val >= 0 ) poses[l].insert( val ); else poses[l].erase( -(val - 1) ); aint[v] = (poses[l].empty() ? info{ INF, -INF } : info{ *poses[l].begin(), *poses[l].rbegin() } ); return; } int mid = (l + r) / 2; update( v * 2 + 1, l, mid, pos, val ); update( v * 2 + 2, mid + 1, r, pos, val ); aint[v] = aint[v * 2 + 1] + aint[v * 2 + 2]; } info query( int v, int l, int r, int lq, int rq ) { if ( lq > rq ) return { INF, -INF }; if ( l > rq || r < lq ) return { INF, -INF }; if ( lq <= l && r <= rq ) return aint[v]; int mid = (l + r) / 2; info a = query( v * 2 + 1, l, mid, lq, rq ); info b = query( v * 2 + 2, mid + 1, r, lq, rq ); return a + b; } } aint; struct per { int i, j; bool operator < ( const per &x ) const { return abs( i - j ) > abs( x.i - x.j ); } }; int leftPair[MAX_N + 1], rightPair[MAX_N + 1]; vector<int> pairs[MAX_N + 1]; map<int, int> mp; set<per> cand; vector<int> countScans( vector<int> v, vector<int> pos, vector<int> val ){ int n = v.size(); int q = pos.size(); vector<int> ans( q ); for ( int i = 0; i < n; i++ ) mp[v[i]] = 1; for ( int i = 0; i < q; i++ ) mp[val[i]] = 1; int valmax = 0; for ( auto x: mp ) mp[x.first] = ++valmax; for ( int i = 0; i < n; i++ ) v[i] = mp[v[i]]; for ( int i = 0; i < q; i++ ) val[i] = mp[val[i]]; for ( int i = 0; i < n; i++ ) { aint.update( 0, 1, valmax, v[i], i ); int pl = aint.query( 0, 1, valmax, v[i] + 1, valmax ).minn; leftPair[i] = -1; if ( 0 <= pl && pl < i ) { leftPair[i] = pl; pairs[leftPair[i]].push_back( i ); cand.insert( { leftPair[i], i } ); } int pr = aint.query( 0, 1, valmax, 1, v[i] - 1 ).maxx; rightPair[i] = -1; if ( i < pr && pr < n ) { rightPair[i] = pr; pairs[rightPair[i]].push_back( i ); cand.insert( { i, rightPair[i] } ); } } for ( int l = 0; l < q; l++ ) { int i = pos[l]; for ( int j: pairs[i] ) cand.erase( { min( i, j ), max( i, j ) } ); if ( leftPair[i] != -1 ) cand.erase( { leftPair[i], i } ); if ( rightPair[i] != -1 ) cand.erase( { i, rightPair[i] } ); aint.update( 0, 1, valmax, v[i], -(i + 1) ); v[i] = val[l]; aint.update( 0, 1, valmax, v[i], i ); int pl = aint.query( 0, 1, valmax, v[i] + 1, valmax ).minn; leftPair[i] = -1; if ( 0 <= pl && pl < i ) { leftPair[i] = pl; pairs[leftPair[i]].push_back( i ); cand.insert( { leftPair[i], i } ); } int pr = aint.query( 0, 1, valmax, 1, v[i] - 1 ).maxx; rightPair[i] = -1; if ( i < pr && pr < n ) { rightPair[i] = pr; pairs[rightPair[i]].push_back( i ); cand.insert( { i, rightPair[i] } ); } ans[l] = (cand.empty() ? 0 : cand.begin()->j - cand.begin()->i); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...