oj.uz

Submission #680558

# Submission time Handle Problem Language Result Execution time Memory
680558 2023-01-11T07:39:47 Z Cross_Ratio Martian DNA (BOI18_dna) C++14
100 / 100
 296 ms 24260 KB 
#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

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.0 / 16.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9812 KB Output is correct
2 Correct 8 ms 9812 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 7 ms 9864 KB Output is correct
5 Correct 6 ms 9800 KB Output is correct
6 Correct 7 ms 9812 KB Output is correct
7 Correct 5 ms 9716 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 6 ms 9716 KB Output is correct
12 Correct 5 ms 9668 KB Output is correct
13 Correct 5 ms 9716 KB Output is correct
14 Correct 6 ms 9684 KB Output is correct
15 Correct 6 ms 9720 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 19532 KB Output is correct
2 Correct 181 ms 18856 KB Output is correct
3 Correct 177 ms 18808 KB Output is correct
4 Correct 196 ms 19640 KB Output is correct
5 Correct 99 ms 16344 KB Output is correct
6 Correct 242 ms 20260 KB Output is correct
7 Correct 19 ms 12420 KB Output is correct
8 Correct 108 ms 20044 KB Output is correct
9 Correct 105 ms 14860 KB Output is correct
10 Correct 212 ms 20156 KB Output is correct
11 Correct 7 ms 9852 KB Output is correct
12 Correct 7 ms 9812 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 6 ms 9812 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct
16 Correct 8 ms 9856 KB Output is correct
17 Correct 5 ms 9720 KB Output is correct
18 Correct 5 ms 9720 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 5 ms 9684 KB Output is correct
21 Correct 6 ms 9684 KB Output is correct
22 Correct 5 ms 9684 KB Output is correct
23 Correct 6 ms 9716 KB Output is correct
24 Correct 5 ms 9716 KB Output is correct
25 Correct 6 ms 9684 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 23396 KB Output is correct
2 Correct 272 ms 21980 KB Output is correct
3 Correct 158 ms 17656 KB Output is correct
4 Correct 143 ms 19380 KB Output is correct
5 Correct 54 ms 15780 KB Output is correct
6 Correct 242 ms 24260 KB Output is correct
7 Correct 247 ms 20684 KB Output is correct
8 Correct 255 ms 20220 KB Output is correct
9 Correct 190 ms 19536 KB Output is correct
10 Correct 196 ms 18720 KB Output is correct
11 Correct 166 ms 18804 KB Output is correct
12 Correct 192 ms 19632 KB Output is correct
13 Correct 98 ms 16332 KB Output is correct
14 Correct 207 ms 20280 KB Output is correct
15 Correct 20 ms 12372 KB Output is correct
16 Correct 113 ms 20000 KB Output is correct
17 Correct 97 ms 14820 KB Output is correct
18 Correct 211 ms 20208 KB Output is correct
19 Correct 8 ms 9812 KB Output is correct
20 Correct 9 ms 9856 KB Output is correct
21 Correct 6 ms 9812 KB Output is correct
22 Correct 7 ms 9812 KB Output is correct
23 Correct 7 ms 9732 KB Output is correct
24 Correct 9 ms 9936 KB Output is correct
25 Correct 6 ms 9716 KB Output is correct
26 Correct 5 ms 9716 KB Output is correct
27 Correct 5 ms 9684 KB Output is correct
28 Correct 6 ms 9812 KB Output is correct
29 Correct 5 ms 9704 KB Output is correct
30 Correct 5 ms 9684 KB Output is correct
31 Correct 5 ms 9684 KB Output is correct
32 Correct 5 ms 9684 KB Output is correct
33 Correct 5 ms 9684 KB Output is correct