이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define endl '\n'
#define v1 v
using namespace std;
const int N = 200010;
vector <int> c[26];
vector <pair <int, int>> v;
struct Segtree{
int tree[4*N];
Segtree(){
for(int i = 0;i < 4*N;i++) tree[i] = 0;
}
int join(int a, int b){
return a+b;
}
void update(int node, int l, int r, int pos, int val){
if(l == r){
tree[node] += val;
return;
}
int mid= (l+r)/2;
if(l <= pos and pos <= mid) update(2*node, l, mid, pos, val);
else update(2*node+1, mid+1, r, pos, val);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
int query(int node, int l, int r, int tl, int tr){
if(l > tr or tl > r) return 0;
if(l <= tl and tr <= r) return tree[node];
int mid = (tl+tr)/2;
return join(query(2*node, l, r, tl , mid), query(2*node+1, l, r, mid+1, tr));
}
}seg;
int main(){
int n;
cin >> n;
string s;
cin >> s;
for(int i = 0;i < 2*n;i++){
c[s[i] - 'a'].push_back(i);
}
for(int i = 0;i < 26;i++){
int t = c[i].size();
t /= 2;
for(int j = t;j < c[i].size();i++){
v.push_back({c[i][j-t], c[i][j]-n});
}
}
sort(v.begin(), v.end());
for(auto &x : v){
x.first++;
x.second++;
}
int at = 1;
int res = 0;
for(auto &x : v){
if(x.first > at){
res += x.first-at;
x.first = at;
}
at++;
}
for(auto &x : v)
swap(x.first, x.second);
sort(v.begin(), v.end());
for(auto &x : v)
swap(x.first, x.second);
for(auto x : v){
res += seg.query(1, x.first, n, 1, n);
seg.update(1, 1, n, x.first, 1);
}
cout << res << endl;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'int main()':
Main.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int j = t;j < c[i].size();i++){
| ~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |