이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
/* /\_/\
(= ._.)
/ > \>
*/
//#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") // codeforces
// #define int long long
#define fi first
#define se second
#define pb push_back
#define ins insert
#define mp make_pair
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(0);}
#define endl '\n'
#define sz(x) ((long long) (x).size())
#define all(x) (x).begin(),(x).end()
#define print(x) cout<<(x)<<" ";
#define printl(x) cout<<(x)<<endl
#define dbg(x) cerr<<#x<<" "<<x<<endl
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
void fileIO(string filename) {
freopen((filename + ".in").c_str(), "r", stdin);
freopen((filename + ".out").c_str(), "w", stdout);
}
// const ll mod = 1000000007;
// const ll mod = 998244353;
// ll mod;
const int inf=1e9,MAXN=2e5+5;
const ll INF=1e18;
const ld pi = 3.14159265358979323846;
struct BIT {
int n; vi S;
void update(int pos,int add) {
for(pos;pos<=n;pos+=pos&-pos) S[pos]+=add;
}
int sum(int pos) {
int ret=0;
for(pos;pos>0;pos-=pos&-pos) ret += S[pos];
return ret;
}
int query(int l,int r) {
if(r < l) return 0;
return sum(r) - sum(l-1);
}
BIT(vi v) {
n = v.size();
S = vi(n+1,0);
for(int i=0;i<n;i++) update(i+1,v[i]);
}
};
long long count_swaps(std::vector<int> S) {
int n = S.size();
BIT bit(vi(n+1,0));
queue<int> pos[2][n+1];
bool marked[n+1] = {0};
for(int i=0;i<n;i++) {
if(S[i] < 0) pos[0][-S[i]].push(i+1);
else pos[1][S[i]].push(i+1);
}
ll ans = 0;
for(int i=0;i<n;i++) {
if(marked[i+1]) continue;
if(S[i] > 0) {
int x = pos[0][S[i]].front();
pos[0][S[i]].pop();
ans += x - i - 1 - bit.query(i+1,x);
//dbg(ans);
bit.update(x,1);
marked[x] = 1;
pos[1][S[i]].pop();
}else {
int x = pos[1][-S[i]].front(); pos[1][-S[i]].pop();
ans += x - i - 2 - bit.query(i+1,x);
bit.update(x,1);
marked[x] = 1;
pos[0][-S[i]].pop();
}
}
return ans;
}
/*int main() {
print(count_swaps({-1,2,1,-2,3,-3}));
}*/
컴파일 시 표준 에러 (stderr) 메시지
shoes.cpp: In member function 'void BIT::update(int, int)':
shoes.cpp:54:13: warning: statement has no effect [-Wunused-value]
54 | for(pos;pos<=n;pos+=pos&-pos) S[pos]+=add;
| ^~~
shoes.cpp: In member function 'int BIT::sum(int)':
shoes.cpp:59:13: warning: statement has no effect [-Wunused-value]
59 | for(pos;pos>0;pos-=pos&-pos) ret += S[pos];
| ^~~
shoes.cpp: In function 'void fileIO(std::string)':
shoes.cpp:38:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | freopen((filename + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
shoes.cpp:39:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
39 | freopen((filename + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |