oj.uz

Submission #30127

# Submission time Handle Problem Language Result Execution time Memory
30127 2017-07-22T07:37:34 Z 시제연(#1249) Tree Rotations (POI11_rot) C++11
90 / 100
 1000 ms 60580 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(int l, int r, int val, int ori) {
		tree[p++] = (~ori)?node(l,r,tree[ori].v+val):node(l,r,val);
		return p-1;
	}
	int add(int val, int ori) {
		return add(-1,-1,val,ori);
	}
	int upd(int idx, int val, int ori, int s = 0, 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(int S, int E, int cur, int s = 0, 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 3 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 9 ms 57744 KB Output is correct
2 Correct 26 ms 57520 KB Output is correct
3 Correct 83 ms 57520 KB Output is correct
4 Correct 13 ms 57628 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 57520 KB Output is correct
2 Correct 76 ms 58020 KB Output is correct
3 Correct 139 ms 58448 KB Output is correct
4 Correct 96 ms 58368 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 59872 KB Output is correct
2 Correct 173 ms 58780 KB Output is correct
3 Correct 263 ms 58080 KB Output is correct
4 Correct 213 ms 57616 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 57520 KB Output is correct
2 Correct 343 ms 58056 KB Output is correct
3 Correct 253 ms 59308 KB Output is correct
4 Correct 249 ms 59220 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 723 ms 58684 KB Output is correct
2 Correct 243 ms 58072 KB Output is correct
3 Correct 576 ms 58308 KB Output is correct
4 Correct 383 ms 57928 KB Output is correct
5 Correct 969 ms 57520 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 57960 KB Output is correct
2 Correct 379 ms 60152 KB Output is correct
3 Correct 483 ms 59312 KB Output is correct
4 Correct 283 ms 60580 KB Output is correct
5 Correct 979 ms 57520 KB Output is correct

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 57792 KB Output is correct
2 Correct 703 ms 58196 KB Output is correct
3 Correct 896 ms 57520 KB Output is correct
4 Correct 606 ms 57788 KB Output is correct
5 Correct 566 ms 60520 KB Output is correct
6 Execution timed out 1000 ms 57520 KB Execution timed out