| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 830962 |
2023-08-19T13:42:51 Z |
vjudge1 |
Exam (eJOI20_exam) |
C++17 |
|
20 ms |
3280 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//turn on extra precision
//#pragma GCC target("fpmath=387")
using namespace std;
using namespace __gnu_pbds;
using str = string;
using ll = long long;
using pii = pair <int,int>;
using pll = pair <ll,ll>;
using vi = vector <int>;
using vll = vector <ll>;
using vpii = vector <pii>;
using vpll = vector <pll>;
template<class A, class B>
ostream& operator<<(ostream& os, const pair<A, B> &p) {
os << '(' << p.first << ',' << p.second << ')';
return os;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T> &v) {
bool van = 1; os << '{';
for(auto &i : v) { if(!van) os << ", "; os << i; van = 0; }
os << '}'; return os;
}
template<class T, size_t sz>
ostream& operator<<(ostream&os, const array<T,sz> &arr) {
bool fs = 1; os << '{';
for(auto &i : arr) { if(!fs) os << ", "; os << i; fs = 0; }
os << '}'; return os;
}
#define mp make_pair
#define fi first
#define se second
#define fs first.second
#define ss second.second
#define ff first.first
#define sf second.first
#define newl '\n'
#define all(x) x.begin(), x.end()
#define watch(x) cerr << (#x) << " is : " << (x) << newl
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <class T>
ll quickpow(ll num1, ll num2, const T MOD) {
assert(num2 >= 0); ll ans = 1;
for(; num2; num2>>=1, num1 = num1 * num1 % MOD) if(num2 & 1) ans = ans * num1 % MOD;
return ans;
}
// end of Template
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n; cin >> n;
vector<int> a(n+1), b(n+1);
for(int i = 1; i <= n; ++i) cin >> a[i];
for(int i = 1; i <= n; ++i) cin >> b[i];
const auto sub2 = [&b, &n]() -> bool {
for(int i = 2; i <= n; ++i) if(b[i] != b[i-1]) return false;
return true;
};
const auto sub4 = [&a, &n]() -> bool {
set<int> s;
for(int i = 1; i <= n; ++i) s.emplace(a[i]);
return s.size() == n;
};
if(sub2()) {
bool hasb = false;
int len = 0;
int res = 0;
for(int i = 1; i <= n; ++i) {
if(a[i] > b[i]) {
res += hasb * len;
len = 0;
hasb = false;
continue;
}
++len;
if(a[i] == b[i]) hasb = true;
}
res += hasb * len;
return cout << res << newl, 0;
}
if(sub4()) {
map<int,int> pos;
for(int i = 1; i <= n; ++i) pos[a[i]] = i;
class sparseTable {
private:
vector<vector<int>> st;
int n;
public:
sparseTable(vector<int> &v) : n(v.size() - 1) {
st.emplace_back(vector<int>(n+1));
for(int i = 1; i <= n; ++i) st[0][i] = v[i];
for(int i = 1; (1<<i) <= n; ++i) {
st.emplace_back(vector<int>(n+1));
for(int j = 1; j + (1<<i) - 1 <= n; ++j) {
st[i][j] = max(st[i-1][j], st[i-1][j+(1<<(i-1))]);
}
}
}
int getMin(int l, int r) {
int lv = __lg(r - l + 1);
return max(st[lv][l], st[lv][r-(1<<lv)+1]);
}
};
class fenwick {
private:
vector<int> BIT;
int n;
public:
fenwick(int n) : n(n) {
BIT.resize(n+1);
}
void update(int idx, int val) {
for(int i = idx; i <= n; i += i & -i) BIT[i] = max(BIT[i], val);
return;
}
int getMax(int idx) {
int res = 0;
for(int i = idx; i; i -= i & -i) res = max(res, BIT[i]);
return res;
}
};
sparseTable sparse(a);
fenwick BIT(n);
int ans = 0;
for(int i = 1; i <= n; ++i) {
if(!pos.count(b[i])) continue;
if(sparse.getMin(min(i, pos[b[i]]), max(i, pos[b[i]])) > b[i]) continue;
int res = 1 + BIT.getMax(pos[b[i]]);
BIT.update(pos[b[i]], 1);
ans = max(ans, res);
}
return cout << ans << newl, 0;
}
cout << -1 << newl;
return 0;
}
Compilation message
exam.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
6 | #pragma GCC optimization ("O3")
|
exam.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
7 | #pragma GCC optimization ("unroll-loops")
|
exam.cpp:8: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
8 | #pragma comment(linker, "/stack:200000000")
|
exam.cpp: In lambda function:
exam.cpp:84:25: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
84 | return s.size() == n;
| ~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
4 ms |
852 KB |
Output is correct |
| 3 |
Correct |
11 ms |
2048 KB |
Output is correct |
| 4 |
Correct |
8 ms |
1492 KB |
Output is correct |
| 5 |
Correct |
16 ms |
3020 KB |
Output is correct |
| 6 |
Correct |
8 ms |
1492 KB |
Output is correct |
| 7 |
Correct |
9 ms |
1620 KB |
Output is correct |
| 8 |
Correct |
20 ms |
3280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
