oj.uz

Submission #987615

# Submission time Handle Problem Language Result Execution time Memory
987615 2024-05-23T07:24:11 Z Tsagana Arranging Shoes (IOI19_shoes) C++14
0 / 100
 162 ms 272724 KB 
#include "shoes.h"

#include<bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define F first
#define S second

#define meta int M = (L + R) / 2, x = 2 * id, y = x + 1

using namespace std;

queue<int> q[400001];
int res[400001];
int dp[400001];
 
struct Tree{
	int tree[1600001];
	void update(int id, int L, int R, int i){
		if (L == R) {tree[id] = 1; return ;}
		meta;
		if (L <= i && i <= M) update(x, L, M, i);
		else update(y, M + 1, R, i);
		tree[id] = tree[x] + tree[y];
	}
	int query(int id, int l, int r, int L, int R) {
		if (l <= L && R <= r) return tree[id];
		if (l >  R || L >  r) return 0;
		meta;
		return query(x, L, R, l, M) + query(y, L, R, M + 1, r);
	}
} T;
 
long long count_swaps(vector<int> v) {
	int n = v.size(), num = n;
	for (int i = n-1; i >= 0; i--) {
		if (q[v[i] + n].empty()) {
			if (v[i] > 0) {res[i+1] = num; q[n-v[i]].push(num-1);}
			else {res[i+1] = num-1; q[n-v[i]].push(num);}
			num -= 2;
		}
		else {res[i+1] = q[v[i]+n].front(); q[v[i]+n].pop();}
	}
	long long resp = 0;
	for (int i = 1; i <= n; i++){
		resp += T.query(1, res[i], n, 1, n);
		T.update(1, 1, n, res[i]);
	}
	return resp;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 162 ms 272628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 162 ms 272628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 162 ms 272628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 161 ms 272724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 162 ms 272628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 162 ms 272628 KB Output isn't correct
2 Halted 0 ms 0 KB -