oj.uz

Submission #335032

# Submission time Handle Problem Language Result Execution time Memory
335032 2020-12-10T21:52:11 Z rocks03 Comparing Plants (IOI20_plants) C++14
14 / 100
 4000 ms 1034032 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);
    }
}

vector<vector<int>> g, g2;
vector<bool> vis[2];

void bfs(int s){
    vis[0].resize(N);
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(auto u : g[v]){
            if(vis[0][u] == false){
                vis[0][u] = true;
                q.push(u);
            }
        }
    }
    vis[1].resize(N);
    q.push(s);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(auto u : g2[v]){
            if(vis[1][u] == false){
                vis[1][u] = true;
                q.push(u);
            }
        }
    }
}

void init(int k, vector<int> r){
    N = SZ(r), K = k, R = r;
    P.resize(N);
    st.build(N, r);
    genera();
    g.resize(N);
    g2.resize(N);
    for(int i = 0; i < N; i++){
        for(int j = i + 1; j <= i + K - 1; j++){
            if(P[i] > P[j % N]){
                g[i].pb(j % N);
                g2[j % N].pb(i);
            } else{
                g[j % N].pb(i);
                g2[i].pb(j % N);
            }
        }
    }
    bfs(0);
}

int compare_plants(int x, int y){
	if(x == 0){
	    if(vis[0][y])
	        return 1;
	    if(vis[1][y])
	        return -1;
	    return 0;
	}
	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 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 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 376 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 34 ms 10604 KB Output is correct
7 Correct 994 ms 213484 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 31 ms 10624 KB Output is correct
10 Correct 958 ms 213612 KB Output is correct
11 Correct 551 ms 141932 KB Output is correct
12 Correct 552 ms 142316 KB Output is correct
13 Correct 1203 ms 265324 KB Output is correct

Subtask #3
0 / 13.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 1 ms 376 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 34 ms 10604 KB Output is correct
7 Correct 994 ms 213484 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 31 ms 10624 KB Output is correct
10 Correct 958 ms 213612 KB Output is correct
11 Correct 551 ms 141932 KB Output is correct
12 Correct 552 ms 142316 KB Output is correct
13 Correct 1203 ms 265324 KB Output is correct
14 Execution timed out 4093 ms 689524 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.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 Correct 67 ms 5356 KB Output is correct
4 Correct 435 ms 50028 KB Output is correct
5 Correct 1146 ms 258156 KB Output is correct
6 Execution timed out 4114 ms 998168 KB Time limit exceeded
7 Halted 0 ms 0 KB -

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 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 6 ms 1644 KB Output is correct
6 Correct 1117 ms 257084 KB Output is correct
7 Execution timed out 4148 ms 1034032 KB Time limit exceeded
8 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 -