oj.uz

Submission #680616

# Submission time Handle Problem Language Result Execution time Memory
680616 2023-01-11T10:54:36 Z someone Comparing Plants (IOI20_plants) C++14
30 / 100
 1386 ms 61252 KB 
#include <bits/stdc++.h>
#define deb first
#define fin second
#define mid ((deb + fin) >> 1)
using namespace std;
 
const int T = 18, L = 1 << T, M = 2 * L, N = 2 * M, INF = 1e9 + 42;
 
int n, k, vals[L], corr[L], gauche[T][L], droite[T][L];

set<int> pos0, posMin;
int imin[M], nbInf[M], lazy[M], 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 = L; i < M; i++)
        imin[i] = i - L;
    for(int i = L-1; i > 0; i--)
        imin[i] = imin[i*2];
    
    for(int i = 0; i < n; i++) {
        r[i] = k - r[i];
        update(1, 0, L, 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, L, 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, L, id - k, id, -1);
        } else {
            update(1, 0, L, 0, id, -1);
            update(1, 0, L, n + id - k, n, -1);
        }
        auto pii = update(1, 0, L, 0, n, 0);
        while(pii.first == 0) {
            update(1, 0, L, pii.second, pii.second+1, INF);
            set0(pii.second, 1);
            set0(pii.second + n, 1);
            pii = update(1, 0, L, 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];
        }
    }
}
 
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 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 111 ms 5496 KB Output is correct
7 Correct 231 ms 10172 KB Output is correct
8 Correct 1016 ms 52396 KB Output is correct
9 Correct 1050 ms 52184 KB Output is correct
10 Correct 946 ms 52136 KB Output is correct
11 Correct 1070 ms 50992 KB Output is correct
12 Correct 1068 ms 51356 KB Output is correct
13 Correct 871 ms 42492 KB Output is correct
14 Correct 1240 ms 61252 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2644 KB Output is correct
6 Correct 7 ms 2900 KB Output is correct
7 Correct 159 ms 6392 KB Output is correct
8 Correct 4 ms 2772 KB Output is correct
9 Correct 9 ms 2900 KB Output is correct
10 Correct 198 ms 6384 KB Output is correct
11 Correct 133 ms 6280 KB Output is correct
12 Correct 140 ms 6744 KB Output is correct
13 Correct 150 ms 6476 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2644 KB Output is correct
6 Correct 7 ms 2900 KB Output is correct
7 Correct 159 ms 6392 KB Output is correct
8 Correct 4 ms 2772 KB Output is correct
9 Correct 9 ms 2900 KB Output is correct
10 Correct 198 ms 6384 KB Output is correct
11 Correct 133 ms 6280 KB Output is correct
12 Correct 140 ms 6744 KB Output is correct
13 Correct 150 ms 6476 KB Output is correct
14 Correct 259 ms 9092 KB Output is correct
15 Incorrect 1386 ms 42444 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2664 KB Output is correct
3 Correct 138 ms 5884 KB Output is correct
4 Correct 958 ms 48804 KB Output is correct
5 Correct 965 ms 43836 KB Output is correct
6 Correct 1083 ms 42604 KB Output is correct
7 Correct 1122 ms 42416 KB Output is correct
8 Incorrect 1239 ms 42492 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 5 ms 2900 KB Output is correct
7 Correct 21 ms 3284 KB Output is correct
8 Correct 26 ms 3256 KB Output is correct
9 Correct 22 ms 3284 KB Output is correct
10 Correct 23 ms 3260 KB Output is correct
11 Correct 21 ms 3264 KB Output is correct
12 Correct 31 ms 3288 KB Output is correct
13 Correct 24 ms 3252 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 5 ms 2856 KB Output is correct
6 Correct 737 ms 42632 KB Output is correct
7 Correct 977 ms 42452 KB Output is correct
8 Correct 960 ms 42408 KB Output is correct
9 Incorrect 1099 ms 42444 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 111 ms 5496 KB Output is correct
7 Correct 231 ms 10172 KB Output is correct
8 Correct 1016 ms 52396 KB Output is correct
9 Correct 1050 ms 52184 KB Output is correct
10 Correct 946 ms 52136 KB Output is correct
11 Correct 1070 ms 50992 KB Output is correct
12 Correct 1068 ms 51356 KB Output is correct
13 Correct 871 ms 42492 KB Output is correct
14 Correct 1240 ms 61252 KB Output is correct
15 Correct 1 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 3 ms 2644 KB Output is correct
20 Correct 7 ms 2900 KB Output is correct
21 Correct 159 ms 6392 KB Output is correct
22 Correct 4 ms 2772 KB Output is correct
23 Correct 9 ms 2900 KB Output is correct
24 Correct 198 ms 6384 KB Output is correct
25 Correct 133 ms 6280 KB Output is correct
26 Correct 140 ms 6744 KB Output is correct
27 Correct 150 ms 6476 KB Output is correct
28 Correct 259 ms 9092 KB Output is correct
29 Incorrect 1386 ms 42444 KB Output isn't correct
30 Halted 0 ms 0 KB -