| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 14613 |
2015-05-21T16:29:31 Z |
dydnjs |
공장 (KOI13_factory) |
C++ |
|
223 ms |
26060 KB |
#include<stdio.h>
#include<algorithm>
using namespace std;
#define MAX_N 1100000
//struct S {
// int m;
// int i;
//};
//S a[500001];
//S b[500001];
//struct s {
// int a;
// int b;
//} D[500001];
int tree[1<<22];
int A[MAX_N];
int B[MAX_N];
int n;
long long lim;
///////////정올책/////////////
// -> 인덱스 트리
//void update(int n) {
// while(n>1) {
// if(tree[n]>tree[n/2])
// tree[n/2]=tree[n];
// n>>=1;
// }
//}
//int lg_sum(int s, int e) {
// int m=0;
// while(s<e) {
// m=max(m, tree[e]);
// if(!(e%2)) e--;
// e>>=1, s>>=1;
// }
// if(s==e) m=max(m, tree[s]);
// return m;
//}
//////////////////////////////////
//이건 위키에서 긁은것. 더 짧음. -> [펜윅 트리] = [바이너리 인덱스드 트리]
int sum(int idx) {
int s = 0;
while(idx>0) {
s += tree[idx];
idx -= (idx&-idx);
}
return s;
}
//1~15까지의 합을 구하고 싶으면 차례대로 15번, 14번, 12번, 8번 노드를 더하면 된다.
//15, 14, 12, 8을 보면 각각 1111 -> 1110 -> 1100 -> 1000 임을 알 수 있다! 이것은 pos = pos & (pos - 1); 같은 코드를 이용하면 된다.
//이것은 제일 오른쪽의 1을 떼는 작업이다.
//따라서 부분합 하나를 구하는데에 드는 시간복잡도 역시 O(log N) 이다.
void update(int idx, int val, int N) {
while(idx <= N) {
tree[idx] += val;
idx += (idx&-idx);
}
}
//5번을 예로 들면 5, 6, 8, 16번 노드가 5번 원소를 갖고 있는데, 이진법으로 살펴보면 101, 110, 1000, 10000 이다.
//이것은 제일 오른쪽의 1의 자리에 1을 하나 더 더해주는 작업이다.
//이는 pos += (pos & -pos); 같은 코드를 이용하여 순회하면 된다. 따라서, 원소 한개를 업데이트하는 연산 역시 O(log N)이다.
//int binry_search(int k) {
// int l=0,r=n,mid,key=k;
// while(l<=r) {
// mid=(l+r)/2;
// if(key == a[mid].m) return a[mid].i;
// else if(key < a[mid].m) r=mid-1;
// else l=mid+1;
// }
//}
int main() {
//freopen("input.txt", "r" ,stdin);
/*int i,j,res;
for(i=1; i<=n; i++) {
scanf("%d", &a[i].m);
a[i].i = i;
}
sort(a, a+n, cmp);
for(i=1; i<=n; i++) {
scanf("%d", &b[i].m);
b[i].i = binry_search(b[i].m);
}
for(i=0; i<n; i++) {
D[i]=1;
for(j=0; j<i; j++) {
if(a[i].m>a[j].m && D[i] < D[j]+1) {
D[i] = D[j]+1;
if(res < D[i])
res = D[i];
}
}
}*/
// -> O(n^2) -> 노답;;;;; 바서+LIS -> D[500001][500001] 이라 노답;;;;;
// -> 그리고 O(n^2) 에도 걸림.
// -> 지금과 같이 만약 D[N][N]으로 했을 때 안되는 경우, 문제가 완전 꼬여버릴 수 있다.
// -> 이 정도로 꼬인다는 뜻은 답이 없다;;; 와 같은 뜻이다.
// -> 창의적인 방법은 인덱스트리를 보는 것이다.!
// -> 인덱스트리의 복잡도는 O(n*2), 즉 O(n) 이다.
// -> 즉 LIS(최대 증가 수열)를 구현하는 것은 1. D[N][N]의 구현과
// 2. 인덱스트리로의 구현이 있는 것이다.
// -> 인덱스트리의 구현을 살펴보자.!
// -> 다음은 구종만의 알고리즘 트레이닝 북을 참조한 인덱스트리의 정의이다.
// = 구간 트리의 궁극적인 진화 형태는 펜윅 트리 혹은 이진 인덱스 트리라고 불리는 것입니다.
//
int i,base,t,lim;
long long res=0;
scanf("%d", &n);
//for(base=1;base<n;base*=2); 리프 노드의 인덱스를 구하기 위함.
for(i=1;i<=n;i++) {
scanf("%d", &t);
A[t]=i;
}
//A[t]가 갖는 인덱스 번호.
for(i=1;i<=n;i++) {
scanf("%d", &t);
//B[A[t]]=i;
res+=i-sum(A[t])-1;
update(A[t],1,n);
}
// 2 4 1 3 5 차례로 오는데,
// 2 다음 4면 교차점 없다. 인덱스 트리는 최소한의 노드만을 탐색하여 아래 구간의 최대 값을 찾을 수 있다.
// 4는 4이전에 입력된 데이터들 중 4 미만의 데이터의 최대값을 빠른 시간안안에 찾을 수 있다.
// 여기서는 그 전에 있었던값의 개수 중(i)-미만인 것이 몇개인지세서(sum(A[t]))-나자신도빼주고(-1) = 4가 들어옴으로써 추가된 교차점의 개수가 된다.
// 즉 포인트는 sum(A[t])로 O(logn)만에 현재노드 미만의 노드에서 현재노드 보다 미만인 노드가 몇개인지 세는 것이다.
//for(i=1;i<=n;i++) {
//res+=i-sum(B[i])-1;
//update(B[i],1,n);
//} -> 이렇게 B를 따로 만들 수도 있음.
printf("%lld\n", res);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
26060 KB |
Output is correct |
| 2 |
Correct |
0 ms |
26060 KB |
Output is correct |
| 3 |
Correct |
0 ms |
26060 KB |
Output is correct |
| 4 |
Correct |
0 ms |
26060 KB |
Output is correct |
| 5 |
Correct |
1 ms |
26060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
26060 KB |
Output is correct |
| 2 |
Correct |
0 ms |
26060 KB |
Output is correct |
| 3 |
Correct |
0 ms |
26060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
26060 KB |
Output is correct |
| 2 |
Correct |
0 ms |
26060 KB |
Output is correct |
| 3 |
Correct |
0 ms |
26060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
26060 KB |
Output is correct |
| 2 |
Correct |
0 ms |
26060 KB |
Output is correct |
| 3 |
Correct |
79 ms |
26060 KB |
Output is correct |
| 4 |
Correct |
87 ms |
26060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
146 ms |
26060 KB |
Output is correct |
| 2 |
Correct |
98 ms |
26060 KB |
Output is correct |
| 3 |
Correct |
175 ms |
26060 KB |
Output is correct |
| 4 |
Correct |
202 ms |
26060 KB |
Output is correct |
| 5 |
Correct |
223 ms |
26060 KB |
Output is correct |
| 6 |
Correct |
210 ms |
26060 KB |
Output is correct |
