oj.uz

Submission #30125

# Submission time Handle Problem Language Result Execution time Memory
30125 2017-07-22T07:32:15 Z 김현수(#1247) Tree Rotations (POI11_rot) C++11
0 / 100
 213 ms 35740 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]);
	}
	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<=n;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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 30536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 30536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 30536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 30692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 31196 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 31388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 35740 KB Output is correct
2 Incorrect 23 ms 34100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 32156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 213 ms 34856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 109 ms 34136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 146 ms 34156 KB Output isn't correct
2 Halted 0 ms 0 KB -