oj.uz

Submission #30128

# Submission time Handle Problem Language Result Execution time Memory
30128 2017-07-22T07:38:25 Z 김현수(#1247) Tree Rotations (POI11_rot) C++14
100 / 100
 459 ms 38348 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 400005;

ll n, a[N], s[N], e[N], l[N], r[N], cc, bc, ans;
bool vis[N];

vector<ll> st;

struct segtree {
	ll v[4*N], lim;
	void init () {
		for(lim=1;lim<=n;lim<<=1);
	}
	void upd (ll P, ll V) {
		P += lim;
		while(P) {v[P] += V; P>>=1;}
	}
	ll get (ll S, ll E) {
		S += lim; E += lim;
		ll ret = 0;
		while(S <= E) {
			if(S%2 == 1) ret += v[S++];
			if(E%2 == 0) ret += v[E--];
			S>>=1; E>>=1;
		}
		return ret;
	}
} seg;

void calc (ll I) {
	s[I] = cc+1;
	ll T;
	scanf("%lld",&T);
	if(T) a[++cc] = T;
	else {
		l[I] = ++bc; calc(bc);
		r[I] = ++bc; calc(bc);
	}
	e[I] = cc;
}

ll len (ll I) {return e[I] - s[I] + 1;}

void solve (ll I) {
	if(vis[I]) return;
	vis[I] = true;
	if(s[I] == e[I]) {
		seg.upd(a[s[I]], 1);
		st.push_back(a[s[I]]);
		return;
	}
	ll A = (len(l[I]) >= len(r[I]) ? l[I] : r[I]);
	ll B = l[I] + r[I] - A;
	solve(A);
	ll T = 0;
	for(ll i=s[B];i<=e[B];i++) {
		T += seg.get(0, a[i]-1);
	}
	ans += min(T, len(A)*len(B)-T);
	for(ll i=s[B];i<=e[B];i++) {
		seg.upd(a[i], 1);
		st.push_back(a[i]);
	}
}

int main()
{
	scanf("%lld",&n);
	calc(++bc);
	seg.init();
	for(ll i=1;i<=bc;i++) {
		solve(i);
		for(auto &T : st) seg.upd(T, -1);
		st.clear();
	}
	printf("%lld\n",ans);
}

Compilation message

rot.cpp: In function 'void calc(ll)':
rot.cpp:35:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&T);
                  ^
rot.cpp: In function 'int main()':
rot.cpp:70:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
                  ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 30536 KB Output is correct
2 Correct 0 ms 30536 KB Output is correct
3 Correct 0 ms 30536 KB Output is correct
4 Correct 0 ms 30536 KB Output is correct
5 Correct 0 ms 30536 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 30536 KB Output is correct
2 Correct 0 ms 30536 KB Output is correct
3 Correct 0 ms 30536 KB Output is correct
4 Correct 0 ms 30536 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 30536 KB Output is correct
2 Correct 0 ms 30536 KB Output is correct
3 Correct 0 ms 30536 KB Output is correct
4 Correct 0 ms 30536 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 30692 KB Output is correct
2 Correct 3 ms 30676 KB Output is correct
3 Correct 0 ms 30692 KB Output is correct
4 Correct 3 ms 30728 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31200 KB Output is correct
2 Correct 9 ms 30808 KB Output is correct
3 Correct 36 ms 31004 KB Output is correct
4 Correct 9 ms 31032 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 31388 KB Output is correct
2 Correct 29 ms 31944 KB Output is correct
3 Correct 39 ms 32844 KB Output is correct
4 Correct 43 ms 32720 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 35744 KB Output is correct
2 Correct 63 ms 34104 KB Output is correct
3 Correct 83 ms 33048 KB Output is correct
4 Correct 69 ms 32284 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 32156 KB Output is correct
2 Correct 96 ms 33020 KB Output is correct
3 Correct 83 ms 34896 KB Output is correct
4 Correct 83 ms 34252 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 34856 KB Output is correct
2 Correct 166 ms 34580 KB Output is correct
3 Correct 159 ms 34484 KB Output is correct
4 Correct 179 ms 34360 KB Output is correct
5 Correct 319 ms 33692 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 34132 KB Output is correct
2 Correct 186 ms 36668 KB Output is correct
3 Correct 199 ms 36440 KB Output is correct
4 Correct 166 ms 38348 KB Output is correct
5 Correct 426 ms 33692 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 34156 KB Output is correct
2 Correct 176 ms 34764 KB Output is correct
3 Correct 299 ms 33692 KB Output is correct
4 Correct 263 ms 33960 KB Output is correct
5 Correct 149 ms 38252 KB Output is correct
6 Correct 459 ms 33692 KB Output is correct