oj.uz

Submission #985650

# Submission time Handle Problem Language Result Execution time Memory
985650 2024-05-18T12:25:54 Z Zbyszek99 Arranging Shoes (IOI19_shoes) C++17
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>
#include "shoes.h"
#define rep(i,n) for(int i = 0; i < n; i++)
#define ll long long
#define ss second 
#define ff first
using namespace std;

int wiel = 1024*256-1;
ll drzewo[1024*256-1];
int n;

void add_t(int akt, int p1, int p2, int s1, int s2)
{
	if(p2 < s1 || p1 > s2) return;
	if(p1 >= s1 && p2 <= s2)
	{
		drzewo[akt-1]++;
		return;
	}
	add_t(akt*2,p1,(p1+p2)/2,s1,s2);
	add_t(akt*2+1,(p1+p2)/2+1,p2,s1,s2);
}

int query_t(int akt)
{
	int wyn = drzewo[akt-1];
	if(akt != 1) wyn += query_t(akt/2);
	return wyn;
}

long long count_swaps(vector<int> s) 
{
	ll ans = 0;
	n = (int)s.size();
	set<pair<int,int>> se;
	rep(i,n)
	{
		se.insert({s[i],i});
	}
	//se.erase({s[0],0});
	rep(i,n)
	{
		if(se.find({s[i],i}) == se.end()) continue;
		cout << i << " i\n";
		set<pair<int,int>>::iterator t_ = se.lower_bound({-s[i],-1});
		pair<int,int> t = *t_;
		//cout << t.ff << " " << t.ss << " t\n";
		se.erase(se.find({t.ff,t.ss}));
		se.erase(se.find({s[i],i}));
		ll odl1 = query_t(wiel/2+1+i);
		ll odl2 = query_t(wiel/2+1+t.ss);
		add_t(1,0,wiel/2,t.ss,wiel/2);
		//cout << odl1 << " " << odl2 << " odl\n";
		if(s[i] < 0)
		{
			ans += -(odl2-odl1) + t.ss - i -1;
		}
		else
		{
			ans +=-(odl2-odl1) + t.ss - i;
		}
		//cout << ans << "\n\n";
	}
	return ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB secret mismatch
2 Halted 0 ms 0 KB -