1260 | 2022-03-29 11:43:16 | vandras | Növekvő Ödön és a Másoló Varázsló | cpp14 | Időlimit túllépés 40/100 | 697ms | 60536 KiB |
#include <bits/stdc++.h>
using namespace std;
/*<DEBUG>*/
#define tem template <typename
#define can_shift(_X_, ...) enable_if_t<sizeof test<_X_>(0) __VA_ARGS__ 8, debug&> operator<<(T i)
#define _op debug& operator<<
tem C > auto test(C *x) -> decltype(cerr << *x, 0LL);
tem C > char test(...);
tem C > struct itr{C begin, end; };
tem C > itr<C> get_range(C b, C e) { return itr<C>{b, e}; }
struct debug{
#ifdef _LOCAL
~debug(){ cerr << endl; }
tem T > can_shift(T, ==){ cerr << boolalpha << i; return *this; }
tem T> can_shift(T, !=){ return *this << get_range(begin(i), end(i)); }
tem T, typename U > _op (pair<T, U> i){
return *this << "< " << i.first << " , " << i.second << " >"; }
tem T> _op (itr<T> i){
*this << "{ ";
for(auto it = i.begin; it != i.end; it++){
*this << " , " + (it==i.begin?2:0) << *it;
}
return *this << " }";
}
#else
tem T> _op (const T&) { return *this; }
#endif
};
tem T>
string _ARR_(T* arr, int sz){
string ret = "{ " + to_string(arr[0]);
for(int i = 1; i < sz; i++) ret += " , " + to_string(arr[i]);
ret += " }"; return ret;
}
#define exp(...) " [ " << #__VA_ARGS__ << " : " << (__VA_ARGS__) << " ]"
/*</DEBUG>*/
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef unsigned int uint;
typedef pair<int, int> pii;
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb push_back
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define TC int __TC__; cin >> __TC__; while(__TC__--)
#define ar array
const int INF = 1e9 + 7, N = 200005, M = 5003;
int a[N], b[N], n, m, dp[N];
vector<int> vals;
int get(int v){
return lower_bound(vals.begin(), vals.end(), v) - vals.begin();
}
int cnt_between(int l, int r){
// debug() << exp(lower_bound(b+1, b+m+1, l) - b) exp(l);
return lower_bound(b+1, b+m+1, r) - lower_bound(b+1, b+m+1, l);
}
int main()
{
FAST;
cin >> n >> m;
vals.resize(n+m);
for(int i = 1; i <= n; ++i){
cin >> a[i];
vals[i-1] = a[i];
}
for(int i = 1; i <= m; ++i){
cin >> b[i];
vals[n+i-1] = b[i];
}
sort(vals.begin(), vals.end());
a[0] = -1;
for(int i = 1; i <= n; ++i) a[i] = get(a[i]);
for(int i = 1; i <= m; ++i) b[i] = get(b[i]);
sort(b+1, b+m+1);
int mxN = vals.size();
//dp[i] : best solution up to ith element (ith is left unchanged)
dp[0] = 0;
dp[1] = 0;
set<ar<int,2>> st;
a[n+1] = INF;
st.insert({a[0], 0});
st.insert({a[1], 1});
for(int i = 2; i <= n+1; ++i){
dp[i] = INF;
for(auto [v, j] : st){
if(a[j] > a[i]) break;
if(a[j] < a[i] && cnt_between(a[j], a[i]) >= i-j-1) dp[i] = min(dp[i], dp[j] + i-j-1);
}
st.insert({a[i], i});
}
cout << min(dp[n], dp[n+1]) << '\n';
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 3ms | 1844 KiB | ||||
2 | Időlimit túllépés | 691ms | 3016 KiB | ||||
subtask2 | 5/5 | ||||||
3 | Elfogadva | 96ms | 7696 KiB | ||||
4 | Elfogadva | 101ms | 9636 KiB | ||||
5 | Elfogadva | 96ms | 11672 KiB | ||||
subtask3 | 10/10 | ||||||
6 | Elfogadva | 2ms | 8732 KiB | ||||
7 | Elfogadva | 1ms | 8720 KiB | ||||
8 | Elfogadva | 2ms | 8748 KiB | ||||
subtask4 | 15/15 | ||||||
9 | Elfogadva | 4ms | 8784 KiB | ||||
10 | Elfogadva | 4ms | 8804 KiB | ||||
11 | Elfogadva | 3ms | 8760 KiB | ||||
12 | Elfogadva | 4ms | 8824 KiB | ||||
subtask5 | 5/5 | ||||||
13 | Elfogadva | 351ms | 9548 KiB | ||||
14 | Elfogadva | 381ms | 9552 KiB | ||||
15 | Elfogadva | 351ms | 8156 KiB | ||||
subtask6 | 5/5 | ||||||
16 | Elfogadva | 331ms | 8248 KiB | ||||
17 | Elfogadva | 509ms | 8348 KiB | ||||
18 | Elfogadva | 495ms | 8456 KiB | ||||
19 | Elfogadva | 312ms | 8528 KiB | ||||
subtask7 | 0/10 | ||||||
20 | Időlimit túllépés | 620ms | 7352 KiB | ||||
21 | Időlimit túllépés | 607ms | 7392 KiB | ||||
22 | Időlimit túllépés | 638ms | 8820 KiB | ||||
23 | Elfogadva | 354ms | 8568 KiB | ||||
24 | Időlimit túllépés | 683ms | 7736 KiB | ||||
subtask8 | 0/25 | ||||||
25 | Elfogadva | 128ms | 23272 KiB | ||||
26 | Elfogadva | 118ms | 25148 KiB | ||||
27 | Elfogadva | 118ms | 27156 KiB | ||||
28 | Elfogadva | 1ms | 14100 KiB | ||||
29 | Időlimit túllépés | 694ms | 16876 KiB | ||||
30 | Időlimit túllépés | 694ms | 18896 KiB | ||||
31 | Időlimit túllépés | 677ms | 20756 KiB | ||||
32 | Időlimit túllépés | 676ms | 22740 KiB | ||||
33 | Időlimit túllépés | 694ms | 24704 KiB | ||||
34 | Időlimit túllépés | 691ms | 26612 KiB | ||||
35 | Időlimit túllépés | 665ms | 28656 KiB | ||||
36 | Időlimit túllépés | 693ms | 30416 KiB | ||||
37 | Időlimit túllépés | 694ms | 32432 KiB | ||||
38 | Időlimit túllépés | 693ms | 34328 KiB | ||||
39 | Időlimit túllépés | 694ms | 36300 KiB | ||||
40 | Időlimit túllépés | 685ms | 38424 KiB | ||||
41 | Időlimit túllépés | 676ms | 37728 KiB | ||||
42 | Időlimit túllépés | 693ms | 32464 KiB | ||||
43 | Időlimit túllépés | 694ms | 34976 KiB | ||||
44 | Időlimit túllépés | 697ms | 37060 KiB | ||||
45 | Időlimit túllépés | 694ms | 38804 KiB | ||||
subtask9 | 0/25 | ||||||
46 | Időlimit túllépés | 694ms | 44208 KiB | ||||
47 | Időlimit túllépés | 691ms | 48140 KiB | ||||
48 | Időlimit túllépés | 670ms | 52012 KiB | ||||
49 | Időlimit túllépés | 677ms | 52420 KiB | ||||
50 | Időlimit túllépés | 694ms | 48344 KiB | ||||
51 | Időlimit túllépés | 661ms | 52332 KiB | ||||
52 | Időlimit túllépés | 670ms | 55256 KiB | ||||
53 | Időlimit túllépés | 693ms | 59000 KiB | ||||
54 | Időlimit túllépés | 642ms | 60536 KiB | ||||
55 | Időlimit túllépés | 609ms | 41544 KiB |