#include "message.h" #include "teatr.h" #include <cstdio> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) typedef long long LL; int t[1 << 21]; void inc(int x) { x += 1 << 20; while (x) { ++t[x]; x >>= 1; } } int get(int x, int l, int a, int b) { int s = x - (1 << l) << 20 - l; int e = s + (1 << 20 - l); if (a == s && b == e) return t[x]; int m = (s + e) >> 1; int r = 0; if (a < m) r += get(x << 1, l + 1, a, m); if (b > m) r += get((x << 1) + 1, l + 1, m, b); return r; } int main() { if (MyNodeId()) return 0; int n = GetN(); LL r = 0; REP(i,n) { int x = GetElement(i) - 1; r += get(1, 0, x + 1, 1000000); inc(x); } printf("%d\n", r); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | #include "message.h" #include "teatr.h" #include <cstdio> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) typedef long long LL; int t[1 << 21]; void inc(int x) { x += 1 << 20; while (x) { ++t[x]; x >>= 1; } } int get(int x, int l, int a, int b) { int s = x - (1 << l) << 20 - l; int e = s + (1 << 20 - l); if (a == s && b == e) return t[x]; int m = (s + e) >> 1; int r = 0; if (a < m) r += get(x << 1, l + 1, a, m); if (b > m) r += get((x << 1) + 1, l + 1, m, b); return r; } int main() { if (MyNodeId()) return 0; int n = GetN(); LL r = 0; REP(i,n) { int x = GetElement(i) - 1; r += get(1, 0, x + 1, 1000000); inc(x); } printf("%d\n", r); } |