Submission #1238620

#TimeUsernameProblemLanguageResultExecution timeMemory
1238620al_reem_2010Arranging Shoes (IOI19_shoes)C++20
50 / 100
135 ms148756 KiB
// اَللَهُمَ صَلِ عَلَىَ مُحَمَدٍ وَ آلِ مُحَمَدٍ #include "bits/stdc++.h" #include "shoes.h" #include <iostream> #include <vector> #include <string> #include <algorithm> #include <cmath> #include <map> #include <set> #include <queue> #include <thread> #include <fstream> #include <stack> using namespace std ; //#define int long long #define pb push_back #define si size() #define fi first #define se second #define all(a) a.begin(),a.end() #define applejuice ios::sync_with_stdio(false) ; cin.tie(nullptr) ; cout.tie(nullptr) ; const int inf=1e9 ; const int mod=1e9+7 ; const int maxn=1e5+7 ; int tt=1 , sz=1<<17 , e=0 ; queue<int> lp[maxn] ; queue<int> ln[maxn] ; map<int,int> p ; bool u[maxn] ; long long seg[maxn*4] ; long long op(long long l , long long r) {return l+r ;} void build() { for(int i=sz-1 ; i>0 ; i--) {seg[i]=op(seg[i*2],seg[i*2+1]) ;} } void update(int k) { k+=sz ; seg[k]=0 ; for(k/=2 ; k>0 ; k/=2) {seg[k]=op(seg[k*2],seg[k*2+1]) ;} } long long get(int l , int r , int lo=0 , int hi=sz-1 , int x=1) { if(hi<l || r<lo) {return e ;} if(l<=lo && hi<=r) {return seg[x] ;} int mid=(lo+hi)/2 ; long long segl=get(l,r,lo,mid,x*2) ; long long segr=get(l,r,mid+1,hi,x*2+1) ; return op(segl,segr) ; } long long count_swaps(vector<int> s) { int n=(int)s.si ; for(int i=0 ; i<n ; i++) { if(s[i]<0 && !lp[abs(s[i])].empty()) { p[lp[abs(s[i])].front()]=i ; p[i]=lp[abs(s[i])].front() ; lp[abs(s[i])].pop() ; } else if(s[i]>0 && !ln[s[i]].empty()) { p[ln[s[i]].front()]=i ; p[i]=ln[s[i]].front() ; ln[s[i]].pop() ; } else if(s[i]<0) {ln[abs(s[i])].push(i) ;} else {lp[s[i]].push(i) ;} } int cnt=0 ; //for(int i=0 ; i<n ; i++) {cout << i << " " << p[i] << "\n" ;} for(int i=0 ; i<n ; i++) {seg[i+sz]=1 ;} //cout << get(0,n-1,1,0,n-1) << "\n" ; build() ; //update(2) ; //cout << get(0,sz-1,1,1) << "\n" ; //for(int i=0 ; i<2*sz ; i++) {cout <<i << " "<< seg[i] << "\n" ;} for(int i=n-1 ; i>=0 ; i--) { if(u[i]) {continue ;} if(p[i]+1!=i) { long long v=get(p[i]+1,i-1) ; //cout << v << "\n" ; cnt+=v ; } if(s[i]<0) {cnt+=1 ;} //cout << cnt << " " << i <<"\n" ; update(p[i]) ; u[i]=u[p[i]]=1 ; } return cnt ; } /*signed main() { //wrong applejuice ; //cin >> tt ; //while(tt--) {solve() ;} int n ; cin >> n ; vector<int> a(n*2) ; for(int i=0 ; i<n*2 ; i++) {cin >> a[i] ;} cout << count_swaps(a) ; }*/ /* 4 2 1 -2 -2 3 -1 2 -3 */
#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...