Submission #680558

#	Time	Username	Problem	Language	Result	Execution time	Memory
680558		Cross_Ratio	Martian DNA (BOI18_dna)	C++14	100 / 100	296 ms	24260 KiB

dna

#include <bits/stdc++.h>
using namespace std;
struct SegTree {
    vector<int> seg;
    int MAX;
    SegTree(int N) {
        int i;
        for(i=1;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
        for(i=MAX/2;i<MAX;i++) seg[i] = i - MAX/2;
    }
    void cons() {
        for(int i = MAX/2-1;i>=1;i--) {
            seg[i] = min(seg[2*i], seg[2*i+1]);
        }
    }
    void prop(int n, int ns, int ne) {
        if(n<MAX/2) {
            seg[2*n] = max(seg[2*n], seg[n]);
            seg[2*n+1] = max(seg[2*n+1], seg[n]);
        }
    }
    void add(int s, int e, int n, int ns, int ne) {
        prop(n,ns,ne);
        if(e<=ns||ne<=s) return;
        if(s<=ns&&ne<=e) {
            seg[n] = 1e9;
            prop(n,ns,ne);
            return;
        }
        int mid = ns + ne >> 1;
        add(s, e, 2*n, ns, mid);
        add(s, e, 2*n+1, mid, ne);
        if(n<MAX/2) seg[n] = min(seg[2*n], seg[2*n+1]);
    }
    int sum(int s, int e, int n, int ns, int ne) {
        prop(n,ns,ne);
        if(e<=ns||ne<=s) return 1e9;
        if(s<=ns&&ne<=e) return seg[n];
        int mid = ns + ne >> 1;
        return min(sum(s, e, 2*n, ns, mid), sum(s, e, 2*n+1, mid, ne));
    }
};
int A[200005];
vector<int> V[200005];
vector<int> Query[200005];
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, K, R;
    cin >> N >> K >> R;
    int i, j;
    for(i=0;i<N;i++) cin >> A[i];
    for(i=0;i<N;i++) V[A[i]].push_back(i);
    bool isPos = true;
    for(i=0;i<R;i++) {
        int B, Q;
        cin >> B >> Q;
        if(V[B].size() < Q) {
            isPos = false;
            continue;
        }
        int sz = V[B].size();
        Query[0].push_back(V[B][Q-1]-1);
        for(j=0;j<sz;j++) {
            Query[V[B][j] + 1].push_back((j+Q < sz ? V[B][j+Q] - 1 : N));
        }
    }
    if(!isPos) {
        cout << "impossible";
        return 0;
    }
    SegTree tree(N+5);
    tree.cons();
    int MAX = tree.MAX;
    int ans = N;
    for(i=0;i<N;i++) {
        for(int n : Query[i]) {
            tree.add(i, n+1, 1, 0, MAX/2);
            //cout << "Add " << i << ' '<< n << '\n';
        }
        int res = tree.sum(i, N+1, 1, 0, MAX/2);
        if(res < N) ans = min(ans, res - i + 1);
        //cout<< i << " : " << res << '\n';
    }
    cout << ans;
}

Compilation message (stderr)

dna.cpp: In member function 'void SegTree::add(int, int, int, int, int)':
dna.cpp:32:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
dna.cpp: In member function 'int SegTree::sum(int, int, int, int, int)':
dna.cpp:41:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
dna.cpp: In function 'int main()':
dna.cpp:61:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |         if(V[B].size() < Q) {
      |            ~~~~~~~~~~~~^~~

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