Submission #420958

#	Time	Username	Problem	Language	Result	Execution time	Memory
420958		nicolaalexandra	Martian DNA (BOI18_dna)	C++14	100 / 100	287 ms	140564 KiB

dna

#include <bits/stdc++.h>
#define DIM 200010
#define INF 2000000000
using namespace std;

int aint[DIM*4],v[DIM],f[DIM];
deque <int> d[DIM];
int n,k,r,i,x,y;

void build (int nod, int st, int dr){
    if (st == dr){
        if (f[st])
            aint[nod] = -INF;
        else aint[nod] = INF;

        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);

    aint[nod] = min (aint[nod<<1],aint[(nod<<1)|1]);
}

void update (int nod, int st, int dr, int poz, int val){
    if (st == dr){
        aint[nod] = val;
        return;
    }
    int mid = (st+dr)>>1;
    if (poz <= mid)
        update (nod<<1,st,mid,poz,val);
    else update ((nod<<1)|1,mid+1,dr,poz,val);

    aint[nod] = min (aint[nod<<1],aint[(nod<<1)|1]);
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>k>>r;
    for (i=1;i<=n;i++){
        cin>>v[i];
        v[i]++;
    }

    for (i=1;i<=r;i++){
        cin>>x>>y;
        x++;
        f[x] = y;
    }

    build (1,1,k);

    int sol = INF;
    for (i=1;i<=n;i++){
        d[v[i]].push_back(i);
        if (!f[v[i]])
            continue;

        if (d[v[i]].size() > f[v[i]])
            d[v[i]].pop_front();

        if (d[v[i]].size() == f[v[i]])
            update (1,1,k,v[i],d[v[i]].front());

        sol = min (sol,i - aint[1] + 1);
    }

    if (sol == INF)
        cout<<"impossible";
    else cout<<sol;


    return 0;
}

Compilation message (stderr)

dna.cpp: In function 'int main()':
dna.cpp:63:28: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |         if (d[v[i]].size() > f[v[i]])
      |             ~~~~~~~~~~~~~~~^~~~~~~~~
dna.cpp:66:28: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |         if (d[v[i]].size() == f[v[i]])
      |             ~~~~~~~~~~~~~~~^~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 28 / 28
• Subtask 4: 32 / 32