제출 #173005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
173005		FieryPhoenix	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	496 ms	32452 KiB

shoes

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <chrono>
#include <ctime>
#include <random>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <climits>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007

int N;
map<int,set<int>>mp;
int tree[200001];
bool dead[200001];

void update(int pos, int val){
  while (pos<=N*2){
    tree[pos]+=val;
    pos+=(pos&(-pos));
  }
}

int query(int pos){
  int ans=0;
  while (pos>=1){
    ans+=tree[pos];
    pos-=(pos&(-pos));
  }
  return ans;
}

ll count_swaps(vector<int>S){
  N=(int)S.size()/2;
  for (int i=1;i<=N*2;i++){
    mp[S[i-1]].insert(i);
    update(i,1);
  }
  ll ans=0;
  for (int i=1;i<=N*2;i++){
    if (dead[i])
      continue;
    int target=(*mp[S[i-1]*(-1)].begin());
    mp[S[i-1]*(-1)].erase(*mp[S[i-1]*(-1)].begin());
    mp[S[i-1]].erase(i);
    ans+=query(target)-query(i-1)-2;
    if (S[i-1]>0)
      ans++;
    dead[i]=true;
    update(i,-1);
    dead[target]=true;
    update(target,-1);
  }
  return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15