이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using lli = long long;
using pii = pair<int,int>;
int n;
struct seg_tr{
int tr[200001];
void init() {
for(int i=0;i<=n;i++) tr[i] = 0;
}
void upd(int cur, int val) {
while(cur<=n) tr[cur]+=val, cur+=cur&-cur;
}
int get(int cur) {
int ret=0;
while(cur) ret+=tr[cur], cur-=cur&-cur;
return ret;
}
}seg;
long long count_swaps(vector<int> s) {
set<pii> vi, iv;
n = s.size();
seg.init();
for(int i=0;i<s.size();i++) {
vi.insert({s[i], i});
iv.insert({i, s[i]});
seg.upd(i+1, 1);
}
lli ans = 0;
int n=s.size() / 2;
for(int i=0;i<n;i++) {
auto st = iv.begin();
auto mat = vi.lower_bound({-st->se, 0});
ans += seg.get(mat->se);
if(st->se < 0) ans--;
seg.upd(st->fi+1, -1);
seg.upd(mat->se+1, -1);
iv.erase({mat->se, -st->se});
vi.erase(mat);
vi.erase({st->se, st->fi});
iv.erase(st);
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:27:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<s.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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |