oj.uz

Submission #961867

# Submission time Handle Problem Language Result Execution time Memory
961867 2024-04-12T15:21:30 Z Gr1sen Arranging Shoes (IOI19_shoes) C++17
10 / 100
 1 ms 504 KB 
#include "shoes.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<stack>

using namespace std;

#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define vs vector<stack<int>>

struct segmentTree {
	int n;
	vi L;
	void set_n(int a) {
		n = a;
		L.resize(4*n, 0);
	}
	void update(int p, int l, int r, int x, int v) {
		if (l > x || r < x) return;
		if (l == r) {
			L[p] = v;
			return;
		}
		int m = (l+r)/2;
		update(p*2, l, m, x, v);
		update(p*2+1, m+1, r, x, v);
		L[p] = L[p*2] + L[p*2+1];
	}
	int query(int p, int l, int r, int x, int y) {
		//cerr << p << " " << l << " " << r << " " << x << " " << y << endl;
		if (l > y || r < x) return 0;
		if (x <= l && r <= y) {
			return L[p];
		}
		int m = (l+r)/2;
		return query(p*2, l, m, x, y) + query(p*2+1, m+1, r, x, y);
	}
};

ll count_swaps(vector<int> S) {
	//cerr << endl;
	int n = S.size();
	vs L(n*2+5);
	for (int i = n-1; i > -1; i--) L[S[i]+n].push(i);
	segmentTree T;
	T.set_n(n+5);
	ll t = 0;
	int p = 0;
	while (p < n) {
		//cerr << p << " " << t << endl;
		L[S[p]+n].pop();
		if (T.query(1, 0, n, p, p)) {
			//cerr << "oink" << endl;
			p++; continue;
		}
		//cerr << "oink" << endl;
		int a = L[S[p]*(-1)+n].top();
		t += a-p-T.query(1, 0, n, p, a);
		if (S[p] < 0) t--;
		T.update(1, 0, n, a, 1);
		p++;
	}
	return t;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Runtime error 1 ms 348 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 1 ms 348 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 432 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Runtime error 1 ms 348 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Runtime error 1 ms 348 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Runtime error 1 ms 348 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -