Submission #1238644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238644		ayathk	Arranging Shoes (IOI19_shoes)	C++20	30 / 100	109 ms	116808 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
#define fi first 
#define se second 
#define all(a) a.begin(),a.end()
#define pb push_back
const int maxn = 1<<21;
int seg[2 * maxn];

int op(int a,int b){
  return a + b;
}

void update(int i,int v){
    i+=maxn;
    seg[i]=v;

    for(i /= 2;i > 0;i /= 2){
      seg[i] = op(seg[i * 2], seg[i * 2 +1 ]);
    }
}
 
int que(int l,int r,int lo = 0,int mx = maxn - 1,int x = 1){

    if (l <= lo && mx <= r)return seg[x];
    if (r < lo || mx < l)return 0;

    int mid= (lo + mx) / 2;
    int xl = x * 2,xr = xl+1;
    int tl = que(l,r,lo,mid,xl);
    int tr =que(l,r,mid+1,mx,xr);

    return op(tl,tr);
}

long long count_swaps(vector <int> s){
  vector <int> nm(maxn, -1);
  vector <vector <int>> ne(maxn);
  vector <vector <int>> pos(maxn);

  int n = s.size();

  for(int i = 0;i < n;i++){
    if(s[i] > 0){
      pos[s[i]].push_back(i);
    }
    else{
      ne[-s[i]].push_back(i);
    }
  }
  vector <bool> vis(maxn, 0);

  for(int i = n - 1;i >= 0;i--){
    if(vis[i])continue;
    vis[i] = 1;

    if(s[i] > 0){
      nm[i] = ne[s[i]].back();
      ne[s[i]].pop_back();
      ne[i].pop_back();
    }
    else{
      nm[i] = pos[-s[i]].back();
      pos[-s[i]].pop_back();
      pos[i].pop_back();
    }
    vis[nm[i]] = true;
  }

  fill(all(vis), false);

  for(int i = 0;i < n;i++){
    update(i, 1);
  }

  int ans = 0;
  for(int i = n - 1;i >= 0;i--){
    if(vis[i])continue ;

    vis[i] = vis[nm[i]] = true;

    if(s[i] > 0){
      if(nm[i] != i - 1)
        ans += que(nm[i] + 1, i - 1);

      update(nm[i], 0);
    }
    else{
      if(nm[i] != i - 1)
       ans += que(nm[i] + 1, i - 1);
      update(nm[i], 0);
    }
    
    if(s[i] < 0)ans++;
    //cout<<ans<<' ';
  }
  return ans;
}


// signed main() {
// 	int n;
// 	assert(1 == scanf("%d", &n));
// 	vector<int> S(2 * n);
// 	for (int i = 0; i < 2 * n; i++)
// 		assert(1 == scanf("%d", &S[i]));
// 	fclose(stdin);

// 	long long result = count_swaps(S);

// 	printf("%lld\n", result);
// 	fclose(stdout);
// 	return 0;
// }

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