oj.uz

Submission #334971

# Submission time Handle Problem Language Result Execution time Memory
334971 2020-12-10T15:28:57 Z rocks03 Comparing Plants (IOI20_plants) C++14
44 / 100
 529 ms 17132 KB 
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

class SegmentTree{
    public:
    int n;
    vector<int> st, lazy;
    void build(int i, int l, int r, vector<int>& a){
        if(l == r){
            st[i] = a[l];
        } else{
            int m = (l + r) / 2;
            build(2*i+1, l, m, a);
            build(2*i+2, m+1, r, a);
            st[i] = min(st[2*i+1], st[2*i+2]);
        }
    }
    void build(int sz, vector<int>& a){
        n = sz;
        st.resize(4 * n, n+1);
        lazy.resize(4 * n, 0);
        build(0, 0, n - 1, a);
    }
    void push(int i){
        if(lazy[i] != 0){
            lazy[2*i+1] += lazy[i];
            st[2*i+1] += lazy[i];
            lazy[2*i+2] += lazy[i];
            st[2*i+2] += lazy[i];
        }
        lazy[i] = 0;
    }
    int ask(int i, int l, int r, int ql, int qr){
        if(qr < l || ql > r || st[i] != 0){
            return -1;
        }
        if(l == r){
            return l;
        }
        push(i);
        int m = (l + r) / 2;
        int res = -1;
        if(res == -1){
            res = ask(2*i+1, l, m, ql, qr);
        }
        if(res == -1){
            res = ask(2*i+2, m + 1, r, ql, qr);
        }
        st[i] = min(st[2*i+1], st[2*i+2]);
        return res;
    }
    int ask(int l, int r){
        int res = ask(0, 0, n - 1, l, r);
        return res;
    }
    void add(int i, int l, int r, int ql, int qr){
        if(qr < l || ql > r){
            return;
        }
        if(ql <= l && r <= qr){
            st[i]--;
            lazy[i]--;
            return;
        }
        push(i);
        int m = (l + r) / 2;
        add(2*i+1, l, m, ql, qr);
        add(2*i+2, m+1, r, ql, qr);
        st[i] = min(st[2*i+1], st[2*i+2]);
    }
    void add(int l, int r){
        add(0, 0, n - 1, l, r);
    }
    void pop(int i, int l, int r, int p, int k){
        if(l == r){
            st[i] = k;
            return;
        }
        push(i);
        int m = (l + r) / 2;
        if(p <= m)
            pop(2*i+1, l, m, p, k);
        else
            pop(2*i+2, m+1, r, p, k);
        st[i] = min(st[2*i+1], st[2*i+2]);
    }
    void pop(int i, int k){
        pop(0, 0, n-1, i, k);
    }
};

int N, K;
vector<int> P, R;
SegmentTree st;

int ask(int l, int r){
    return st.ask(l, r);
    /*
    for(int i = l; i <= r; i++){
        if(R[i] == 0)
            return i;
    }
    return -1;
    */
}

void pop(int i){
    st.pop(i, N);
}

void add(int l, int r){
    st.add(l, r);
    /*
    for(int i = l; i <= r; i++){
        R[i]--;
    }
    */
}

void f(int& n, int pos){
    int pos2;
    while(true){
        pos2 = -1;
        int l = pos - K + 1, r = pos - 1;
        if(r < 0){
            l += N, r += N;
            pos2 = ask(l, r);
        } else if(l < 0){
            l += N;
            pos2 = max(ask(0, r), ask(l, N-1));
        } else{
            pos2 = ask(l, r);
        }
        if(pos2 == -1){
            break;
        }
        f(n, pos2);
    }
    P[pos] = n--;
    pop(pos);
    int l = pos - K + 1, r = pos - 1;
    if(r < 0){
        l += N, r += N;
        add(l, r);
    } else if(l < 0){
        l += N;
        add(0, r);
        add(l, N-1);
    } else{
        add(l, r);
    }
}

void genera(){
    int n = N;
    while(n >= 0){
        int pos = ask(0, N-1);
        f(n, pos);
    }
}

void init(int k, vector<int> r){
    N = SZ(r), K = k, R = r;
    P.resize(N);
    st.build(N, r);
    genera();
}

int compare_plants(int x, int y){
	if(P[x] > P[y])
	    return 1;
	if(P[x] < P[y])
	    return -1;
    return 0;
}

Compilation message

plants.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization("O3")
      | 
plants.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization("unroll-loops")
      |

Subtask #1
0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Correct 76 ms 5356 KB Output is correct
8 Correct 2 ms 496 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 70 ms 5356 KB Output is correct
11 Correct 68 ms 5228 KB Output is correct
12 Correct 71 ms 5356 KB Output is correct
13 Correct 71 ms 5260 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Correct 76 ms 5356 KB Output is correct
8 Correct 2 ms 496 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 70 ms 5356 KB Output is correct
11 Correct 68 ms 5228 KB Output is correct
12 Correct 71 ms 5356 KB Output is correct
13 Correct 71 ms 5260 KB Output is correct
14 Correct 95 ms 6400 KB Output is correct
15 Correct 488 ms 15804 KB Output is correct
16 Correct 95 ms 6400 KB Output is correct
17 Correct 488 ms 15980 KB Output is correct
18 Correct 365 ms 15676 KB Output is correct
19 Correct 337 ms 15980 KB Output is correct
20 Correct 529 ms 15980 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 65 ms 4972 KB Output is correct
4 Correct 309 ms 17132 KB Output is correct
5 Correct 331 ms 15468 KB Output is correct
6 Correct 414 ms 15468 KB Output is correct
7 Correct 455 ms 15636 KB Output is correct
8 Correct 494 ms 15852 KB Output is correct
9 Correct 311 ms 15340 KB Output is correct
10 Correct 308 ms 15084 KB Output is correct
11 Correct 281 ms 15084 KB Output is correct
12 Correct 300 ms 15340 KB Output is correct
13 Correct 345 ms 15340 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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