Submission #815741

#TimeUsernameProblemLanguageResultExecution timeMemory
815741exodus_Ekoeko (COCI21_ekoeko)C++14
20 / 110
49 ms4728 KiB
#include<bits/stdc++.h> using namespace std; int freq[200]; const int maxn = 200001; vector<char>exclnt; deque<int>dex[200]; vector<int>ord; int segtree[4*maxn]={0}; void update(int idx, int low, int high, int val) { if(low==val && high==val) { segtree[idx]=1; return; } if(val<low || val>high) { return; } int mid = (low+high)/2; update(2*idx,low,mid,val); update(2*idx+1, mid+1,high,val); segtree[idx] = segtree[2*idx] + segtree[2*idx+1]; } int quer(int idx, int low, int high, int l, int r) { if(low>=l && high<=r) { return segtree[idx]; } if(low>r || high<l) return 0; int mid = (low+high)/2; return quer(2*idx,low,mid,l,r)+quer(2*idx+1,mid+1,high,l,r); } int main() { int n; string gab; cin >> n; cin >> gab; n = n*2; for(int i=0; i<n; i++) { int x = gab[i]-97; freq[x]++; } for(int i=0; i<n; i++) { int x = gab[i]-97; if(freq[x] > 0) { exclnt.push_back(gab[i]); freq[x]-=2; } } int ukex = exclnt.size(); for(int i=0; i<ukex; i++) { exclnt.push_back(exclnt[i]); } for(int i=0; i<n; i++) { int x = exclnt[i]-97; dex[x].push_back(i); } for(int i=0; i<n; i++) { int x = gab[i]-97; ord.push_back(dex[x].front()); dex[x].pop_front(); } int ans=0; for(int i=0; i<n; i++) { ans+=quer(1,1,n-1,ord[i],n-1); update(1,1,n-1,ord[i]); } cout << ans << endl; 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...