Submission #1003797

#TimeUsernameProblemLanguageResultExecution timeMemory
1003797vjudge1Ekoeko (COCI21_ekoeko)C++17
20 / 110
31 ms16224 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define pb push_back const int maxn = 2e5+5; int bit[maxn]; void upd(int x){ for(; x<maxn; x+=x&-x) bit[x]++; } int query(int x){ int rt=0; for(; x>0; x-=x&-x) rt+=bit[x]; return rt; } int ord(char c){ return (int)(c-'a'); } signed main(){ int n; cin >> n; string s; cin >> s; vector<int> mp(26,0), cnt(26,0); for(char c : s) cnt[ord(c)]++; int cnt1=0, cnt2=0; vector<int> arr1, arr2; vector<int> trans(2*n); set<int> pos[26]; for(int i=0; i<2*n; i++){ int p = ord(s[i]); if(mp[p]<cnt[p]/2){ mp[p]++; cnt1++; trans[i]=cnt1; pos[p].insert(i+1); } } for(int i=0; i<2*n; i++) if(!trans[i]){ int p = ord(s[i]); assert(pos[p].size()>0); trans[i] = (*pos[p].begin())+n; pos[p].erase(pos[p].begin()); } // for(int x : trans) cout << x << " "; // cout << endl; int ans=0; for(int i=0; i<2*n; i++ ){ ans += i-query(trans[i]-1); upd(trans[i]); } cout << ans << '\n'; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:29:14: warning: unused variable 'cnt2' [-Wunused-variable]
   29 |  int cnt1=0, cnt2=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...