oj.uz

Submission #598278

# Submission time Handle Problem Language Result Execution time Memory
598278 2022-07-17T22:10:34 Z urosk Martian DNA (BOI18_dna) C++14
100 / 100
 127 ms 37472 KB 
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
using namespace __gnu_pbds;

typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define maxn 200005
ll n,k,r;
ll a[maxn];
ordered_set v[maxn];
ll c[maxn];
ll b[maxn];
int main(){
	daj_mi_malo_vremena
    cin >> n >> k >> r;
	for(ll i = 1;i<=n;i++) cin >> a[i];
	for(ll i = 1;i<=n;i++) a[i]++;
	for(ll i = 1;i<=n;i++) v[a[i]].insert(i);
	for(ll i = 1;i<=r;i++){
        ll x,y; cin >> x >> y;
        x++;
        b[i] = x;
        c[x] = y;
	}
    ll tr = 0;
    for(ll i = 1;i<=r;i++){
        ll x = b[i];
        if(sz(v[x])<c[x]){
            cout<<"impossible"<<endl;
            return 0;
        }
        tr = max(tr,*v[x].find_by_order(c[x]-1));
    }
    ll ans = llinf;
    for(ll i = 1;i<=n;i++){
        ans = min(tr-i+1,ans);
        ll x = a[i];
        if(c[x]==0) continue;
        c[x]++;
        if(sz(v[x])<c[x]) break;
        tr = max(tr,*v[x].find_by_order(c[x]-1));
    }
    cout<<ans<<endl;
	return 0;
}
/*
5 2 2
0 1 1 0 1
0 1
1 1
13 4 3
1 1 3 2 0 1 2 0 0 0 0 3 1
0 2
2 1
1 2

*/

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19028 KB Output is correct
2 Correct 13 ms 19028 KB Output is correct
3 Correct 14 ms 19028 KB Output is correct
4 Correct 14 ms 19132 KB Output is correct
5 Correct 14 ms 19028 KB Output is correct
6 Correct 15 ms 19124 KB Output is correct
7 Correct 14 ms 19128 KB Output is correct
8 Correct 17 ms 19156 KB Output is correct
9 Correct 18 ms 19016 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19412 KB Output is correct
2 Correct 18 ms 19412 KB Output is correct
3 Correct 17 ms 19396 KB Output is correct
4 Correct 15 ms 19384 KB Output is correct
5 Correct 16 ms 19424 KB Output is correct
6 Correct 15 ms 19388 KB Output is correct
7 Correct 14 ms 19076 KB Output is correct
8 Correct 14 ms 19028 KB Output is correct
9 Correct 14 ms 19056 KB Output is correct
10 Correct 14 ms 19124 KB Output is correct
11 Correct 15 ms 19028 KB Output is correct
12 Correct 19 ms 19116 KB Output is correct
13 Correct 15 ms 19080 KB Output is correct
14 Correct 15 ms 19132 KB Output is correct
15 Correct 15 ms 19028 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 33572 KB Output is correct
2 Correct 84 ms 33484 KB Output is correct
3 Correct 98 ms 33568 KB Output is correct
4 Correct 88 ms 33544 KB Output is correct
5 Correct 79 ms 34380 KB Output is correct
6 Correct 85 ms 33484 KB Output is correct
7 Correct 97 ms 33684 KB Output is correct
8 Correct 97 ms 34452 KB Output is correct
9 Correct 112 ms 34124 KB Output is correct
10 Correct 98 ms 33564 KB Output is correct
11 Correct 15 ms 19412 KB Output is correct
12 Correct 15 ms 19392 KB Output is correct
13 Correct 16 ms 19352 KB Output is correct
14 Correct 18 ms 19400 KB Output is correct
15 Correct 16 ms 19412 KB Output is correct
16 Correct 15 ms 19388 KB Output is correct
17 Correct 15 ms 19124 KB Output is correct
18 Correct 14 ms 19128 KB Output is correct
19 Correct 14 ms 19028 KB Output is correct
20 Correct 17 ms 19056 KB Output is correct
21 Correct 17 ms 19156 KB Output is correct
22 Correct 14 ms 19028 KB Output is correct
23 Correct 14 ms 19128 KB Output is correct
24 Correct 14 ms 19112 KB Output is correct
25 Correct 14 ms 19028 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 36156 KB Output is correct
2 Correct 91 ms 35644 KB Output is correct
3 Correct 87 ms 35120 KB Output is correct
4 Correct 88 ms 33480 KB Output is correct
5 Correct 122 ms 36728 KB Output is correct
6 Correct 116 ms 37472 KB Output is correct
7 Correct 101 ms 34224 KB Output is correct
8 Correct 116 ms 34652 KB Output is correct
9 Correct 127 ms 33588 KB Output is correct
10 Correct 89 ms 33588 KB Output is correct
11 Correct 89 ms 33560 KB Output is correct
12 Correct 86 ms 33536 KB Output is correct
13 Correct 90 ms 34324 KB Output is correct
14 Correct 85 ms 33536 KB Output is correct
15 Correct 93 ms 33756 KB Output is correct
16 Correct 93 ms 34396 KB Output is correct
17 Correct 102 ms 34128 KB Output is correct
18 Correct 100 ms 33556 KB Output is correct
19 Correct 15 ms 19412 KB Output is correct
20 Correct 15 ms 19396 KB Output is correct
21 Correct 14 ms 19412 KB Output is correct
22 Correct 15 ms 19396 KB Output is correct
23 Correct 15 ms 19392 KB Output is correct
24 Correct 15 ms 19412 KB Output is correct
25 Correct 14 ms 19044 KB Output is correct
26 Correct 15 ms 19120 KB Output is correct
27 Correct 15 ms 19128 KB Output is correct
28 Correct 14 ms 19040 KB Output is correct
29 Correct 15 ms 19028 KB Output is correct
30 Correct 14 ms 19128 KB Output is correct
31 Correct 14 ms 19128 KB Output is correct
32 Correct 14 ms 19028 KB Output is correct
33 Correct 15 ms 19116 KB Output is correct