oj.uz

Submission #680977

# Submission time Handle Problem Language Result Execution time Memory
680977 2023-01-12T07:30:22 Z someone Comparing Plants (IOI20_plants) C++14
30 / 100
 1175 ms 67824 KB 
#include <bits/stdc++.h>
#include "plants.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];
        }
    }
}
 
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 4796 KB Output is correct
4 Correct 3 ms 4820 KB Output is correct
5 Correct 2 ms 4820 KB Output is correct
6 Correct 83 ms 8680 KB Output is correct
7 Correct 229 ms 14668 KB Output is correct
8 Correct 990 ms 58904 KB Output is correct
9 Correct 988 ms 58880 KB Output is correct
10 Correct 944 ms 58840 KB Output is correct
11 Correct 1004 ms 57676 KB Output is correct
12 Correct 1030 ms 57996 KB Output is correct
13 Correct 834 ms 49164 KB Output is correct
14 Correct 1136 ms 67824 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4820 KB Output is correct
2 Correct 2 ms 4820 KB Output is correct
3 Correct 3 ms 4820 KB Output is correct
4 Correct 2 ms 4820 KB Output is correct
5 Correct 3 ms 4820 KB Output is correct
6 Correct 8 ms 5112 KB Output is correct
7 Correct 152 ms 10472 KB Output is correct
8 Correct 5 ms 4948 KB Output is correct
9 Correct 9 ms 5076 KB Output is correct
10 Correct 155 ms 10472 KB Output is correct
11 Correct 143 ms 10444 KB Output is correct
12 Correct 141 ms 10832 KB Output is correct
13 Correct 146 ms 10572 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4820 KB Output is correct
2 Correct 2 ms 4820 KB Output is correct
3 Correct 3 ms 4820 KB Output is correct
4 Correct 2 ms 4820 KB Output is correct
5 Correct 3 ms 4820 KB Output is correct
6 Correct 8 ms 5112 KB Output is correct
7 Correct 152 ms 10472 KB Output is correct
8 Correct 5 ms 4948 KB Output is correct
9 Correct 9 ms 5076 KB Output is correct
10 Correct 155 ms 10472 KB Output is correct
11 Correct 143 ms 10444 KB Output is correct
12 Correct 141 ms 10832 KB Output is correct
13 Correct 146 ms 10572 KB Output is correct
14 Correct 232 ms 13624 KB Output is correct
15 Incorrect 1175 ms 49924 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 4820 KB Output is correct
2 Correct 2 ms 4820 KB Output is correct
3 Correct 117 ms 9832 KB Output is correct
4 Correct 869 ms 55332 KB Output is correct
5 Correct 884 ms 50668 KB Output is correct
6 Correct 1008 ms 49608 KB Output is correct
7 Correct 1098 ms 49744 KB Output is correct
8 Incorrect 1159 ms 49920 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 3 ms 4820 KB Output is correct
2 Correct 2 ms 4820 KB Output is correct
3 Correct 2 ms 4820 KB Output is correct
4 Correct 3 ms 4792 KB Output is correct
5 Correct 4 ms 4796 KB Output is correct
6 Correct 5 ms 4948 KB Output is correct
7 Correct 22 ms 5716 KB Output is correct
8 Correct 24 ms 5816 KB Output is correct
9 Correct 23 ms 5744 KB Output is correct
10 Correct 24 ms 5836 KB Output is correct
11 Correct 22 ms 5732 KB Output is correct
12 Correct 23 ms 5768 KB Output is correct
13 Correct 24 ms 5836 KB Output is correct

Subtask #6
0 / 15.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 3 ms 4820 KB Output is correct
4 Correct 3 ms 4820 KB Output is correct
5 Correct 6 ms 5076 KB Output is correct
6 Correct 684 ms 48656 KB Output is correct
7 Correct 906 ms 48564 KB Output is correct
8 Correct 942 ms 48968 KB Output is correct
9 Incorrect 1049 ms 49072 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
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 4796 KB Output is correct
4 Correct 3 ms 4820 KB Output is correct
5 Correct 2 ms 4820 KB Output is correct
6 Correct 83 ms 8680 KB Output is correct
7 Correct 229 ms 14668 KB Output is correct
8 Correct 990 ms 58904 KB Output is correct
9 Correct 988 ms 58880 KB Output is correct
10 Correct 944 ms 58840 KB Output is correct
11 Correct 1004 ms 57676 KB Output is correct
12 Correct 1030 ms 57996 KB Output is correct
13 Correct 834 ms 49164 KB Output is correct
14 Correct 1136 ms 67824 KB Output is correct
15 Correct 2 ms 4820 KB Output is correct
16 Correct 2 ms 4820 KB Output is correct
17 Correct 3 ms 4820 KB Output is correct
18 Correct 2 ms 4820 KB Output is correct
19 Correct 3 ms 4820 KB Output is correct
20 Correct 8 ms 5112 KB Output is correct
21 Correct 152 ms 10472 KB Output is correct
22 Correct 5 ms 4948 KB Output is correct
23 Correct 9 ms 5076 KB Output is correct
24 Correct 155 ms 10472 KB Output is correct
25 Correct 143 ms 10444 KB Output is correct
26 Correct 141 ms 10832 KB Output is correct
27 Correct 146 ms 10572 KB Output is correct
28 Correct 232 ms 13624 KB Output is correct
29 Incorrect 1175 ms 49924 KB Output isn't correct
30 Halted 0 ms 0 KB -