oj.uz

Submission #680619

# Submission time Handle Problem Language Result Execution time Memory
680619 2023-01-11T10:59:24 Z someone Comparing Plants (IOI20_plants) C++14
5 / 100
 1360 ms 62788 KB 
#include <bits/stdc++.h>
#define deb first
#define fin second
#define mid ((deb + fin) >> 1)
using namespace std;
 
const int T = 19, L = 1 << (T-1), 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) - n);
        it--;
        if(i > (*it) + k && n <= i && i < 2*n)
            posMin.insert(i - n);
        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 - n);
    }
}
 
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 = (*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 1 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 88 ms 5460 KB Output is correct
7 Correct 249 ms 10420 KB Output is correct
8 Correct 1012 ms 53852 KB Output is correct
9 Correct 1056 ms 53876 KB Output is correct
10 Correct 961 ms 53636 KB Output is correct
11 Correct 1049 ms 52556 KB Output is correct
12 Correct 1048 ms 52904 KB Output is correct
13 Correct 1082 ms 53420 KB Output is correct
14 Correct 1360 ms 62788 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.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 2712 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 5 ms 2772 KB Output is correct
7 Correct 23 ms 3276 KB Output is correct
8 Incorrect 26 ms 3272 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2664 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 Incorrect 6 ms 2900 KB Output isn't correct
6 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 1 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 88 ms 5460 KB Output is correct
7 Correct 249 ms 10420 KB Output is correct
8 Correct 1012 ms 53852 KB Output is correct
9 Correct 1056 ms 53876 KB Output is correct
10 Correct 961 ms 53636 KB Output is correct
11 Correct 1049 ms 52556 KB Output is correct
12 Correct 1048 ms 52904 KB Output is correct
13 Correct 1082 ms 53420 KB Output is correct
14 Correct 1360 ms 62788 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 3 ms 2644 KB Output is correct
17 Incorrect 2 ms 2644 KB Output isn't correct
18 Halted 0 ms 0 KB -