oj.uz

Submission #335280

# Submission time Handle Problem Language Result Execution time Memory
335280 2020-12-11T19:35:10 Z rocks03 Comparing Plants (IOI20_plants) C++14
11 / 100
 107 ms 12392 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));
    }
}

class MergeSortTree{
    public:
    int sz;
    vector<vector<pii>> st;
    void combine(int i){
        for(auto x : st[2 * i + 1]){
            st[i].pb(x);
        }
        for(auto x : st[2 * i + 2]){
            st[i].pb(x);
        }
        sort(all(st[i]));
    }
    void build(int i, int l, int r, vector<int>& P){
        if(l == r){
            st[i].pb({P[l], l});
        } else{
            int m = (l + r) / 2;
            build(2 * i + 1, l, m, P);
            build(2 * i + 2, m + 1, r, P);
            combine(i);
        }
    }
    void build(int n, vector<int>& P){
        sz = n;
        st.resize(4 * n);
        build(0, 0, n - 1, P);
    }
    pii best(pii a, pii b){
        if(a.ff > b.ff) return a;
        else return b;
    }
    pii query(int i, int l, int r, int ql, int qr, int k){
        if(ql <= l && r <= qr){
            pii p = {k, -1};
            int pos = upper_bound(all(st[i]), p) - st[i].begin() - 1;
            if(pos < 0 || st[i][pos].ff >= k){
                return {-1, -1};
            }
            return st[i][pos];
        }
        if(qr < l || ql > r){
            return {-1, -1};
        }
        int m = (l + r) / 2;
        pii a = query(2 * i + 1, l, m, ql, qr, k);
        pii b = query(2 * i + 2, m + 1, r, ql, qr, k);
        return best(a, b);
    }
    pii query(int l, int r, int k){
        return query(0, 0, sz - 1, l, r, k);
    }
};
MergeSortTree mt;

pii best(pii a, pii b){
    if(a.ff > b.ff) return a;
    else return b;
}

pii query(int l, int r, int k){
    return mt.query(l, r, k);
}

vector<vector<int>> g, g2;
void build_graph(){
    g.resize(N);
    g2.resize(N);
    mt.build(N, P);
    for(int i = 0; i < N; i++){
        int l, r;
        pii u;
        l = i + 1, r = i + K - 1;
        if(l >= N){
            l %= N, r %= N;
            u = query(l, r, P[i]);
        } else if(r >= N){
            r %= N;
            u = best(query(l, N - 1, P[i]), query(0, r, P[i]));
        } else{
            u = query(l, r, P[i]);
        }
        if(u.ss != -1){
            g[i].pb(u.ss);
            g2[u.ss].pb(i);
        }
        l = i - K + 1, r = i - 1;
        if(r < 0){
            l += N, r += N;
            u = query(l, r, P[i]);
        } else if(l < 0){
            l += N;
            u = best(query(0, r, P[i]), query(l, N - 1, P[i]));
        } else{
            u = query(l, r, P[i]);
        }
        if(u.ss != -1){
            g[i].pb(u.ss);
            g2[u.ss].pb(i);
        }
    }
}

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

vector<bool> vis1, vis2;
void bfs_zero(int s){
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(auto u : g[v]){
            if(!vis1[u]){
                vis1[u] = true;
                q.push(u);
            }
        }
    }
    q.push(s);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(auto u : g2[v]){
            if(!vis2[u]){
                vis2[u] = true;
                q.push(u);
            }
        }
    }
}

void init(int k, vector<int> r){
    N = SZ(r), K = k, R = r;
    P.resize(N);
    build_plants();
    build_graph();
    if(N <= 300){
        vis.resize(N);
        for(int i = 0; i < N; i++){
            bfs(i);
        }
    }
    vis1.resize(N, false);
    vis2.resize(N, false);
    bfs_zero(0);
}

int compare_plants(int x, int y){
	if(N <= 300){
	    if(vis[x][y]){
	        return 1;
	    } else if(vis[y][x]){
	        return -1;
	    } else{
	        return 0;
	    }
	}
	if(x == 0){
	    if(vis1[x]){
	        return 1;
	    } else if(vis2[x]){
	        return -1;
	    } else return 0;
	}
	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 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 59 ms 3116 KB Output is correct
7 Incorrect 107 ms 12392 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
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 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Incorrect 5 ms 748 KB Output isn't correct
7 Halted 0 ms 0 KB -

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 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Incorrect 5 ms 748 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 268 KB Output is correct
3 Correct 1 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 2 ms 492 KB Output is correct
7 Correct 15 ms 1132 KB Output is correct
8 Correct 16 ms 1132 KB Output is correct
9 Correct 22 ms 1132 KB Output is correct
10 Correct 16 ms 1260 KB Output is correct
11 Correct 15 ms 1132 KB Output is correct
12 Correct 15 ms 1132 KB Output is correct
13 Correct 16 ms 1132 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.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 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 59 ms 3116 KB Output is correct
7 Incorrect 107 ms 12392 KB Output isn't correct
8 Halted 0 ms 0 KB -