Submission #30129

#	Time	Username	Problem	Language	Result	Execution time	Memory
30129		khsoo01	Untitled (POI11_rot)	C++11	100 / 100	406 ms	38348 KiB

Main

#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 (stderr)

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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 10 / 10