Editorial for USACO 2011 - Nov - Gold - Above the Median
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
#include <iostream> #include <algorithm> #include <cstdio> #define delta 100010 using namespace std; int f[200200]; int main() { int n,k,x=delta,s=0; long long re=0; cin >> n >> k; while (x<=n+delta) f[x]++, x+=x&-x; for (int i=1;i<=n;i++) { scanf("%d",&x); if (x>=k) s++; else s--; x=s+delta; while (x) re+=f[x], x-=x&-x; x=s+delta; while (x<=n+delta) f[x]++, x+=x&-x; } cout << re << endl; }
Code mẫu của happyboy99x
#include<algorithm> #include<iostream> #include<cstdio> using namespace std; const int N = 1e5; int sum[N+1], bit[N+1], a[N], n, x, m; void enter() { cin >> n >> x; for(int i = 0; i < n; ++i) { cin >> a[i]; a[i] = a[i] >= x ? 1 : -1; } } void generate() { sum[0] = 0; for(int i = 0; i < n; ++i) sum[i+1] = sum[i] + a[i]; m = n + 1; sort(sum, sum + m); m = unique(sum, sum + m) - sum; } int get(int idx) { int res = 0; for(int x = idx; x >= 0; x -= ~x & (x + 1)) res += bit[x]; return res; } void update(int idx, int v) { for(int x = idx; x < m; x += ~x & (x + 1)) bit[x] += v; } void solve() { update(lower_bound(sum, sum + m, 0) - sum, 1); int s = 0; long long res = 0; for(int i = 0; i < n; ++i) { s += a[i]; int v = lower_bound(sum, sum + m, s) - sum; res += get(v); update(v, 1); } cout << res << endl; } int main() { ios::sync_with_stdio(false); enter(); generate(); solve(); return 0; }
Code mẫu của ladpro98
program KMEDIAN; uses math; const maxn=2*trunc(1e5)+5; lb=trunc(1e5)+5; fi=''; var bit:array[1..maxn] of longint; a,s,n,k,i,t,lim:longint; res:int64; inp:text; procedure update(i:longint); begin while i<=lim do begin inc(bit[i]); i:=i+i and (-i); end; end; function get(i:longint):longint; var sum:longint; begin sum:=0; while i>0 do begin inc(sum,bit[i]); i:=i-i and (-i); end; exit(sum); end; begin assign(inp,fi);reset(inp); readln(inp,n,k); s:=n+1;lim:=s+n; update(s); for i:=1 to n do begin readln(inp,a); if a>=k then inc(s); if a<k then dec(s); inc(res,get(s)); update(s); end; write(res); end.
Code mẫu của RR
#include <iostream> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <iomanip> #include <bitset> #include <complex> #define FOR(i,a,b) for(int i = a; i <= b; ++i) #define FORD(i,a,b) for(int i = a; i >= b; --i) #define REP(i,a) for(int i = 0; i < a; ++i) #define MP make_pair #define PB push_back using namespace std; int n, x, bit[200111]; #define _(x) ((x) & (-(x))) void update(int u) { while (u <= 200000) { bit[u]++; u += _(u); } } int get(int u) { int res = 0; while (u) { res += bit[u]; u -= _(u); } return res; } int main() { while (scanf("%d%d", &n, &x) == 2) { memset(bit, 0, sizeof bit); int s = 100000, u; update(100000); long long res = 0; FOR(i,1,n) { scanf("%d", &u); if (u >= x) ++s; else --s; res += get(s); update(s); } cout << res << endl; } return 0; }
Code mẫu của hieult
#include<cstdio> #include<cmath> #include<math.h> #include<cstring> #include<cstdlib> #include<cassert> #include<ctime> #include<algorithm> #include<iterator> #include<iostream> #include<cctype> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<list> #define ep 0.00001 #define maxn 100111 #define oo 1111111111 #define modunlo 111539786 #define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++) //#define g 9.81 double const PI=4*atan(1.0); using namespace std; typedef pair<int, int> II; typedef vector<int> VI; typedef vector<II> VII; typedef vector<VI> VVI; typedef vector<VII> VVII; int x,t,so,a[100111],MIN; long long kq = 0,f[100011] = {0}; void update(int u){ while(u<=100000){ f[u]++; u+=u&-u; } } long long tinh(int u){ long long r = 0; while(u>0){ r+=f[u]; u-=u&-u; } return r; } int main(){ // freopen("I.10","r",stdin); // freopen("KMEDIAN.out","w",stdout); int n,k; cin>>n>>k; so = 0; a[0] = 0; MIN = 0; for(int i = 1;i<=n;i++){ scanf("%d",&x); if(x>=k) so++; a[i] = so*2-i; MIN = min(MIN,a[i]); } for(int i = 0;i<=n;i++){ a[i] = a[i]-MIN+1; kq+=tinh(a[i]); update(a[i]); } cout<<kq; }
Code mẫu của ll931110
#include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <fstream> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> #define maxn 100010 using namespace std; int n,x; pair<int,int> s[maxn]; int tx[maxn]; int main() { // freopen("median.in","r",stdin); // freopen("median.out","w",stdout); scanf("%d %d", &n, &x); s[1] = make_pair(0,1); for (int i = 2; i <= n + 1; i++) { scanf("%d", &s[i].first); if (s[i].first >= x) s[i].first = 1; else s[i].first = -1; s[i].first += s[i - 1].first; s[i].second = i; } sort(s + 1,s + n + 2); long long ret = 0; for (int i = 1; i <= n + 1; i++) { int u = s[i].second; for (int v = u; v; v -= (v & -v)) ret += tx[v]; for (int v = u; v <= n + 1; v += (v & -v)) tx[v]++; } cout << ret << endl; }
Code mẫu của skyvn97
#include<algorithm> #include<cstdio> #include<vector> #define MAX 100100 #define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1) #define REP(i,n) for (int i=0;i<(n);i=i+1) #define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++) using namespace std; int s[MAX]; int t[MAX]; int c[MAX]; int n; vector<int> val; void init(void) { int v,x; scanf("%d",&n); scanf("%d",&x); val.push_back(0); FOR(i,1,n) { scanf("%d",&v); s[i]=s[i-1]+(v>=x)-(v<x); val.push_back(s[i]); } sort(val.begin(),val.end()); val.resize(unique(val.begin(),val.end())-val.begin()); REP(i,n+1) c[i]=lower_bound(val.begin(),val.end(),s[i])-val.begin()+1; } void update(int x) { while (1<=x && x<=n+7) { t[x]++; x+=x&(-x); } } int count(int x) { int ret=0; while (1<=x && x<=n+7) { ret+=t[x]; x=x&(x-1); } return (ret); } void process(void) { long long res=0LL; FOR(i,0,n) { res+=count(c[i]); update(c[i]); } printf("%lld",res); } int main(void) { init(); process(); return 0; }
Comments