oj.uz

Submission #1112736

# Submission time Handle Problem Language Result Execution time Memory
1112736 2024-11-14T17:29:52 Z 0pt1mus23 Martian DNA (BOI18_dna) C++14
100 / 100
 1262 ms 27000 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
int nxt(){ int x;cin>>x; return x; }
const int mod = 1e9 +7, sze = 2e5 +23, inf = LLONG_MAX, LG = 20;

int T[sze*4];
int mal[sze];
int got[sze];
int gotur=0;
void build(int node,int l,int r){
    if(l==r){
        T[node]=mal[l];
        return;
    }

    int mid = (l+r)/2;
    build(2*node,l,mid);
    build(2*node +1,mid+1,r);
    T[node]=min(T[node *2 ],T[node *2 +1]);
}
int qry(int node,int l,int r,int lx,int rx){
    if( lx>r || rx<l ){
        return inf;
    }
    if(l<=lx && rx<=r){
        return T[node]; 
    }

    int mid = (lx+rx)/2;
    int left = qry(2*node,l,r,lx,mid);
    int right = qry(2*node +1,l,r,mid+1,rx);
    return min(left,right);
}
void upd(int node,int idx,int lx,int rx,int to){
    if(lx==rx){
        T[node]=to;
        return;
    }
    int mid = (lx+rx)/2;
    if( idx<=mid){
        upd(2*node,idx,lx,mid,to);
    }
    else{
        upd(2*node +1,idx,mid+1,rx,to);
    }
    T[node]=min(T[node *2 ],T[node *2 +1]);
}


void fast(){
    int n,k,rq;
    cin>>n>>k>>rq;
    map<int,vector<int>> var;
    
    vector<int> arr(n+1,0);
    generate(arr.begin()+1,arr.end(),nxt);
    
    vector<int> lazim(n+10,0);
    vector<int> last(n+10,0);
    int goturmeli = rq;
    while(rq--){
        int b,q;
        cin>>b>>q;
        lazim[b]=q;
    }
    for(int i=1;i<=n;i++){
        mal[i]=inf;
        if(lazim[arr[i]]){
            mal[i]=-inf;
            if(!var[arr[i]].empty()){
                last[i]=var[arr[i]].back();
            }
            var[arr[i]].pb(i);
            if(var[arr[i]].size()>=lazim[arr[i]]){
                mal[i]=var[arr[i]][ var[arr[i]].size() - lazim[arr[i]] ];
            }
        }
    }
    // for(int i =0;i<n;i++){
    //     cout<<mal[i+1]<<" ";
    // }
    // cout<<endl;
    build(1,0,n);
    // cout<<qry(1,1,2,0,n)<<endl;

    int l =1;
    int r = n;
    int ans=-1;
    // cout<<qry(1,2,5,0,n)<<endl;
    while(l<=r){
        int mid = (l+r)/2;

        bool flag=false;
        gotur = 0;
        for(int i =0;i<=n;i++){
            got[i]=0;
        }
        vector<pair<int,int>> recov;
        for(int i =1;i<=mid;i++){
            if(lazim[arr[i]]){
                if(++got[arr[i]]==1){
                    ++gotur;
                }
                else{
                    recov.pb({last[i],mal[last[i]]});
                    upd(1,last[i],0,n,inf);
                }
            }
        }
        if(gotur == goturmeli && qry(1,1,mid,0,n) > 0){
            flag=true;
        }
        else{

            for(int i =mid+1;i<=n;i++){
                if(lazim[ arr[i - mid] ]){
                    if( (--got[arr[i-mid]]) ==0){
                        --gotur;
                    }
                }
                if(lazim[arr[i]]){
                    if( (++got[arr[i]]) ==1 ){
                        ++gotur;
                    }
                    else{
                        // cout<<mid<<" sil"<<last[i]<<endl;
                        recov.pb({last[i],mal[last[i]]});
                        upd(1,last[i],0,n,inf);
                    }
                }
                if(gotur == goturmeli && qry(1,i-mid+1,i,0,n) > i-mid){
                    // cout<<mid<< " "<<i<<" "<<qry(1,i-mid+1,i,0,n)<<endl;
                    flag=true;
                    break;
                }
            }
        }

        for(auto [p,b]:recov){
            upd(1,p,0,n,b);
        }

        if(flag){
            ans = mid;
            r = mid-1;
        }
        else{
            l = mid+1;
        }
    }

    if(ans==-1){
        putr("impossible");
    }
    putr(ans);
}

signed main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    int tt = 1;

    // cin>>tt;
 
    while(tt--){
        fast();
    }
 
    return 0;
}

Compilation message

dna.cpp: In function 'void fast()':
dna.cpp:80:34: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} [-Wsign-compare]
   80 |             if(var[arr[i]].size()>=lazim[arr[i]]){
dna.cpp:145:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  145 |         for(auto [p,b]:recov){
      |                  ^

Subtask #1
16.0 / 16.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 712 KB Output is correct
2 Correct 8 ms 848 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 12 ms 848 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 444 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 444 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1110 ms 20744 KB Output is correct
2 Correct 935 ms 20404 KB Output is correct
3 Correct 289 ms 20320 KB Output is correct
4 Correct 877 ms 20844 KB Output is correct
5 Correct 58 ms 13384 KB Output is correct
6 Correct 837 ms 21864 KB Output is correct
7 Correct 170 ms 14004 KB Output is correct
8 Correct 59 ms 13508 KB Output is correct
9 Correct 324 ms 13112 KB Output is correct
10 Correct 1227 ms 21772 KB Output is correct
11 Correct 10 ms 592 KB Output is correct
12 Correct 8 ms 848 KB Output is correct
13 Correct 2 ms 592 KB Output is correct
14 Correct 2 ms 760 KB Output is correct
15 Correct 2 ms 592 KB Output is correct
16 Correct 11 ms 860 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 508 KB Output is correct
23 Correct 1 ms 500 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 23508 KB Output is correct
2 Correct 209 ms 22164 KB Output is correct
3 Correct 106 ms 15688 KB Output is correct
4 Correct 73 ms 16840 KB Output is correct
5 Correct 721 ms 27000 KB Output is correct
6 Correct 253 ms 25844 KB Output is correct
7 Correct 1186 ms 23588 KB Output is correct
8 Correct 877 ms 23700 KB Output is correct
9 Correct 1087 ms 21140 KB Output is correct
10 Correct 915 ms 20572 KB Output is correct
11 Correct 263 ms 20776 KB Output is correct
12 Correct 831 ms 21248 KB Output is correct
13 Correct 51 ms 13508 KB Output is correct
14 Correct 855 ms 21904 KB Output is correct
15 Correct 172 ms 14020 KB Output is correct
16 Correct 55 ms 13392 KB Output is correct
17 Correct 345 ms 13340 KB Output is correct
18 Correct 1262 ms 21776 KB Output is correct
19 Correct 9 ms 592 KB Output is correct
20 Correct 9 ms 1016 KB Output is correct
21 Correct 2 ms 592 KB Output is correct
22 Correct 2 ms 760 KB Output is correct
23 Correct 2 ms 592 KB Output is correct
24 Correct 12 ms 848 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 1 ms 336 KB Output is correct
28 Correct 1 ms 336 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 1 ms 336 KB Output is correct
31 Correct 1 ms 336 KB Output is correct
32 Correct 1 ms 336 KB Output is correct
33 Correct 1 ms 336 KB Output is correct