oj.uz

답안 #413183

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
413183 2021-05-28T10:52:29 Z 반딧불(#7606) Weird Numeral System (CCO21_day1problem2) C++17
0 / 25
 40 ms 44740 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Fenwick {
    int n;
    int tree[100002];

    void add(int x, int y){
        while(x<=n){
            tree[x] += y;
            x += x&-x;
        }
    }

    int sum(int x){
        int ret = 0;
        while(x){
            ret += tree[x];
            x -= x&-x;
        }
        return ret;
    }
} fenwick;

unordered_map<int, int> tree[400002];
void init(int i, int l, int r, int *A){
    for(int j=l; j<=r; j++) tree[i][A[j]]++;
    if(l==r) return;
    int m = (l+r)>>1;
    init(i*2, l, m, A);
    init(i*2+1, m+1, r, A);
}

ll query(int i, int l, int r, int A, int B){ /// A �����ʿ� �ִ� B�� ����
    if(!tree[i][A] && !tree[i][B]) return 0;
    if(r-l==1) return tree[i*2][A] * tree[i*2+1][B];
    int m = (l+r)>>1;
    return ll(tree[i*2][A]) * tree[i*2+1][B] + query(i*2, l, m, A, B) + query(i*2+1, m+1, r, A, B);
}

int n, k, q;
int arr[100002], perm[100002];
ll cnt[100002];
unordered_map<ll, ll> mapped;
ll ans;

ll query(int A, int B){
    ll key = A * 1000000000LL + B;
    if(mapped[key]) return mapped[key] - 1;
    ll tmp = query(1, 1, n, A, B);
    mapped[key] = tmp + 1;
    return tmp;
}

int main(){
    scanf("%d %d %d", &n, &k, &q);
    for(int i=1; i<=n; i++){
        scanf("%d", &arr[i]);
        cnt[arr[i]]++;
    }
    if(q > 5000) n = 10000;
    init(1, 1, n, arr);

    for(int i=1; i<=k; i++) perm[i] = i;
    fenwick.n = k;
    for(int i=1; i<=n; i++){
        ans += (i-1) - fenwick.sum(arr[i]);
        fenwick.add(arr[i], 1);
    }

    for(int i=1; i<=q; i++){
        int x;
        scanf("%d", &x);
        ll tmp = query(perm[x+1], perm[x]);
        ans += cnt[perm[x+1]] * cnt[perm[x]] - tmp*2;
        swap(perm[x+1], perm[x]);
        printf("%lld\n", ans);
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     scanf("%d %d %d", &n, &k, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%d", &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
Main.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 40 ms 44740 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 40 ms 44740 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -