This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
cerr << h; if(sizeof...(t)) cerr << ", ";
DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL
#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"
using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;
void setIO(string NAME = "") {
cin.tie(0)->sync_with_stdio(0);
if(sz(NAME)) {
freopen((NAME + ".inp").c_str(),"r",stdin);
freopen((NAME + ".out").c_str(),"w",stdout);
}
}
tcT> bool ckmin(T&a, const T&b) {
return b < a ? a=b,1 : 0; }
tcT> bool ckmax(T&a, const T&b) {
return b > a ? a=b,1 : 0; }
struct BIT {
int N; vi bit;
void init(int _N) {
N = _N;
bit.assign(N + 7, 0);
}
void upd(int p, int val) {
for(; p<=N; p += p&-p) bit[p] += val;
}
int query(int r) {
int res = 0;
for(; r>0; r -= r&-r) res += bit[r];
return res;
}
} fen;
const int MOD = 1e9 + 7;
const int MX = 2e5+5;
int N, numNod, adj[2*MX][2], tin[2*MX], tout[2*MX], tt, val[2*MX];
ll ans = 0;
int inputTree() {
int u = ++numNod, cur;
cin >> cur;
if(!cur) {
adj[u][0] = inputTree();
tin[u] = tin[adj[u][0]];
adj[u][1] = inputTree();
}
else {
val[tin[u] = tt++] = cur;
}
tout[u] = tt;
return u;
}
void dfs(int u, bool toKeep) {
if(!adj[u][0]) {
if(toKeep) fen.upd(val[tin[u]], 1);
return;
}
int x = adj[u][0], y = adj[u][1];
if(tout[x] - tin[x] > tout[y] - tin[y])
swap(x, y);
dfs(x, 0); dfs(y, 1); ll cntInv = 0;
FOR(p, tin[x], tout[x]) {
cntInv += fen.query(val[p]-1);
}
ans += min(cntInv, 1LL*(tout[x] - tin[x])*(tout[y] - tin[y]) - cntInv);
if(toKeep) {
FOR(p, tin[x], tout[x]) fen.upd(val[p], 1);
}
else {
FOR(p, tin[y], tout[y]) fen.upd(val[p], -1);
}
}
void solve() {
cin >> N;
fen.init(N + 5);
inputTree();
dfs(1, 1);
cout << ans << nl;
}
int main() {
setIO();
int t=1;
//cin>>t;
while(t-->0) {
solve();
}
return 0;
}
Compilation message (stderr)
rot.cpp: In function 'void setIO(std::string)':
rot.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | freopen((NAME + ".inp").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
rot.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | freopen((NAME + ".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... |
# | 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... |