//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'
typedef pair<int, int> ii;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
inline int myrand(int l, int r) {
int ret = rand(); ret <<= 15; ret ^= rand();
if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
return os<<"(" <<p.first<<", "<<p.second<<")"; }
template<typename T> using min_pq =
priority_queue<T, vector<T>, greater<T> >;
//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};
struct MaxSegmentTree {
vector<int> t;
MaxSegmentTree() {}
MaxSegmentTree(vector<int> &vec) {
t.resize(vec.size() * 2);
for(int i = 0; i < vec.size(); i++) {
t[i + vec.size()] = vec[i];
}
for(int i = vec.size() - 1; i; i--) {
t[i] = max(t[i << 1], t[i << 1 | 1]);
}
}
int get_max(int l, int r) { r++; int ret = -1;
for(l += (t.size() >> 1), r += (t.size() >> 1); l < r; l >>= 1, r >>= 1) {
if(l & 1) ret = max(ret, t[l++]);
if(r & 1) ret = max(ret, t[--r]);
} return ret;
}
};
struct IntervalTree {
vector<vector<int>> t;
IntervalTree() {}
IntervalTree(int _N) {
t.resize(_N << 1);
}
void AddInterval(int l, int r, int val) { r++;
for(l += (t.size() >> 1), r += (t.size() >> 1); l < r; l >>= 1, r >>= 1) {
if(l & 1) t[l++].push_back(val);
if(r & 1) t[--r].push_back(val);
}
}
void sort() {
for(int i = 0; i < t.size(); i++) {
std::sort(all(t[i]));
}
}
int count(int p, int val) { int ret = 0;
for(p += (t.size() >> 1); p > 0; p >>= 1) ret += lower_bound(all(t[p]), val) - t[p].begin();
return ret;
}
};
vector<int> K, S, E;
int N, C, R;
vector<ii> intervals;
vector<int> val;
int get_max(int l, int r) {
int mx = -1;
for(int i = l; i <= r; i++) {
mx = max(mx, K[i]);
} return mx;
}
int GetBestPosition(int _N, int _C, int _R, int *_K, int *_S, int *_E) {
N = _N, C = _C, R = _R;
K.assign(N - 1, 0), S.assign(C, 0), E.assign(C, 0);
for(int i = 0; i < N - 1; i++) K[i] = _K[i];
for(int i = 0; i < C; i++) S[i] = _S[i], E[i] = _E[i];
ordered_set os;
for(int i = 0; i < N; i++) {
os.insert(ii(i, i));
}
for(int i = 0; i < C; i++) {
vector<ii> dlt;
auto l_it = os.find_by_order(S[i]);
auto r_it = os.find_by_order(E[i]);
ii in = ii(l_it -> first, r_it -> second);
r_it++;
for(auto it = l_it; it != r_it; it++) dlt.push_back(*it);
for(int i = 0; i < dlt.size(); i++) os.erase(dlt[i]);
os.insert(in);
intervals.push_back(in);
} val.resize(intervals.size());
MaxSegmentTree mst(K);
for(int i = 0; i < intervals.size(); i++) {
val[i] = mst.get_max(intervals[i].first, intervals[i].second - 1);
}
IntervalTree Itree(N);
for(int i = 0; i < intervals.size(); i++) {
Itree.AddInterval(intervals[i].first, intervals[i].second, val[i]);
}
Itree.sort();
int mx = -1, id = -1;
for(int i = 0; i < N; i++) {
int c = Itree.count(i, R);
if(c > mx) {
mx = c;
id = i;
}
}
return id;
}
Compilation message
tournament.cpp: In function 'int myrand(int, int)':
tournament.cpp:22:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
^~
tournament.cpp:22:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
^~~
tournament.cpp: In constructor 'MaxSegmentTree::MaxSegmentTree(std::vector<int>&)':
tournament.cpp:40:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < vec.size(); i++) {
~~^~~~~~~~~~~~
tournament.cpp: In member function 'void IntervalTree::sort()':
tournament.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < t.size(); i++) {
~~^~~~~~~~~~
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:106:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < dlt.size(); i++) os.erase(dlt[i]);
~~^~~~~~~~~~~~
tournament.cpp:113:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < intervals.size(); i++) {
~~^~~~~~~~~~~~~~~~~~
tournament.cpp:119:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < intervals.size(); i++) {
~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
356 KB |
Output is correct |
| 3 |
Correct |
4 ms |
484 KB |
Output is correct |
| 4 |
Correct |
3 ms |
592 KB |
Output is correct |
| 5 |
Correct |
2 ms |
592 KB |
Output is correct |
| 6 |
Correct |
3 ms |
592 KB |
Output is correct |
| 7 |
Correct |
3 ms |
592 KB |
Output is correct |
| 8 |
Correct |
3 ms |
592 KB |
Output is correct |
| 9 |
Correct |
2 ms |
592 KB |
Output is correct |
| 10 |
Correct |
2 ms |
592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
592 KB |
Output is correct |
| 2 |
Correct |
11 ms |
1360 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1360 KB |
Output is correct |
| 4 |
Correct |
11 ms |
1360 KB |
Output is correct |
| 5 |
Correct |
10 ms |
1360 KB |
Output is correct |
| 6 |
Correct |
10 ms |
1360 KB |
Output is correct |
| 7 |
Correct |
10 ms |
1404 KB |
Output is correct |
| 8 |
Correct |
11 ms |
1404 KB |
Output is correct |
| 9 |
Correct |
5 ms |
1404 KB |
Output is correct |
| 10 |
Correct |
12 ms |
1404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
126 ms |
6136 KB |
Output is correct |
| 2 |
Correct |
322 ms |
20708 KB |
Output is correct |
| 3 |
Correct |
154 ms |
20708 KB |
Output is correct |
| 4 |
Correct |
313 ms |
22072 KB |
Output is correct |
| 5 |
Correct |
307 ms |
23456 KB |
Output is correct |
| 6 |
Correct |
282 ms |
23456 KB |
Output is correct |
| 7 |
Correct |
299 ms |
26912 KB |
Output is correct |
| 8 |
Correct |
309 ms |
28880 KB |
Output is correct |
| 9 |
Correct |
127 ms |
28880 KB |
Output is correct |
| 10 |
Correct |
141 ms |
28880 KB |
Output is correct |
