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も解きます..