Submission #1208329

#TimeUsernameProblemLanguageResultExecution timeMemory
1208329al95ireyizArranging Shoes (IOI19_shoes)C++20
100 / 100
434 ms147776 KiB
//*** Bismillah ***// #pragma GCC optimize("O3", "fast-math", "unroll-loops", "no-stack-protector") #include <bits/stdc++.h> using namespace std; #if !defined(ONLINE_JUDGE) and !defined(EVAL) #include "template/debug.h" #else #define d(x...) #endif #define fr first #define er erase #define sc second #define in insert #define ll long long #define pb push_back #define vll vector<ll> #define pll pair<ll,ll> #define ull unsigned ll #define vpll vector<pll> #define len(x)(ll)x.size() #define all(x)x.begin(),x.end() const ll INF = 1e9; const ll INFL = 1e18; const ll MOD = 1e9+7; // const ll MOD = 998244353; const ll maxn = 2e5+5; ll n,m,k=0; #include "shoes.h" ll fw[maxn]; bool vis[maxn]; void upd(ll i, ll val){ for(i ++; i < maxn; i += i & -i) fw[i] += val; } ll get(ll i){ ll cv = 0; for(i ++; i > 0; i -= i & -i) cv += fw[i]; return cv; } ll count_swaps(vector<int>v){ n = len(v); map<ll, queue<ll>>mp; for(ll i = 0; i < n; i ++) mp[v[i]].push(i); ll cv = 0; memset(fw, 0, sizeof(fw)); memset(vis, 0, sizeof(vis)); for(ll i = 0; i < n; i ++){ if(vis[i]) continue; ll qar = mp[-v[i]].front(); mp[v[i]].pop(), mp[-v[i]].pop(); vis[i] = vis[qar] = 1; cv += (get(qar) + qar) - (get(i) + i) - 1; if(v[i] > 0) cv ++; upd(i, 1), upd(qar, -1); } return cv; } // void _(ll tt){ // } // signed main(){ // ll tm=clock(); // cin.tie(0)->sync_with_stdio(0); // ll t=1; // // cin>>t; // for(ll tt=1;tt<=t;tt++){ // _(tt); // } // cerr<<"\n\033[1;31mTime: \033[1;30m" \ // <<(double)(clock()-tm)/1000000<<"\033[1;32m seconds\n"; // }
#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...