oj.uz

Submission #680611

# Submission time Handle Problem Language Result Execution time Memory
680611 2023-01-11T10:44:54 Z someone Comparing Plants (IOI20_plants) C++14
30 / 100
 4000 ms 67916 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) {
    while(i < 0)
        i += n;
    while(i >= n)
        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 3 ms 4820 KB Output is correct
2 Correct 3 ms 4820 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 99 ms 8604 KB Output is correct
7 Correct 221 ms 14692 KB Output is correct
8 Correct 1084 ms 58996 KB Output is correct
9 Correct 1004 ms 58804 KB Output is correct
10 Correct 997 ms 58712 KB Output is correct
11 Correct 1125 ms 57688 KB Output is correct
12 Correct 1089 ms 58076 KB Output is correct
13 Correct 937 ms 49048 KB Output is correct
14 Correct 1241 ms 67916 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 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 21 ms 5156 KB Output is correct
7 Correct 1671 ms 10564 KB Output is correct
8 Correct 8 ms 4940 KB Output is correct
9 Correct 20 ms 5160 KB Output is correct
10 Correct 1561 ms 10480 KB Output is correct
11 Correct 160 ms 10472 KB Output is correct
12 Correct 149 ms 10832 KB Output is correct
13 Correct 2318 ms 10484 KB Output is correct

Subtask #3
0 / 13.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 3 ms 4820 KB Output is correct
6 Correct 21 ms 5156 KB Output is correct
7 Correct 1671 ms 10564 KB Output is correct
8 Correct 8 ms 4940 KB Output is correct
9 Correct 20 ms 5160 KB Output is correct
10 Correct 1561 ms 10480 KB Output is correct
11 Correct 160 ms 10472 KB Output is correct
12 Correct 149 ms 10832 KB Output is correct
13 Correct 2318 ms 10484 KB Output is correct
14 Correct 2586 ms 13632 KB Output is correct
15 Execution timed out 4041 ms 47148 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.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 113 ms 9828 KB Output is correct
4 Correct 929 ms 55288 KB Output is correct
5 Correct 990 ms 50736 KB Output is correct
6 Correct 1184 ms 49640 KB Output is correct
7 Correct 1913 ms 49736 KB Output is correct
8 Execution timed out 4033 ms 49532 KB Time limit exceeded
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 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 5 ms 4948 KB Output is correct
7 Correct 19 ms 5780 KB Output is correct
8 Correct 32 ms 5732 KB Output is correct
9 Correct 29 ms 5780 KB Output is correct
10 Correct 44 ms 5824 KB Output is correct
11 Correct 30 ms 5744 KB Output is correct
12 Correct 26 ms 5740 KB Output is correct
13 Correct 81 ms 5716 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 4 ms 4800 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 5076 KB Output is correct
6 Correct 810 ms 48576 KB Output is correct
7 Correct 1045 ms 48548 KB Output is correct
8 Correct 1651 ms 48724 KB Output is correct
9 Execution timed out 4059 ms 47336 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.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 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 99 ms 8604 KB Output is correct
7 Correct 221 ms 14692 KB Output is correct
8 Correct 1084 ms 58996 KB Output is correct
9 Correct 1004 ms 58804 KB Output is correct
10 Correct 997 ms 58712 KB Output is correct
11 Correct 1125 ms 57688 KB Output is correct
12 Correct 1089 ms 58076 KB Output is correct
13 Correct 937 ms 49048 KB Output is correct
14 Correct 1241 ms 67916 KB Output is correct
15 Correct 3 ms 4820 KB Output is correct
16 Correct 3 ms 4820 KB Output is correct
17 Correct 3 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 21 ms 5156 KB Output is correct
21 Correct 1671 ms 10564 KB Output is correct
22 Correct 8 ms 4940 KB Output is correct
23 Correct 20 ms 5160 KB Output is correct
24 Correct 1561 ms 10480 KB Output is correct
25 Correct 160 ms 10472 KB Output is correct
26 Correct 149 ms 10832 KB Output is correct
27 Correct 2318 ms 10484 KB Output is correct
28 Correct 2586 ms 13632 KB Output is correct
29 Execution timed out 4041 ms 47148 KB Time limit exceeded
30 Halted 0 ms 0 KB -