Submission #3076061
Source Code Expand
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<vector> #define REP(i,m) for(int i=0;i<m;++i) #define pb push_back #define mp make_pair #define fr first #define sc second #define dump(x) cerr << #x << " = " << (x) << endl #define prl cerr<<"called:"<< __LINE__<<endl using namespace std; static const int INF =500000000; template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;} typedef long long int lint; typedef pair<int,int> pi; struct BIT{ int val[60005]; int n; int elem; void init(int n_){ n=1; elem=0; while(n<n_) n<<=1; REP(i,n+1) val[i]=0; } int add(int k,int a){// ..k] ++k; elem+=a; while(k>0){ val[k]+=a; k-=k&-k; } } int query(int k){//[k... ++k; int res=0; while(k<=n){ res+=val[k]; k+=k&-k; } return res; } int query2(int k){// ...k) int res=elem-query(k); return res; } }; static const int B=200; BIT bit[205]; BIT sum[205]; BIT bind[205]; int self[205],seq[30005]; int group; int n; void init(int N, int A[]) { n=N; REP(i,n) seq[i]=A[i]; for(int i=0;i<n;i+=B){ int m=min(B,n-i); bit[i/B].init(n+1); REP(j,m) bit[i/B].add(seq[i+j],1),self[i/B]+=bit[i/B].query(seq[i+j]+1); ++group; } REP(i,group) sum[i].init(n+1); REP(i,n){ for(int j=i/B;j<group;++j) sum[j].add(seq[i],1); } REP(i,group){ bind[i].init(group+1); REP(j,i){ for(int k=i*B;k<min(n,i*B+B);++k) bind[i].add(j,bit[j].query(seq[k]+1)); } } } void update(int k,int x){ int prev=seq[k]; int pos=k/B,m=min(pos*B+B,n)-pos*B; REP(i,m) bit[pos].add(seq[i+pos*B],-1); seq[k]=x; self[pos]=0; REP(i,m) bit[pos].add(seq[i+pos*B],1),self[pos]+=bit[pos].query(seq[i+pos*B]+1); for(int i=pos;i<group;++i){ sum[i].add(prev,-1); sum[i].add(x,1); } REP(i,pos){ bind[pos].add(i,-bit[i].query(prev+1)); bind[pos].add(i,bit[i].query(x+1)); } for(int i=pos+1;i<group;++i){ bind[i].add(pos,-bit[i].query2(prev)); bind[i].add(pos,bit[i].query2(x)); } } int tmp[205],zip[205]; BIT temp; int train(int p, int q) { int res=0; ++q; int qbegin=q/B; for(int i=0;i<qbegin;++i) res+=bind[i].query(0)+self[i]; qbegin*=B; int m=q-qbegin; REP(i,m) res+=(qbegin==0?0:sum[qbegin/B-1].query(seq[i+qbegin]+1)); REP(i,m) zip[i]=tmp[i]=seq[i+qbegin]; sort(zip,zip+m); int zn=unique(zip,zip+m)-zip; REP(i,m) tmp[i]=lower_bound(zip,zip+zn,tmp[i])-zip; temp.init(zn+1); REP(i,m) res+=temp.query(tmp[i]+1),temp.add(tmp[i],1); int pbegin=p/B; for(int i=0;i*B+B<=q;++i){ res-=bind[i].query2(pbegin); if(i<pbegin) res-=self[i]; } for(int i=qbegin;i<q;++i) res-=(pbegin==0?0:sum[pbegin-1].query(seq[i]+1)); pbegin*=B; if(qbegin!=pbegin){ m=p-pbegin; REP(i,m) zip[i]=tmp[i]=seq[i+pbegin]; REP(i,m) res-=sum[qbegin/B-1].query2(tmp[i])-sum[pbegin/B].query2(tmp[i]); sort(zip,zip+m); int zn=unique(zip,zip+m)-zip; REP(i,m) tmp[i]=lower_bound(zip,zip+zn,tmp[i])-zip; temp.init(zn+1); REP(i,m) res-=temp.query(tmp[i]+1),temp.add(tmp[i],1); for(int i=p;i<pbegin+B;++i) res-=temp.query(upper_bound(zip,zip+zn,seq[i])-zip); for(int i=qbegin;i<q;++i) res-=temp.query(upper_bound(zip,zip+zn,seq[i])-zip); }else{ m=p-pbegin; REP(i,m) zip[i]=tmp[i]=seq[i+pbegin]; sort(zip,zip+m); int zn=unique(zip,zip+m)-zip; REP(i,m) tmp[i]=lower_bound(zip,zip+zn,tmp[i])-zip; temp.init(zn+1); REP(i,m) res-=temp.query(tmp[i]+1),temp.add(tmp[i],1); for(int i=p;i<q;++i) res-=temp.query(upper_bound(zip,zip+zn,seq[i])-zip); } return res; }
Submission Info
Submission Time | |
---|---|
Task | C - 魔法の訓練 (Magical Training) |
User | cong666 |
Language | C++ (GCC 5.4.1) |
Score | 0 |
Code Size | 3628 Byte |
Status | CE |
Compile Error
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 0 has invalid symbol index 11 /usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 1 has invalid symbol index 12 /usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 2 has invalid symbol index 2 /usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 3 has invalid symbol index 2 /usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 4 has invalid symbol index 11 /usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 5 has invalid symbol index 13 /usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 6 has invalid symbol index 13 /usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 7 has invalid symbol index 13 /usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 8 has invalid symbol ...