oj.uz

Submission #927090

# Submission time Handle Problem Language Result Execution time Memory
927090 2024-02-14T08:57:56 Z vjudge1 Martian DNA (BOI18_dna) C++17
100 / 100
 153 ms 30052 KB 
/*
no more temmy :(
*/

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
// #include<icecream.hpp>
// using namespace icecream;
#define ll long long
#define int ll
#define ld long double
#define y1 cheza
// mt19937 rng(1983413);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int N=2e5+100;
const int M=1e3+1;
const int B=317;
const int mod=1e9+7;
const int INF=1e18;
const int lg=64;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
const double eps=1e-9;
int n,k,rr;
int a[N];
int b[N],q[N];
bool bad(){
    map<int,int>cnt;
    for(int i=1;i<=n;i++){
        cnt[a[i]]++;
    }
    for(int i=1;i<=rr;i++){
        if(cnt[b[i]]<q[i]){
            return 1;
        }
    }
    return 0;
}
vector<int>g[N];
int cnt[N];
void test(){
    cin>>n>>k>>rr;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        g[a[i]].push_back(i);
    }
    for(int i=0;i<=n;i++){
        g[i].push_back(n+1);
    }
    for(int i=1;i<=rr;i++){
        cin>>b[i]>>q[i];
        cnt[b[i]]=q[i];
    }
    if(bad()){
        cout<<"impossible\n";
        return;
    }
    int ans=INF;
    int r=0;
    for(int i=1;i<=rr;i++){
        r=max(r,g[b[i]][q[i]-1]);
    }
    for(int i=1;i<=n;i++){
        ans=min(ans,r-i+1);
        if(cnt[a[i]]){
            cnt[a[i]]++;
            if(cnt[a[i]]>=g[a[i]].size()){
                break;
            }
            r=max(r,g[a[i]][cnt[a[i]]-1]);
        }
    }
    cout<<ans<<'\n';

}
/*
*/  
 
signed main(){

    // ic.prefix("debug->| ");
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // cout.tie(nullptr);
    long long t2=1;
    //  cin>>t2;
    for(int i=1;i<=t2;i++){
        test();
    }
    
    return 0;
 
}

Compilation message

dna.cpp: In function 'void test()':
dna.cpp:72:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             if(cnt[a[i]]>=g[a[i]].size()){
      |                ~~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 3 ms 10844 KB Output is correct
4 Correct 3 ms 11096 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10748 KB Output is correct
7 Correct 3 ms 10588 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10676 KB Output is correct
11 Correct 2 ms 10840 KB Output is correct
12 Correct 2 ms 10584 KB Output is correct
13 Correct 2 ms 10584 KB Output is correct
14 Correct 2 ms 10584 KB Output is correct
15 Correct 2 ms 10588 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19012 KB Output is correct
2 Correct 21 ms 19076 KB Output is correct
3 Correct 26 ms 18900 KB Output is correct
4 Correct 21 ms 19044 KB Output is correct
5 Correct 66 ms 24164 KB Output is correct
6 Correct 23 ms 19332 KB Output is correct
7 Correct 27 ms 19036 KB Output is correct
8 Correct 126 ms 30052 KB Output is correct
9 Correct 46 ms 19976 KB Output is correct
10 Correct 28 ms 19104 KB Output is correct
11 Correct 2 ms 10844 KB Output is correct
12 Correct 2 ms 10844 KB Output is correct
13 Correct 3 ms 10844 KB Output is correct
14 Correct 4 ms 11100 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 3 ms 10844 KB Output is correct
17 Correct 2 ms 10724 KB Output is correct
18 Correct 2 ms 10588 KB Output is correct
19 Correct 2 ms 10588 KB Output is correct
20 Correct 2 ms 10588 KB Output is correct
21 Correct 3 ms 10588 KB Output is correct
22 Correct 2 ms 10588 KB Output is correct
23 Correct 2 ms 10588 KB Output is correct
24 Correct 2 ms 10584 KB Output is correct
25 Correct 2 ms 10584 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 23880 KB Output is correct
2 Correct 85 ms 22480 KB Output is correct
3 Correct 69 ms 22732 KB Output is correct
4 Correct 20 ms 18924 KB Output is correct
5 Correct 84 ms 25092 KB Output is correct
6 Correct 153 ms 29148 KB Output is correct
7 Correct 48 ms 20104 KB Output is correct
8 Correct 68 ms 21012 KB Output is correct
9 Correct 21 ms 19016 KB Output is correct
10 Correct 20 ms 18960 KB Output is correct
11 Correct 21 ms 18900 KB Output is correct
12 Correct 22 ms 19324 KB Output is correct
13 Correct 66 ms 24012 KB Output is correct
14 Correct 22 ms 19132 KB Output is correct
15 Correct 26 ms 19016 KB Output is correct
16 Correct 100 ms 30012 KB Output is correct
17 Correct 50 ms 20112 KB Output is correct
18 Correct 23 ms 19104 KB Output is correct
19 Correct 2 ms 11040 KB Output is correct
20 Correct 3 ms 10840 KB Output is correct
21 Correct 3 ms 11096 KB Output is correct
22 Correct 3 ms 11256 KB Output is correct
23 Correct 2 ms 10844 KB Output is correct
24 Correct 2 ms 10844 KB Output is correct
25 Correct 2 ms 10588 KB Output is correct
26 Correct 2 ms 10588 KB Output is correct
27 Correct 2 ms 10588 KB Output is correct
28 Correct 2 ms 10584 KB Output is correct
29 Correct 2 ms 10584 KB Output is correct
30 Correct 2 ms 10588 KB Output is correct
31 Correct 2 ms 10588 KB Output is correct
32 Correct 2 ms 10840 KB Output is correct
33 Correct 2 ms 10584 KB Output is correct