oj.uz

Submission #335281

# Submission time Handle Problem Language Result Execution time Memory
335281 2020-12-11T19:36:26 Z rocks03 Comparing Plants (IOI20_plants) C++14
70 / 100
 1643 ms 100584 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[y]){
	        return 1;
	    } else if(vis2[y]){
	        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 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 59 ms 3180 KB Output is correct
7 Incorrect 110 ms 12264 KB Output isn't correct
8 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 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 5 ms 748 KB Output is correct
7 Correct 84 ms 5356 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 5 ms 748 KB Output is correct
10 Correct 84 ms 5356 KB Output is correct
11 Correct 74 ms 5228 KB Output is correct
12 Correct 84 ms 5484 KB Output is correct
13 Correct 83 ms 5356 KB Output is correct

Subtask #3
13.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 Correct 5 ms 748 KB Output is correct
7 Correct 84 ms 5356 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 5 ms 748 KB Output is correct
10 Correct 84 ms 5356 KB Output is correct
11 Correct 74 ms 5228 KB Output is correct
12 Correct 84 ms 5484 KB Output is correct
13 Correct 83 ms 5356 KB Output is correct
14 Correct 168 ms 12392 KB Output is correct
15 Correct 1643 ms 95452 KB Output is correct
16 Correct 172 ms 12392 KB Output is correct
17 Correct 1632 ms 95540 KB Output is correct
18 Correct 870 ms 95452 KB Output is correct
19 Correct 859 ms 95452 KB Output is correct
20 Correct 1526 ms 95452 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 70 ms 3948 KB Output is correct
4 Correct 644 ms 97796 KB Output is correct
5 Correct 791 ms 95580 KB Output is correct
6 Correct 1027 ms 95688 KB Output is correct
7 Correct 1277 ms 95580 KB Output is correct
8 Correct 1587 ms 95456 KB Output is correct
9 Correct 664 ms 95452 KB Output is correct
10 Correct 700 ms 95324 KB Output is correct
11 Correct 521 ms 95452 KB Output is correct
12 Correct 610 ms 95324 KB Output is correct
13 Correct 859 ms 95504 KB Output is correct

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 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 2 ms 492 KB Output is correct
7 Correct 16 ms 1132 KB Output is correct
8 Correct 16 ms 1132 KB Output is correct
9 Correct 15 ms 1132 KB Output is correct
10 Correct 16 ms 1132 KB Output is correct
11 Correct 15 ms 1132 KB Output is correct
12 Correct 16 ms 1132 KB Output is correct
13 Correct 16 ms 1132 KB Output is correct

Subtask #6
15.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 4 ms 748 KB Output is correct
6 Correct 756 ms 97628 KB Output is correct
7 Correct 996 ms 97884 KB Output is correct
8 Correct 1258 ms 98268 KB Output is correct
9 Correct 1616 ms 98356 KB Output is correct
10 Correct 665 ms 97884 KB Output is correct
11 Correct 1188 ms 98324 KB Output is correct
12 Correct 645 ms 100584 KB Output is correct
13 Correct 771 ms 97884 KB Output is correct
14 Correct 1008 ms 98012 KB Output is correct
15 Correct 1258 ms 98080 KB Output is correct
16 Correct 674 ms 97244 KB Output is correct
17 Correct 760 ms 97708 KB Output is correct

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 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 59 ms 3180 KB Output is correct
7 Incorrect 110 ms 12264 KB Output isn't correct
8 Halted 0 ms 0 KB -