Submission #1237626

#TimeUsernameProblemLanguageResultExecution timeMemory
1237626hamanp87Monochrome Points (JOI20_monochrome)C++17
100 / 100
982 ms10332 KiB
#include<bits/stdc++.h> using namespace std; using ll=long long; //#pragma GCC optimize("03,unroll-loops") //#pragma GCC target("avx2") //#pragma GCC target("sse4") #define all(v) v.begin(),v.end() #define F first #define S second #define pub push_back #define pob pop_back #define puf push_front #define pof pop_front //#define randi uniform_int_distribution<long long> #define damoon(v) v.resize(unique(all(v))-v.begin()) //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //randi dist(0,10000000000000000); typedef pair<int,int> pii; typedef pair<long long,long long> pll; typedef pair<int,bool> pib; typedef pair<long long,bool> plb; typedef pair<int,pii> pip; typedef pair<pii,int> ppi; typedef vector<int> veci; typedef vector<long long> vecl; typedef vector<bool> vecb; typedef vector<pii> vecp; typedef set<int> seti; typedef set<long long> setl; typedef set<pii> setp; typedef map<int,int> mapii; typedef map<long long,long long> mapll; typedef map<int,bool> mapib; typedef map<long long,bool> maplb; const int inf=1e9,mod=1e9+7,neginf=-1e9,N=4e5+5; const double PI=acos(-1); struct Fenwick { veci f; int n; Fenwick(int m) { n=m; f.assign(n+1,0); } void update(int i,int v) { for(++i;i<=n;i+=i&-i) f[i]+=v; } int get(int i) { int s=0; for(++i;i>0;i-=i&-i) s+=f[i]; return s; } }; int n; ll krj[N]; veci b,w; inline ll res(int i,Fenwick &Fen) { if(krj[i]!=-1) return krj[i]; vecp v; for(int j=0;j<n;j++) v.pub(pii(min(b[j],w[(j+i)%n]),max(b[j],w[(j+i)%n]))); sort(all(v),greater<>()); ll ret=0; for(int j=0;j<n;j++) { ret+=Fen.get(v[j].S); Fen.update(v[j].F+0,+1); Fen.update(v[j].S+1,-1); } for(int j=0;j<n;j++) { Fen.update(v[j].F+0,-1); Fen.update(v[j].S+1,+1); } return krj[i]=ret; } void solve() { cin>>n; for(int i=0;i<2*n;i++) { char c; cin>>c; if(c=='B') b.pub(i); else w.pub(i); } memset(krj,-1,sizeof(krj)); Fenwick Fen(N); int L=0,R=n; while(L<R) { int mid=(L+R)>>1; if(res(mid,Fen)<res(0,Fen)) { if(res(0,Fen)>res(1,Fen)) { L=mid+1; } else { R=mid-1; } } else { if(res(mid,Fen)<res(mid+1,Fen)) { L=mid+1; } else { R=mid-0; } } } cout<<res(L,Fen)<<"\n"; } int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); //ifstream fin("in.txt"); //ofstream fout("out.txt"); int t=1; //cin>>t; while(t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...