oj.uz

Submission #967380

# Submission time Handle Problem Language Result Execution time Memory
967380 2024-04-22T03:46:58 Z lsi Arranging Shoes (IOI19_shoes) C++14
0 / 100
 11 ms 21592 KB 
#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;

typedef long long ll;
int nm[200100];
bool taken[200100];
int pir[200100];
vector<int> l[200100],r[200100];
int tre[200100];

int lowbit(int i){
	return i&(-i);
}

int ct(int p){
	int tp=0;
	for (int i=p;i;i-=lowbit(i)){
		tp+=tre[i];
	}
	return tp;
}

void ad(int p){
	for (int i=p;i<=200100;i+=lowbit(i)){
		tre[i]++;
	}
}

long long count_swaps(vector<int> s) {
	ll ans=0;
	memset(taken,false,sizeof taken);
	int n=s.size();
	for (int i=1;i<=n*2;i++){
		nm[i]=s[i-1];
		int tp=nm[i];
		if (tp<0) tp*=-1;
		if (nm[i]<0){
			if (r[tp].size()>0){
				pir[i]=r[tp][0];
				pir[r[tp][0]]=i;
				r[tp].erase(r[tp].begin());
				continue;
			}
			l[tp].push_back(i);
		}else{
			if (l[tp].size()>0){
				pir[i]=l[tp][0];
				pir[l[tp][0]]=i;
				l[tp].erase(l[tp].begin());
				continue;
			}
			r[tp].push_back(i);
		}
	}
	for (int i=1;i<=n*2;i++){
		if (taken[i]) continue;
		int tp,tpa=0;
		if (nm[i]>0){
			tpa+=1;
		}
		tp=pir[i];
		tpa+=tp-i-1;
		tpa-=ct(tp-1)-ct(i);
		taken[tp]=true;
		ad(tp);
		ans+=tpa;
		//printf("%d %d\n",tp,tpa);
	}
	return ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 21592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 21592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 21592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 21592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 21592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 21592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -