Submission #1133396

#TimeUsernameProblemLanguageResultExecution timeMemory
1133396lopkusArranging Shoes (IOI19_shoes)C++20
100 / 100
107 ms25928 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; //#define int long long #define OYY LLONG_MAX #define mod 1000000007 #define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define FOR for(int i=1;i<=n;i++) #define mid (start+end)/2 #define lim 300005 #define fi first #define se second typedef long long lo; int n; lo cev; vector<int> poz[lim],neg[lim]; int pairr[lim],vis[lim],tree[4*lim]; inline int query(int node,int start,int end,int l,int r){ if(start>end || start>r || end<l)return 0; if(start>=l && end<=r)return tree[node]; return query(node*2,start,mid,l,r)+query(node*2+1,mid+1,end,l,r); } inline void update(int node,int start,int end,int l,int r,int val){ if(start>end || start>r || end<l)return ; if(start>=l && end<=r){ tree[node]+=val; return; } update(node*2,start,mid,l,r,val),update(node*2+1,mid+1,end,l,r,val); tree[node]=tree[node*2]+tree[node*2+1]; } long long count_swaps(vector<int> s) { n=s.size(); FOR{ if(s[i-1]<0)neg[-s[i-1]].push_back(i); else poz[s[i-1]].push_back(i); } FOR{ for(int j=0;j<(int)poz[i].size();j++){ pairr[poz[i][j]]=neg[i][j]; pairr[neg[i][j]]=poz[i][j]; } } FOR{ if(vis[i])continue; if(s[i-1]<0){ int sol=query(1,1,n,1,i)+i; int sag=query(1,1,n,1,pairr[i])+pairr[i]; cev+=(lo)abs(sag-sol-1); update(1,1,n,i,i,1); update(1,1,n,pairr[i]+1,pairr[i]+1,-1); vis[i]=vis[pairr[i]]=1; } else{ int sol=query(1,1,n,1,i)+i; int sag=query(1,1,n,1,pairr[i])+pairr[i]; cev+=(lo)abs(sag-sol); update(1,1,n,i,i,1); update(1,1,n,pairr[i]+1,pairr[i]+1,-1); vis[i]=vis[pairr[i]]=1; } } return cev; } /* int main(){ //faster int m;cin>>m; vector<int> vv; for(int i=1;i<=m;i++){ int x;cin>>x; vv.push_back(x); } cout<<count_swaps(vv)<<'\n'; 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...