Submission #1238814

#TimeUsernameProblemLanguageResultExecution timeMemory
1238814ayathkArranging Shoes (IOI19_shoes)C++20
10 / 100
0 ms328 KiB
#include <bits/stdc++.h> #include "shoes.h" using namespace std; #define pb push_back #define ll long long const ll inf=1e9+4; const ll off=(1<<19); ll tr[off*2]; ll op(ll trl,ll trr){ return trl+trr; } void upd(ll i,ll v){ i+=off; tr[i]=v; while (i/=2){ ll xl=i*2,xr=xl+1; tr[i]=op(tr[xl],tr[xr]); } } ll query(ll ql,ll qr,ll l=0,ll r=off-1,ll x=1){ if (ql<=l && r<=qr)return tr[x]; if (l>qr || r<ql)return 0; ll mid=(l+r)/2; ll xl=x*2,xr=xl+1; ll trl=query(ql,qr,l,mid,xl),trr=query(ql,qr,mid+1,r,xr); return op(trl,trr); } ll count_swaps(vector<int>a){ ll n=a.size(); ll us[n]; for (int i=0;i<n;i++){ upd(i,1); us[i]=1; } queue<ll>adp[n+1]; queue<ll>adn[n+1]; vector<ll>p(n); //cout<<"DSFI"; for (int i=0;i<n;i++){ if (a[i]>0){ if (adn[abs(a[i])].size()){ p[i]=(adn[abs(a[i])].front()); p[adn[abs(a[i])].front()]=(i); adn[abs(a[i])].pop(); }else{ adp[a[i]].push(i); } } else{ //cout<<'d'; if (adp[abs(a[i])].size()){ p[i]=(adp[abs(a[i])].front()); p[adp[abs(a[i])].front()]=(i); adp[abs(a[i])].pop(); }else{ //cout<<i<<endl; adn[abs(a[i])].push(i); } } } // for (int i=0;i<n;i++){ // cout<<p[i]<<" "; // }cout<<endl; ll sum=0; for (int i=n-1;i>=0;i--){ if (!us[i])continue; // for (auto x:us){ // cout<<x<<" "; // }cout<<endl; ll r=i-1,l=p[i]+1; //cout<<l<<" "<<r<<endl; if (l<r){ ll x=query(l,r); sum+=x; //cout<<x<<endl; } upd(i,0); upd(p[i],0); us[i]=0,us[p[i]]=0; if (a[i]<0)sum++; //cout<<sum<<" "; } return sum; } // int main() { // int n; // assert(1 == scanf("%d", &n)); // vector<int> S(2 * n); // for (int i = 0; i < 2 * n; i++) // assert(1 == scanf("%d", &S[i])); // fclose(stdin); // long long result = count_swaps(S); // printf("%lld\n", result); // fclose(stdout); // return 0; // }
#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...