IJPC 2012 #1

中間やら塾やらで疲れたのでのんびり解いていた()
藤原さん満点とかやばすぎる..

3は小課題3,4が全然わからなかった..

12点解法はやるだけ

#include "training.h"
#include <cstdio>
using namespace std;

int rock[30000];

void init(int N, int A[]){
    for(int i = 0; i < N; i++){
	rock[i] = A[i];
    }
}

void update(int i, int x){
    rock[i] = x;
}

int train(int p, int q){
    if(p + q > 200) return 0;
    int count = 0;
    for(int i = p; i <= q; i++){
	for(int j = i; j <= q; j++){
	    if(rock[i] > rock[j]) count++;
	}
    }
    return count;
}

30点解法は蟻本にBIT使う方法あったな〜とか思いつつ

#include "training.h" 
#include <cstring>
#include <vector> 
using namespace std; 
typedef long long ll;
 
int sz;
int rock[30000], a[30000];

int sum(int k){
    int res = 0;
    while(k > 0){
	res += a[k];
	k -= k & -k;
    }
    return res;
}

void add(int i){
    while(i <= sz){
	a[i]++;
	i += i & -i;
    }
}
 
void init(int N, int A[]){
    sz = N;
    for(int i = 0; i < N; i++){
	rock[i] = A[i];
    }
}

void update(int i, int x){
    rock[i] = x;
}
 
int train(int p, int q){
    ll ans = 0;
    memset(a, 0, sizeof(a));
    for(int i = p; i <= q; i++){
	ans += sum(sz) - sum(rock[i]);
	add(rock[i]);
    }
    return ans;
}

がんばって小課題3, 4も解きます..