Submission #2486616
Source Code Expand
#include <training.h> #include <algorithm> using namespace std; int n,a[30000],P[30001]; pair<int,int> pr[30000]; void init(int N, int A[]) { n=N; for(int i=0;i<n;i++){ a[i]=A[i]; pr[i].first=A[i]; pr[i].second=i; } sort(pr,pr+n); int bit[1<<16]={0}; P[0]=0; for(int i=0;i<n;i++){ P[i+1]=P[i]; int c=n-a[i]+1,p=c-1; while(p){ P[i+1]+=bit[p]; p-=p&(-p); } bit[c]++; while(c<1<<16){ c+=c&(-c); bit[c]++; } } } void update(int i, int x) { int k=0; for(int j=0;j<i;j++){ if(a[j]<=a[i]&&a[j]>x){ k++; } else if(a[j]>a[i]&&a[j]<=x){ k--; } } P[i+1]+=k; for(int j=i+1;j<n;j++){ if(a[i]<=a[j]&&x>a[j]){ k++; } else if(a[i]>a[j]&&x<=a[j]){ k--; } P[j+1]+=k; } int l=lower_bound(pr,pr+n,make_pair(a[i],i))-pr; pair<int,int> e=make_pair(x,i); if(a[i]<x){ int j; for(j=l;j+1<n&&pr[j+1]<e;j++){ pr[j]=pr[j+1]; } pr[j]=e; } else{ int j; for(j=l;0<=j-1&&e<pr[j-1];j--){ pr[j]=pr[j-1]; } pr[j]=e; } a[i]=x; } int train(int p, int q) { int A; if(n<=5000){ A=0; int bit[1<<16]={0}; for(int i=q;i>=p;i--){ int c=a[i],p=c-1; while(p){ A+=bit[p]; p-=p&(-p); } bit[c]++; while(c<1<<16){ c+=c&(-c); bit[c]++; } } } else{ A=P[q+1]-P[p]; int k=0; for(int i=0;i<n;i++){ if(pr[i].second<p){ A-=k; } else if(pr[i].second<=q){ k++; } } } return A; }
Submission Info
Submission Time | |
---|---|
Task | C - 魔法の訓練 (Magical Training) |
User | luogu_bot3 |
Language | C++ (GCC 5.4.1) |
Score | 0 |
Code Size | 1653 Byte |
Status | CE |
Compile Error
./Main.cpp:1:22: fatal error: training.h: No such file or directory #include <training.h> ^ compilation terminated.