oj.uz

Submission #986873

# Submission time Handle Problem Language Result Execution time Memory
986873 2024-05-21T13:03:10 Z PagodePaiva Arranging Shoes (IOI19_shoes) C++17
10 / 100
 289 ms 281944 KB 
#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;
const int N = 400010;
queue <int> q[N];
int res[N];
int p[N];

struct Segtree{
	int tree[4*N], lazy[4*N];
	int join(int a, int b){
		return a+b;
	}
	void unlazy(int node, int l, int r){
		tree[node] += (r-l+1)*lazy[node];
		if(l != r){
			lazy[2*node] += lazy[node];
			lazy[2*node+1] += lazy[node];
		}
		lazy[node] = 0;
		return;
	}
	void build(int node, int l,int r){
		if(l == r){
			tree[node] = 0;
			lazy[node] = 0;
			return;
		}
		int mid = (l+r)/2;
		build(2*node, l, mid);
		build(2*node+1, mid+1, r);
		tree[node] = 0;
		lazy[node] = 0;
		return;
	}
	void update(int node, int l, int r, int tl, int tr, int val){
		unlazy(node,tl,tr);
		if(l <= tl and tr <= r){
			lazy[node] += val;
			unlazy(node,tl,tr);
			return;
		}
		if(l > tr or tl > r) return;
		int mid = (tl+tr)/2;
		update(2*node, l, r, tl, mid, val);
		update(2*node+1, l, r, mid+1, tr, val);
		tree[node] = join(tree[2*node], tree[2*node+1]);
		return;
	}
	int query(int node, int l, int r, int tl, int tr){
		unlazy(node, tl, tr);
		if(l <= tl and tr <= r) return tree[node];
		if(l > tr or tl > r) return 0;
		int mid = (tl+tr)/2;
		return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
	}
} seg;

long long count_swaps(std::vector<int> v) {
	int n = v.size();
	int num = n;
	for(int i = v.size()-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();
		}
	}
	seg.build(1, 1, n);
	for(int i = 1;i <= n;i++){
		// cout << res[i] << ' ';
		seg.update(1, res[i], res[i], 1, n, i);
	}
	int resp = 0;
	for(int i = n;i > 0;i--){
		resp += i - seg.query(1, i, i, 1, n);
		seg.update(1, seg.query(1, i, i, 1, n), i, 1, n, -1);
	}
	return resp;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 274932 KB Output is correct
2 Correct 131 ms 274900 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 274932 KB Output is correct
2 Correct 131 ms 274900 KB Output is correct
3 Correct 129 ms 274768 KB Output is correct
4 Correct 131 ms 274784 KB Output is correct
5 Correct 132 ms 274736 KB Output is correct
6 Correct 127 ms 274772 KB Output is correct
7 Correct 127 ms 274900 KB Output is correct
8 Correct 124 ms 274768 KB Output is correct
9 Correct 129 ms 274772 KB Output is correct
10 Correct 131 ms 274884 KB Output is correct
11 Correct 138 ms 274940 KB Output is correct
12 Correct 132 ms 274864 KB Output is correct
13 Correct 131 ms 274768 KB Output is correct
14 Incorrect 140 ms 274888 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 274932 KB Output is correct
2 Correct 131 ms 274900 KB Output is correct
3 Correct 129 ms 274772 KB Output is correct
4 Correct 131 ms 274896 KB Output is correct
5 Correct 126 ms 274888 KB Output is correct
6 Correct 129 ms 274768 KB Output is correct
7 Correct 149 ms 274768 KB Output is correct
8 Correct 141 ms 274768 KB Output is correct
9 Correct 138 ms 274776 KB Output is correct
10 Correct 127 ms 274768 KB Output is correct
11 Correct 126 ms 274824 KB Output is correct
12 Correct 126 ms 274772 KB Output is correct
13 Incorrect 126 ms 274768 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 274772 KB Output is correct
2 Correct 125 ms 274820 KB Output is correct
3 Correct 129 ms 274832 KB Output is correct
4 Correct 123 ms 274768 KB Output is correct
5 Incorrect 289 ms 281944 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 274932 KB Output is correct
2 Correct 131 ms 274900 KB Output is correct
3 Correct 129 ms 274768 KB Output is correct
4 Correct 131 ms 274784 KB Output is correct
5 Correct 132 ms 274736 KB Output is correct
6 Correct 127 ms 274772 KB Output is correct
7 Correct 127 ms 274900 KB Output is correct
8 Correct 124 ms 274768 KB Output is correct
9 Correct 129 ms 274772 KB Output is correct
10 Correct 131 ms 274884 KB Output is correct
11 Correct 138 ms 274940 KB Output is correct
12 Correct 132 ms 274864 KB Output is correct
13 Correct 131 ms 274768 KB Output is correct
14 Incorrect 140 ms 274888 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 274932 KB Output is correct
2 Correct 131 ms 274900 KB Output is correct
3 Correct 129 ms 274768 KB Output is correct
4 Correct 131 ms 274784 KB Output is correct
5 Correct 132 ms 274736 KB Output is correct
6 Correct 127 ms 274772 KB Output is correct
7 Correct 127 ms 274900 KB Output is correct
8 Correct 124 ms 274768 KB Output is correct
9 Correct 129 ms 274772 KB Output is correct
10 Correct 131 ms 274884 KB Output is correct
11 Correct 138 ms 274940 KB Output is correct
12 Correct 132 ms 274864 KB Output is correct
13 Correct 131 ms 274768 KB Output is correct
14 Incorrect 140 ms 274888 KB Output isn't correct
15 Halted 0 ms 0 KB -