oj.uz

Submission #30129

# Submission time Handle Problem Language Result Execution time Memory
30129 2017-07-22T07:39:33 Z khsoo01 Tree Rotations (POI11_rot) C++11
100 / 100
 406 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 3 ms 30696 KB Output is correct
2 Correct 3 ms 30676 KB Output is correct
3 Correct 3 ms 30696 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 3 ms 31196 KB Output is correct
2 Correct 6 ms 30808 KB Output is correct
3 Correct 39 ms 31004 KB Output is correct
4 Correct 3 ms 31032 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 31388 KB Output is correct
2 Correct 43 ms 31948 KB Output is correct
3 Correct 46 ms 32844 KB Output is correct
4 Correct 56 ms 32720 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 35748 KB Output is correct
2 Correct 69 ms 34108 KB Output is correct
3 Correct 86 ms 33052 KB Output is correct
4 Correct 63 ms 32288 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 32156 KB Output is correct
2 Correct 103 ms 33024 KB Output is correct
3 Correct 89 ms 34896 KB Output is correct
4 Correct 73 ms 34252 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 34852 KB Output is correct
2 Correct 156 ms 34580 KB Output is correct
3 Correct 159 ms 34480 KB Output is correct
4 Correct 183 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 149 ms 34128 KB Output is correct
2 Correct 166 ms 36672 KB Output is correct
3 Correct 253 ms 36440 KB Output is correct
4 Correct 156 ms 38348 KB Output is correct
5 Correct 406 ms 33692 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 34156 KB Output is correct
2 Correct 189 ms 34764 KB Output is correct
3 Correct 323 ms 33692 KB Output is correct
4 Correct 336 ms 33956 KB Output is correct
5 Correct 156 ms 38252 KB Output is correct
6 Correct 406 ms 33692 KB Output is correct