Submission #1206564

#TimeUsernameProblemLanguageResultExecution timeMemory
1206564StefanSebezRotating Lines (APIO25_rotate)C++20
100 / 100
752 ms3752 KiB
#include "rotate.h" #include <vector> #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define ll long long #define ld long double const int N=50000; vector<array<int,2>>a; int n; vector<int>v; int dist(int x,int y){return min(abs(x-y),N-abs(x-y));} ll Calc(){ ll res=0; for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ res+=dist(v[i],v[j]); } } return res; } ll Calc1(int i){ ll res=0; for(int j=0;j<n;j++){ if(i==j) continue; res+=dist(v[i],v[j]); } return res; } int T[N+50]; void Update(int i,int x){i++;for(;i<=N;i+=i&-i)T[i]+=x;} int Get(int i){int x=0;i++;for(;i>=1;i-=i&-i)x+=T[i];return x;} int Get(int l,int r){ if(l<0) l+=N; if(r<0) r+=N; l%=N,r%=N; if(l<=r) return Get(r)-Get(l-1); return Get(N)+Get(r)-Get(l-1); } struct SegTree{ int root,nc,lc[2*N],rc[2*N],maks[2*N],lazy[2*N]; SegTree(){maks[0]=-1e9;} void update(int &c,int x){if(!c)c=++nc;maks[c]+=x;lazy[c]+=x;} void push(int &c){if(!c)c=++nc;update(lc[c],lazy[c]),update(rc[c],lazy[c]),lazy[c]=0;} void Update(int &c,int ss,int se,int qs,int qe,int qval){ if(!c)c=++nc; if(qs>qe||qe<ss||se<qs)return; if(qs<=ss&&se<=qe){update(c,qval);return;} int mid=ss+se>>1;push(c); Update(lc[c],ss,mid,qs,qe,qval),Update(rc[c],mid+1,se,qs,qe,qval); maks[c]=max(maks[lc[c]],maks[rc[c]]); } int Get(int &c,int ss,int se,int qs,int qe){ if(!c)c=++nc; if(qs>qe||qe<ss||se<qs)return -1e9; if(qs<=ss&&se<=qe)return maks[c]; int mid=ss+se>>1;push(c); return max(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe)); } void Update(int i,int x){ int l=i-N/2+1,r=i; l+=N;l%=N; if(l<=r) Update(root,0,N-1,l,r,x); else{ Update(root,0,N-1,0,N-1,x); Update(root,0,N-1,r+1,l-1,-x); } l=i+1,r=i+N/2; l%=N,r%=N; if(l<=r) Update(root,0,N-1,l,r,-x); else{ Update(root,0,N-1,0,N-1,-x); Update(root,0,N-1,r+1,l-1,x); } } }ST; void energy(int n1, std::vector<int> v1){ v=v1;n=n1; /*for(int i=0;i<n;i++) a.pb({v[i],i}); sort(a.begin(),a.end()); for(int i=0;i<n;i++){ if(i<=(n-1)/2){ rotate({a[i][1]},a[0][0]-a[i][0]); } else{ rotate({a[i][1]},a[0][0]-a[i][0]+N); } }*/ //ll res=Calc(); //for(auto i:v) Update(i,1); for(auto i:v) ST.Update(i,1); for(int i=0;i<n;i++){ //vector<int>x; /*for(int j=0;j<n;j++){ x.pb(v[j]); x.pb((v[j]+N/2)%N); }*/ //for(int j=0;j<N;j++) x.pb(j); int ct=0; while(0){ /*ll res=Calc1(i); v[i]=(v[i]+1)%N; ll x=Calc1(i); if(x<=res){ v[i]=(v[i]-1+N)%N; break; } res=x;*/ /*Update(v[i],-1); int x=Get(v[i]-N/2+1,v[i]); int y=Get(v[i]+1,v[i]+N/2); if(x<=y){ Update(v[i],1); break; } v[i]=(v[i]+1)%N; Update(v[i],1); ct++;*/ //rotate({i},1); } ST.Update(v[i],-1); int l,r,nxt=v[i]; if(ST.Get(ST.root,0,N-1,v[i],N-1)>=0){ //cerr<<"s1\n"; l=v[i],r=N-1; while(l<=r){ int mid=l+r>>1; int x=ST.Get(ST.root,0,N-1,v[i],mid); //printf("%i %i %i: %i\n",l,mid,r,x); if(x>=0) nxt=(mid-1+N)%N,r=mid-1; else l=mid+1; } } else{ l=0,r=v[i]-1; while(l<=r){ int mid=l+r>>1; int x=ST.Get(ST.root,0,N-1,0,mid); if(x>=0) nxt=(mid-1+N)%N,r=mid-1; else l=mid+1; } } //cerr<<nxt<<endl; rotate({i},nxt-v[i]); v[i]=nxt; ST.Update(v[i],1); /*ll maks=0,dx; for(auto X:x){ ll sum=0; for(int j=0;j<n;j++){ if(i==j) continue; sum+=dist(X,v[j]); } if(sum>=maks){ maks=sum; dx=X; } } rotate({i},dx-v[i]); v[i]=dx;*/ } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...