oj.uz

Submission #105773

# Submission time Handle Problem Language Result Execution time Memory
105773 2019-04-14T14:18:15 Z RezwanArefin01 Jousting tournament (IOI12_tournament) C++17
100 / 100
 213 ms 12584 KB 
#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
using namespace std; 

typedef pair<int, int> ii; 
typedef tree<
ii, null_type, less<ii>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

const int M = 2e5 + 10; 

struct node {
	int sum, flag, l, d; 
	node(int s=0, int f=0, int l=0, int d=0) :
		sum(s), flag(f), l(l), d(d) {} 
} t[M];

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	ordered_set st; 

	for(int i = 0; i < N - 1; i++) { 
		t[i] = node(K[i] > R, K[i] > R, i, 0); 
		st.insert({i, i}); 
	}

	t[N - 1] = node(0, 0, N - 1, 0);
	st.insert({N - 1, N - 1});
	
	int idx = N; 

	for(int i = 0; i < C; i++) {
		auto s = st.find_by_order(S[i]);  
		auto e = st.find_by_order(E[i]); 
		int lid = s -> second, rid = e -> second; 
			
		++e; 
		while(s != e) {
			int id = s -> second; 
			t[idx].sum += t[id].sum; 

			if(t[id].d + 1 > t[idx].d) {
				t[idx].d = t[id].d + 1;
				t[idx].l = t[id].l; 
			} 

			auto it = s; s++; 
			st.erase(it);
		}

		t[idx].flag = t[rid].flag; 
		st.insert({t[idx].l, idx});

		idx++; 
	}	

	int maxwin = 0, ans = 0;

	for(int i = 0; i < idx; i++) if(t[i].d >= maxwin){
		if(t[i].sum == 0 || (t[i].sum == 1 && t[i].flag)) {
			if(t[i].d > maxwin) {
				maxwin = t[i].d;
				ans = t[i].l; 
			} else {
				ans = min(ans, t[i].l);
			}
		}
	}

	return ans; 
}

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:37:7: warning: unused variable 'lid' [-Wunused-variable]
   int lid = s -> second, rid = e -> second; 
       ^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3456 KB Output is correct
2 Correct 4 ms 3456 KB Output is correct
3 Correct 5 ms 3584 KB Output is correct
4 Correct 6 ms 3456 KB Output is correct
5 Correct 5 ms 3456 KB Output is correct
6 Correct 5 ms 3456 KB Output is correct
7 Correct 5 ms 3456 KB Output is correct
8 Correct 6 ms 3456 KB Output is correct
9 Correct 5 ms 3456 KB Output is correct
10 Correct 6 ms 3456 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3456 KB Output is correct
2 Correct 11 ms 3840 KB Output is correct
3 Correct 10 ms 3840 KB Output is correct
4 Correct 9 ms 3840 KB Output is correct
5 Correct 10 ms 3840 KB Output is correct
6 Correct 10 ms 3840 KB Output is correct
7 Correct 11 ms 3840 KB Output is correct
8 Correct 10 ms 3840 KB Output is correct
9 Correct 9 ms 3840 KB Output is correct
10 Correct 16 ms 3840 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 7752 KB Output is correct
2 Correct 183 ms 12584 KB Output is correct
3 Correct 128 ms 10860 KB Output is correct
4 Correct 166 ms 12536 KB Output is correct
5 Correct 173 ms 12124 KB Output is correct
6 Correct 213 ms 11996 KB Output is correct
7 Correct 202 ms 12536 KB Output is correct
8 Correct 194 ms 12536 KB Output is correct
9 Correct 95 ms 10744 KB Output is correct
10 Correct 116 ms 10744 KB Output is correct