oj.uz

Submission #30083

# Submission time Handle Problem Language Result Execution time Memory
30083 2017-07-22T05:09:04 Z 박상수(#1251) Tree Rotations (POI11_rot) C++11
100 / 100
 356 ms 26156 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

int n;
ll ans;
int P[200020], z;
int temp[200020];

int T[200002];
void update(int x, int v) {
	for(int i=x;i<=n;i+=(i&-i)) T[i] += v;
}

int read(int x){
	int res = 0;
	for(int i=x;i;i-=(i&-i)) res += T[i];
	return res;
}

map <pii, int> M;

void Do(int a, int c) {
	if(M.find(pii(a, c)) == M.end()) { update(P[a], 1); return; }
	int b = M[pii(a, c)];
	if(b-a < c-b) {
		Do(a, b);
		for(int i=a;i<b;i++) update(P[i], -1);
		Do(b, c);
		ll t = 0;
		for(int i=a;i<b;i++) t += c - b - read(P[i]);
		t = min(t, (ll)(b-a) * (c-b) - t);
		ans += t;
		for(int i=a;i<b;i++) update(P[i], 1);
	}
	else {
		Do(b, c);
		for(int i=b;i<c;i++) update(P[i], -1);
		Do(a, b);
		ll t = 0;
		for(int i=b;i<c;i++) t += read(P[i]);
		t = min(t, (ll)(b-a) * (c-b) - t);
		ans += t;
		for(int i=b;i<c;i++) update(P[i], 1);
	}
}

void read() {
	int x; scanf("%d", &x);
	if(x == 0) {
		int a = z;
		read();
		int b = z;
		read();
		int c = z;
		M[pii(a, c)] = b;
	}
	else P[z++] = x;
}

void solve(){
	scanf("%d", &n);
	read();
	Do(0, z);
	printf("%lld\n", ans);
}

int main(){
	int T = 1; // scanf("%d", &T);
	while(T--) {
		solve();
	}
	
	return 0;
}

Compilation message

rot.cpp: In function 'void read()':
rot.cpp:77:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int x; scanf("%d", &x);
                        ^
rot.cpp: In function 'void solve()':
rot.cpp:90:17: 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 4368 KB Output is correct
2 Correct 0 ms 4368 KB Output is correct
3 Correct 0 ms 4368 KB Output is correct
4 Correct 0 ms 4368 KB Output is correct
5 Correct 0 ms 4368 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4792 KB Output is correct
2 Correct 3 ms 4632 KB Output is correct
3 Correct 3 ms 4792 KB Output is correct
4 Correct 3 ms 4852 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5928 KB Output is correct
2 Correct 13 ms 5160 KB Output is correct
3 Correct 46 ms 6216 KB Output is correct
4 Correct 16 ms 5736 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 7536 KB Output is correct
2 Correct 43 ms 9148 KB Output is correct
3 Correct 39 ms 10704 KB Output is correct
4 Correct 49 ms 10724 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 16680 KB Output is correct
2 Correct 73 ms 13668 KB Output is correct
3 Correct 93 ms 11424 KB Output is correct
4 Correct 76 ms 10440 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 12048 KB Output is correct
2 Correct 126 ms 13612 KB Output is correct
3 Correct 126 ms 17500 KB Output is correct
4 Correct 139 ms 17104 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 18920 KB Output is correct
2 Correct 189 ms 17096 KB Output is correct
3 Correct 203 ms 17532 KB Output is correct
4 Correct 203 ms 16784 KB Output is correct
5 Correct 259 ms 15060 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 17812 KB Output is correct
2 Correct 223 ms 24520 KB Output is correct
3 Correct 239 ms 21872 KB Output is correct
4 Correct 219 ms 25680 KB Output is correct
5 Correct 299 ms 16512 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 17956 KB Output is correct
2 Correct 209 ms 19176 KB Output is correct
3 Correct 296 ms 16908 KB Output is correct
4 Correct 229 ms 17956 KB Output is correct
5 Correct 269 ms 26156 KB Output is correct
6 Correct 356 ms 16908 KB Output is correct