oj.uz

Submission #30132

# Submission time Handle Problem Language Result Execution time Memory
30132 2017-07-22T07:41:13 Z 시제연(#1249) Tree Rotations (POI11_rot) C++11
81 / 100
 1000 ms 60584 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

struct node {
	int l, r, v;
	node(){}
	node(int l, int r, int v):l(l),r(r),v(v){}
};

int n;
struct PST {
	int p;
	node tree[4000000];
	PST() {p=1;tree[0]=node(-1,-1,0);}
	int add(const int l, const int r, const int val, const int ori) {
		tree[p++] = (~ori)?node(l,r,tree[ori].v+val):node(l,r,val);
		return p-1;
	}
	int add(const int val, const int ori) {
		return add(-1,-1,val,ori);
	}
	int upd(const int idx, const int val, const int ori, const int s = 0, const int e = n-1) {
		if (e<idx||idx<s) return ori;
		if (s==e) return add(val,ori);
		return add(upd(idx,val,(~ori)?tree[ori].l:-1,s,(s+e)>>1),upd(idx,val,(~ori)?tree[ori].r:-1,((s+e)>>1)+1,e),val,ori);
	}
	int getv(const int S, const int E, const int cur, const int s = 0, const int e = n-1) {
		if (e<S||E<s||cur<0) return 0;
		if (S<=s&&e<=E) return tree[cur].v;
		return getv(S,E,tree[cur].l,s,(s+e)/2)+getv(S,E,tree[cur].r,(s+e)/2+1,e);
	}
} pst;
int head[200100];
int arr[200100];
int ord[200100];
pii ran[400100];
int lis[400100][2];
int p, q;
ll res;

int dnc() {
	int a;
	scanf("%d",&a);
	if (!a) {
		int lv = dnc(); int rv = dnc();
		lis[p][0] = lv; lis[p][1] = rv;
		ran[p] = pii(ran[lis[p][0]].first,ran[lis[p][1]].second); p++;
		return p-1;
	}
	lis[p][0] = lis[p][1] = -1; ran[p] = pii(q,q); p++;
	arr[q++] = a;
	return p-1;
}

int sz(int v) {return ran[v].second-ran[v].first+1;}

int main() {
	int i, j;

	scanf("%d",&n);
	dnc();
	for (i=0;i<n;i++) ord[i] = i;
	sort(ord,ord+n,[](int a, int b){return arr[a]<arr[b];});
	for (i=0;i<n;i++) {
		int idx = ord[i];
		head[i+1] = pst.upd(ord[i],1,head[i]);
	}
	for (i=0;i<p;i++) {
		if (sz(i)==1) continue;
		int l = lis[i][0], r = lis[i][1];
		if (sz(l)<sz(r)) swap(l,r);
		ll sum = 0, all = 1LL*sz(l)*sz(r);
		for (j=ran[r].first;j<=ran[r].second;j++) sum += 1LL*pst.getv(ran[l].first,ran[l].second,head[arr[j]-1]);
		res += min(sum,all-sum);
	}
	printf("%lld\n",res);

    return 0;
}

Compilation message

rot.cpp: In function 'int main()':
rot.cpp:69:7: warning: unused variable 'idx' [-Wunused-variable]
   int idx = ord[i];
       ^
rot.cpp: In function 'int dnc()':
rot.cpp:47:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&a);
                ^
rot.cpp: In function 'int main()':
rot.cpp:64:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 57736 KB Output is correct
2 Correct 19 ms 57520 KB Output is correct
3 Correct 99 ms 57520 KB Output is correct
4 Correct 26 ms 57628 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 57520 KB Output is correct
2 Correct 89 ms 58020 KB Output is correct
3 Correct 123 ms 58452 KB Output is correct
4 Correct 133 ms 58368 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 59868 KB Output is correct
2 Correct 169 ms 58776 KB Output is correct
3 Correct 236 ms 58076 KB Output is correct
4 Correct 183 ms 57612 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 57520 KB Output is correct
2 Correct 299 ms 58056 KB Output is correct
3 Correct 213 ms 59308 KB Output is correct
4 Correct 243 ms 59224 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 969 ms 58680 KB Output is correct
2 Correct 283 ms 58076 KB Output is correct
3 Correct 559 ms 58304 KB Output is correct
4 Correct 593 ms 57924 KB Output is correct
5 Correct 786 ms 57520 KB Output is correct

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 57956 KB Output is correct
2 Correct 539 ms 60148 KB Output is correct
3 Correct 706 ms 59316 KB Output is correct
4 Correct 423 ms 60584 KB Output is correct
5 Execution timed out 1000 ms 57520 KB Execution timed out

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 57784 KB Output is correct
2 Correct 689 ms 58200 KB Output is correct
3 Execution timed out 1000 ms 57520 KB Execution timed out
4 Halted 0 ms 0 KB -