oj.uz

Submission #680980

# Submission time Handle Problem Language Result Execution time Memory
680980 2023-01-12T07:35:53 Z someone Comparing Plants (IOI20_plants) C++14
100 / 100
 1348 ms 68076 KB 
#include <bits/stdc++.h>
#define deb first
#define fin second
#define mid ((deb + fin) >> 1)
using namespace std;
 
const int M = 1 << 19, N = 2 * M, T = 19, INF = 1e9 + 42;
 
int n, k, vals[N], corr[N], gauche[T][M], droite[T][M];
 
set<int> pos0, posMin;
int imin[N], nbInf[N], lazy[N], maxi[N];
 
void set0(int i, bool is0) {
    if(is0) {
        auto it = pos0.lower_bound(i);
        if((*it) <= i + k)
            posMin.erase((*it));
        it--;
        if(i > (*it) + k && n <= i && i < 2*n)
            posMin.insert(i);
        pos0.insert(i);
    } else {
        pos0.erase(i);
        posMin.erase(i);
        auto it = pos0.lower_bound(i);
        int nex = (*it);
        it--;
        if(nex > (*it) + k && n <= nex && nex < 2*n)
            posMin.insert(nex);
    }
}
 
inline void applyOp(int i, int add) {
    lazy[i] += add;
    nbInf[i] += add;
}
 
pair<int, int> update(int i, int deb, int fin, int l, int r, int add) {
    if(r <= deb || fin <= l)
        return {INF, -1};
    if(l <= deb && fin <= r) {
        applyOp(i, add);
        return {nbInf[i], imin[i]};
    }
    applyOp(i*2, lazy[i]);
    applyOp(i*2+1, lazy[i]);
    auto ans = min(update(i*2, deb, mid, l, r, add),
                   update(i*2+1, mid, fin, l, r, add));
                   
    lazy[i] = 0;
    nbInf[i] = min(nbInf[i*2], nbInf[i*2+1]);
    if(nbInf[i] == nbInf[i*2])
        imin[i] = imin[i*2];
    else
        imin[i] = imin[i*2+1];
    return ans;
}
 
void setMax(int i, int val) {
    i += M;
    while(i) {
        maxi[i] = max(maxi[i], val);
        i >>= 1;
    }
}
 
int getMax(int i, int deb, int fin, int l, int r) {
    if(r <= deb || fin <= l)
        return 0;
    if(l <= deb && fin <= r)
        return maxi[i];
    return max(getMax(i*2, deb, mid, l, r), getMax(i*2+1, mid, fin, l, r));
}
 
inline int getId(int i) {
    i %= n;
    if(i < 0)
        i += n;
    return i;
}
 
void init(int K, vector<int> r) {
    k = K;
    pos0.insert(INF);
    pos0.insert(-INF);
    
    k--;
    n = (int)r.size();
    for(int i = M; i < N; i++)
        imin[i] = i - M;
    for(int i = M-1; i > 0; i--)
        imin[i] = imin[i*2];
    
    for(int i = 0; i < n; i++) {
        r[i] = k - r[i];
        update(1, 0, M, i, i+1, r[i]);
        if(r[i] == 0) {
            set0(i, 1);
            set0(i + n, 1);
        }
    }
    
    for(int i = 0; i < n; i++) {
        int id = getId((*posMin.begin()));
        update(1, 0, M, id, id+1, INF);
        
        set0(id, 0);
        set0(id + n, 0);
        vals[id] = i+1;
        corr[i+1] = id;
        
        corr[0] = id;
        setMax(id, i+1);
        setMax(id + n, i+1);
        gauche[0][id] = getId(corr[getMax(1, 0, M, id + n - k, id + n)] - id),
        droite[0][id] = getId(corr[getMax(1, 0, M, id + 1, id + k + 1)] - id);
        if(gauche[0][id] > 0)
            gauche[0][id] -= n;
        
        if(id >= k) {
            update(1, 0, M, id - k, id, -1);
        } else {
            update(1, 0, M, 0, id, -1);
            update(1, 0, M, n + id - k, n, -1);
        }
        auto pii = update(1, 0, M, 0, n, 0);
        while(pii.first == 0) {
            update(1, 0, M, pii.second, pii.second+1, INF);
            set0(pii.second, 1);
            set0(pii.second + n, 1);
            pii = update(1, 0, M, 0, n, 0);
        }
    }
    
    for(int i = 1; i < T; i++) {
        for(int j = 0; j < n; j++) {
            gauche[i][j] = gauche[i-1][getId(j + gauche[i-1][j])] + gauche[i-1][j];
            droite[i][j] = droite[i-1][getId(j + droite[i-1][j])] + droite[i-1][j];
            if(gauche[i][j] < -3*n)
                gauche[i][j] = (gauche[i][j] % n) - 3 * n;
            if(droite[i][j] > 3*n)
                droite[i][j] = (droite[i][j] % n) + 3 * n;
        }
    }
}
 
int compare_plants(int x, int y) {
    int ans = 1;
    if(vals[x] < vals[y]) {
        swap(x, y);
        ans = -1;
    }
    int idl = x, idr = x, nbl = 0, nbr = 0;
    for(int i = T-1; i > -1; i--) {
        int l = getId(gauche[i][idl] + idl),
            r = getId(droite[i][idr] + idr);
        if(vals[l] >= vals[y]) {
            nbl += gauche[i][idl];
            idl = l;
        }
        if(vals[r] >= vals[y]) {
            nbr += droite[i][idr];
            idr = r;
        }
    }
    int l = x + nbl, r = x + nbr;
    if((l <= y - n && y - n <= r) || (l <= y && y <= r) || (l <= y + n && y + n <= r))
        return ans;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4820 KB Output is correct
2 Correct 3 ms 4820 KB Output is correct
3 Correct 3 ms 4820 KB Output is correct
4 Correct 3 ms 4820 KB Output is correct
5 Correct 3 ms 4820 KB Output is correct
6 Correct 100 ms 7604 KB Output is correct
7 Correct 247 ms 12428 KB Output is correct
8 Correct 1067 ms 56036 KB Output is correct
9 Correct 1048 ms 55940 KB Output is correct
10 Correct 968 ms 55804 KB Output is correct
11 Correct 1051 ms 54664 KB Output is correct
12 Correct 1031 ms 55040 KB Output is correct
13 Correct 889 ms 46128 KB Output is correct
14 Correct 1158 ms 64948 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4820 KB Output is correct
2 Correct 3 ms 4804 KB Output is correct
3 Correct 4 ms 4820 KB Output is correct
4 Correct 3 ms 4820 KB Output is correct
5 Correct 3 ms 4820 KB Output is correct
6 Correct 9 ms 5072 KB Output is correct
7 Correct 151 ms 8680 KB Output is correct
8 Correct 5 ms 4948 KB Output is correct
9 Correct 9 ms 5124 KB Output is correct
10 Correct 188 ms 8580 KB Output is correct
11 Correct 143 ms 8580 KB Output is correct
12 Correct 142 ms 8908 KB Output is correct
13 Correct 146 ms 8576 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4820 KB Output is correct
2 Correct 3 ms 4804 KB Output is correct
3 Correct 4 ms 4820 KB Output is correct
4 Correct 3 ms 4820 KB Output is correct
5 Correct 3 ms 4820 KB Output is correct
6 Correct 9 ms 5072 KB Output is correct
7 Correct 151 ms 8680 KB Output is correct
8 Correct 5 ms 4948 KB Output is correct
9 Correct 9 ms 5124 KB Output is correct
10 Correct 188 ms 8580 KB Output is correct
11 Correct 143 ms 8580 KB Output is correct
12 Correct 142 ms 8908 KB Output is correct
13 Correct 146 ms 8576 KB Output is correct
14 Correct 250 ms 11428 KB Output is correct
15 Correct 1234 ms 46216 KB Output is correct
16 Correct 255 ms 13744 KB Output is correct
17 Correct 1348 ms 49952 KB Output is correct
18 Correct 968 ms 49408 KB Output is correct
19 Correct 1255 ms 59340 KB Output is correct
20 Correct 1165 ms 49892 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4820 KB Output is correct
2 Correct 3 ms 4820 KB Output is correct
3 Correct 121 ms 8056 KB Output is correct
4 Correct 898 ms 52468 KB Output is correct
5 Correct 911 ms 47544 KB Output is correct
6 Correct 1046 ms 46424 KB Output is correct
7 Correct 1148 ms 46164 KB Output is correct
8 Correct 1225 ms 46220 KB Output is correct
9 Correct 786 ms 49860 KB Output is correct
10 Correct 947 ms 51216 KB Output is correct
11 Correct 842 ms 49164 KB Output is correct
12 Correct 1208 ms 68076 KB Output is correct
13 Correct 936 ms 49432 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4820 KB Output is correct
2 Correct 3 ms 4820 KB Output is correct
3 Correct 2 ms 4820 KB Output is correct
4 Correct 3 ms 4820 KB Output is correct
5 Correct 3 ms 4820 KB Output is correct
6 Correct 6 ms 4936 KB Output is correct
7 Correct 24 ms 5452 KB Output is correct
8 Correct 26 ms 5460 KB Output is correct
9 Correct 24 ms 5460 KB Output is correct
10 Correct 26 ms 5408 KB Output is correct
11 Correct 23 ms 5420 KB Output is correct
12 Correct 24 ms 5508 KB Output is correct
13 Correct 25 ms 5456 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4820 KB Output is correct
2 Correct 3 ms 4752 KB Output is correct
3 Correct 3 ms 4820 KB Output is correct
4 Correct 3 ms 4820 KB Output is correct
5 Correct 9 ms 4948 KB Output is correct
6 Correct 799 ms 46356 KB Output is correct
7 Correct 972 ms 46252 KB Output is correct
8 Correct 1018 ms 46160 KB Output is correct
9 Correct 1161 ms 46136 KB Output is correct
10 Correct 697 ms 49004 KB Output is correct
11 Correct 911 ms 48976 KB Output is correct
12 Correct 835 ms 54444 KB Output is correct
13 Correct 925 ms 49816 KB Output is correct
14 Correct 918 ms 48692 KB Output is correct
15 Correct 1041 ms 48756 KB Output is correct
16 Correct 834 ms 51048 KB Output is correct
17 Correct 720 ms 48932 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4820 KB Output is correct
2 Correct 3 ms 4820 KB Output is correct
3 Correct 3 ms 4820 KB Output is correct
4 Correct 3 ms 4820 KB Output is correct
5 Correct 3 ms 4820 KB Output is correct
6 Correct 100 ms 7604 KB Output is correct
7 Correct 247 ms 12428 KB Output is correct
8 Correct 1067 ms 56036 KB Output is correct
9 Correct 1048 ms 55940 KB Output is correct
10 Correct 968 ms 55804 KB Output is correct
11 Correct 1051 ms 54664 KB Output is correct
12 Correct 1031 ms 55040 KB Output is correct
13 Correct 889 ms 46128 KB Output is correct
14 Correct 1158 ms 64948 KB Output is correct
15 Correct 3 ms 4820 KB Output is correct
16 Correct 3 ms 4804 KB Output is correct
17 Correct 4 ms 4820 KB Output is correct
18 Correct 3 ms 4820 KB Output is correct
19 Correct 3 ms 4820 KB Output is correct
20 Correct 9 ms 5072 KB Output is correct
21 Correct 151 ms 8680 KB Output is correct
22 Correct 5 ms 4948 KB Output is correct
23 Correct 9 ms 5124 KB Output is correct
24 Correct 188 ms 8580 KB Output is correct
25 Correct 143 ms 8580 KB Output is correct
26 Correct 142 ms 8908 KB Output is correct
27 Correct 146 ms 8576 KB Output is correct
28 Correct 250 ms 11428 KB Output is correct
29 Correct 1234 ms 46216 KB Output is correct
30 Correct 255 ms 13744 KB Output is correct
31 Correct 1348 ms 49952 KB Output is correct
32 Correct 968 ms 49408 KB Output is correct
33 Correct 1255 ms 59340 KB Output is correct
34 Correct 1165 ms 49892 KB Output is correct
35 Correct 2 ms 4820 KB Output is correct
36 Correct 3 ms 4820 KB Output is correct
37 Correct 121 ms 8056 KB Output is correct
38 Correct 898 ms 52468 KB Output is correct
39 Correct 911 ms 47544 KB Output is correct
40 Correct 1046 ms 46424 KB Output is correct
41 Correct 1148 ms 46164 KB Output is correct
42 Correct 1225 ms 46220 KB Output is correct
43 Correct 786 ms 49860 KB Output is correct
44 Correct 947 ms 51216 KB Output is correct
45 Correct 842 ms 49164 KB Output is correct
46 Correct 1208 ms 68076 KB Output is correct
47 Correct 936 ms 49432 KB Output is correct
48 Correct 3 ms 4820 KB Output is correct
49 Correct 3 ms 4820 KB Output is correct
50 Correct 2 ms 4820 KB Output is correct
51 Correct 3 ms 4820 KB Output is correct
52 Correct 3 ms 4820 KB Output is correct
53 Correct 6 ms 4936 KB Output is correct
54 Correct 24 ms 5452 KB Output is correct
55 Correct 26 ms 5460 KB Output is correct
56 Correct 24 ms 5460 KB Output is correct
57 Correct 26 ms 5408 KB Output is correct
58 Correct 23 ms 5420 KB Output is correct
59 Correct 24 ms 5508 KB Output is correct
60 Correct 25 ms 5456 KB Output is correct
61 Correct 133 ms 9768 KB Output is correct
62 Correct 220 ms 13812 KB Output is correct
63 Correct 986 ms 51400 KB Output is correct
64 Correct 837 ms 49528 KB Output is correct
65 Correct 962 ms 49452 KB Output is correct
66 Correct 1123 ms 49664 KB Output is correct
67 Correct 1208 ms 49832 KB Output is correct
68 Correct 839 ms 49836 KB Output is correct
69 Correct 990 ms 49840 KB Output is correct
70 Correct 924 ms 55408 KB Output is correct
71 Correct 914 ms 50584 KB Output is correct
72 Correct 1051 ms 49600 KB Output is correct
73 Correct 1178 ms 49720 KB Output is correct
74 Correct 907 ms 50812 KB Output is correct
75 Correct 895 ms 49892 KB Output is correct