제출 #246218

#제출 시각아이디문제언어결과실행 시간메모리
246218EvirirArranging Shoes (IOI19_shoes)C++17
10 / 100
431 ms39672 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define watch(x) cout<<(#x)<<"="<<(x)<<'\n' #define mset(d,val) memset(d,val,sizeof(d)) #define setp(x) cout<<fixed<<setprecision(x) #define forn(i,a,b) for(int i=(a);i<(b);i++) #define fore(i,a,b) for(int i=(a);i<=(b);i++) #define pb push_back #define F first #define S second #define pqueue priority_queue #define fbo find_by_order #define ook order_of_key typedef long long ll; typedef pair<ll,ll> ii; typedef vector<ll> vi; typedef vector<ii> vii; typedef long double ld; typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds; void amin(ll &a, ll b){ a=min(a,b); } void amax(ll &a, ll b){ a=max(a,b); } void YES(){cout<<"YES\n";} void NO(){cout<<"NO\n";} void SD(int t=0){ cout<<"PASSED "<<t<<endl; } const ll INF = ll(1e18); const int MOD = 998244353; class PointSegmentTree{ private: int size_; vector<ll> v; void update(int p, ll val, int k, int l, int r) { if(p < l || r < p) return; if(l == r){ v[k]+=val; //modification return; } int mid = (l+r)>>1; update(p, val, k*2, l, mid); update(p, val, k*2+1, mid+1, r); v[k] = merge(v[k*2], v[k*2+1]); } ll query(int s, int e, int k, int l, int r) { if(e < l || r < s) return 0; //dummy value if(s <= l && r <= e) return v[k]; int mid = (l+r)>>1; ll lc = query(s, e, k*2, l, mid); ll rc = query(s, e, k*2+1, mid+1, r); return merge(lc, rc); } public: PointSegmentTree(): v(vector<ll>()) {} PointSegmentTree(int n){ for(size_=1;size_<n;) size_<<=1; v.resize(size_*4,1); } //void reset(){} inline ll merge(ll x, ll y){ return x+y; } inline void update(int p, ll val){ update(p, val, 1, 0, size_-1); } inline ll query(int l, int r){ return query(l, r, 1, 0, size_-1); } }; bool DEBUG = 0; const int MAXN = 100005; map<int,set<int>> loc; ll count_swaps(vector<int> a) { int n = a.size(); PointSegmentTree fw(n); forn(i,0,n){ loc[a[i]].insert(i); } ll ans = 0; forn(i,0,n) { if(DEBUG) SD(i); if(fw.query(i,i)==0){ if(DEBUG) cout<<"continued"<<endl; continue; } if(a[i]>0) ans++; int nxt = *loc[-a[i]].begin(); ans += fw.query(i+1,nxt-1); fw.update(i,-1); fw.update(nxt,-1); loc[a[i]].erase(loc[a[i]].begin()); loc[-a[i]].erase(loc[-a[i]].begin()); if(DEBUG) cout<<"ans="<<ans<<endl; } 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...