oj.uz

답안 #500741

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
500741 2022-01-01T05:01:49 Z sewon1407 공장 (KOI13_factory) C
20 / 20
 373 ms 15072 KB 
#include <stdio.h>

int n;
int seg[2100000];
int indexes[1000001];

int sum(int from, int to, int node, int start, int end) {
    if(from > end || to < start) return 0;
    if(from <= start && end <= to) return seg[node];
    int mid = (start+end)/2;
    return sum(from, to, node*2, start, mid)+sum(from, to, node*2+1, mid+1, end);
}

void update(int i, int diff, int node, int start, int end) {
    if(i < start || i > end) return;
    seg[node] += diff;
    int mid = (start+end)/2;
    if(start == end) return;
    update(i, diff, node*2, start, mid);
    update(i, diff, node*2+1, mid+1, end);
}

int main() {
    int t, p;
    unsigned long long cnt = 0;
    
    scanf("%d", &n);
    for(int i=0; i<n; i++) {
        scanf("%d", &t);
        indexes[t] = i;
    }
    for(int i=0; i<n; i++) {
        scanf("%d", &t);
        p = indexes[t];
        cnt += sum(p+1, n-1, 1, 0, n-1);
        update(p, 1, 1, 0, n-1);
    }
    printf("%llu", cnt);
}

Compilation message

factory.c: In function 'main':
factory.c:27:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf("%d", &n);
      |     ^~~~~~~~~~~~~~~
factory.c:29:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         scanf("%d", &t);
      |         ^~~~~~~~~~~~~~~
factory.c:33:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         scanf("%d", &t);
      |         ^~~~~~~~~~~~~~~

Subtask #1
2.2 / 2.2

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 288 KB Output is correct
3 Correct 1 ms 564 KB Output is correct
4 Correct 1 ms 1312 KB Output is correct
5 Correct 1 ms 1740 KB Output is correct

Subtask #2
3.4 / 3.4

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2724 KB Output is correct
2 Correct 5 ms 4308 KB Output is correct
3 Correct 8 ms 4428 KB Output is correct

Subtask #3
3.8 / 3.8

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 4768 KB Output is correct
2 Correct 40 ms 5364 KB Output is correct
3 Correct 47 ms 6076 KB Output is correct

Subtask #4
4.8 / 4.8

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 6476 KB Output is correct
2 Correct 97 ms 8356 KB Output is correct
3 Correct 125 ms 8896 KB Output is correct
4 Correct 188 ms 12236 KB Output is correct

Subtask #5
5.8 / 5.8

# 결과 실행 시간 메모리 Grader output
1 Correct 253 ms 13644 KB Output is correct
2 Correct 271 ms 14916 KB Output is correct
3 Correct 285 ms 14916 KB Output is correct
4 Correct 373 ms 15040 KB Output is correct
5 Correct 352 ms 15072 KB Output is correct
6 Correct 362 ms 14928 KB Output is correct