oj.uz

Submission #335274

# Submission time Handle Problem Language Result Execution time Memory
335274 2020-12-11T19:20:08 Z rocks03 Comparing Plants (IOI20_plants) C++14
44 / 100
 464 ms 17664 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 sz;
    vector<int> st, lazy;
    void push(int i){
        if(lazy[i]){
            st[2 * i + 1] += lazy[i];
            lazy[2 * i + 1] += lazy[i];
            st[2 * i + 2] += lazy[i];
            lazy[2 * i + 2] += lazy[i];
        }
        lazy[i] = 0;
    }
    void merge(int i){
        st[i] = min(st[2 * i + 1], st[2 * i + 2]);
    }
    void build(int i, int l, int r, vector<int>& R){
        if(l == r){
            st[i] = R[l];
        } else{
            int m = (l + r) / 2;
            build(2*i+1, l, m, R);
            build(2*i+2, m+1, r, R);
            merge(i);
        }
    }
    void build(int n, vector<int>& R){
        sz = n;
        st.resize(4 * sz);
        lazy.resize(4 * sz);
        build(0, 0, n - 1, R);
    }
    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 ans = ask(2 * i + 1, l, m, ql, qr);
        if(ans == -1)
            ans = ask(2 * i + 2, m + 1, r, ql, qr);
        return ans;
    }
    void add(int i, int l, int r, int ql, int qr, int k){
        if(ql <= l && r <= qr){
            st[i] += k;
            lazy[i] += k;
            return;
        }
        if(qr < l || ql > r){
            return;
        }
        push(i);
        int m = (l + r) / 2;
        add(2 * i + 1, l, m, ql, qr, k);
        add(2 * i + 2, m + 1, r, ql, qr, k);
        merge(i);
    }
};

SegmentTree st;
int N, K;
vector<int> R, P;
int ask(int l, int r){
    return st.ask(0, 0, N - 1, l, r);
}
void add(int l, int r, int k){
    st.add(0, 0, N - 1, l, r, k);
}

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

void build_plants(){
    st.build(N, R);
    int n = N;
    while(n){
        f(n, ask(0, N-1));
    }
}

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

int compare_plants(int x, int y){
	if(P[x] > P[y]){
	    return 1;
	} else if(P[x] < P[y]){
	    return -1;
	} else{
	    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 384 KB Output is correct
2 Correct 1 ms 364 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 256 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 384 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 3436 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 3 ms 492 KB Output is correct
10 Correct 73 ms 5296 KB Output is correct
11 Correct 67 ms 5376 KB Output is correct
12 Correct 67 ms 5356 KB Output is correct
13 Correct 71 ms 5356 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 384 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 3436 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 3 ms 492 KB Output is correct
10 Correct 73 ms 5296 KB Output is correct
11 Correct 67 ms 5376 KB Output is correct
12 Correct 67 ms 5356 KB Output is correct
13 Correct 71 ms 5356 KB Output is correct
14 Correct 96 ms 6508 KB Output is correct
15 Correct 457 ms 15980 KB Output is correct
16 Correct 93 ms 6380 KB Output is correct
17 Correct 464 ms 15980 KB Output is correct
18 Correct 324 ms 15340 KB Output is correct
19 Correct 302 ms 15980 KB Output is correct
20 Correct 459 ms 15852 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 66 ms 3308 KB Output is correct
4 Correct 267 ms 17664 KB Output is correct
5 Correct 293 ms 15468 KB Output is correct
6 Correct 377 ms 15340 KB Output is correct
7 Correct 415 ms 15724 KB Output is correct
8 Correct 451 ms 15852 KB Output is correct
9 Correct 273 ms 15416 KB Output is correct
10 Correct 271 ms 15212 KB Output is correct
11 Correct 239 ms 14956 KB Output is correct
12 Correct 263 ms 15212 KB Output is correct
13 Correct 301 ms 15212 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 0 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 0 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 384 KB Output is correct
2 Correct 1 ms 364 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 -