제출 #172548

#제출 시각아이디문제언어결과실행 시간메모리
172548dsjongArranging Shoes (IOI19_shoes)C++14
100 / 100
141 ms14584 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; vector<int>pos[200005]; int n; long long cnt=0; int get(int x){ if(x<0) return abs(x)+n; return x; } int fen[200005]; //add x to idx i void update(int i,int x){ for(int j=i;j<=2*n;j+=j&(-j)){ fen[j]+=x; } } int query(int i){ int ans=0; for(int j=i;j>0;j-=j&(-j)){ ans+=fen[j]; } return ans; } long long count_swaps(vector<int> s) { n=s.size()/2; for(int i=0;i<2*n;i++){ pos[get(s[i])].push_back(i); } for(int i=1;i<=2*n;i++) reverse(pos[i].begin(),pos[i].end()); memset(fen,0,sizeof fen); for(int i=1;i<=2*n;i++) update(i,1); for(int i=0;i<2*n;i++){ //cout<<i<<": "; if(pos[get(s[i])].empty()||pos[get(s[i])].back()>i) continue; pos[get(s[i])].pop_back(); int j=pos[get(-s[i])].back(); pos[get(-s[i])].pop_back(); int posj=query(j), posi=query(i); if(s[i]<0){ cnt+=posj-posi-1; update(i+1,1); update(j+1,-1); } else{ cnt+=posj-posi; update(i+1,1); update(j+1,-1); } //cout<<cnt<<endl; } return cnt; }
#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...