oj.uz

Submission #335194

# Submission time Handle Problem Language Result Execution time Memory
335194 2020-12-11T12:20:31 Z rocks03 Comparing Plants (IOI20_plants) C++14
55 / 100
 537 ms 17196 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<vector<bool>> vis[2];

void bfs(int s){
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(auto u : g[v]){
            if(vis[0][s][u] == false){
                vis[0][s][u] = true;
                q.push(u);
            }
        }
    }
    q.push(s);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(auto u : g2[v]){
            if(vis[1][s][u] == false){
                vis[1][s][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();
    if(N <= 300){
        g.resize(N);
        g2.resize(N);
        vis[0].resize(N);
        vis[1].resize(N);
        for(int i = 0; i < N; i++){
            vis[0][i].resize(N, false);
            vis[1][i].resize(N, false);
            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);
                }
            }
        }
        for(int i = 0; i < N; i++){
            bfs(i);
        }
    }
}

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

/*

static int n, k, q;
static std::vector<int> r;
static std:: vector<int> x;
static std:: vector<int> y;
static std:: vector<int> answer;
int main() {
	assert(scanf("%d%d%d", &n, &k, &q) == 3);
	r.resize(n);
	answer.resize(q);
	for (int i = 0; i < n; i++) {
		int value;
		assert(scanf("%d", &value) == 1);
		r[i] = value;
	}
	x.resize(q);
	y.resize(q);
	for (int i = 0; i < q; i++) {
		assert(scanf("%d%d", &x[i], &y[i]) == 2);
	}
	fclose(stdin);

	init(k, r);
	for (int i = 0; i < q; i++) {
		answer[i] = compare_plants(x[i], y[i]);
	}

	for (int i = 0; i < q; i++) {
		printf("%d\n", answer[i]);
	}

	fclose(stdout);

	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 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 63 ms 4204 KB Output is correct
7 Incorrect 89 ms 6268 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 2 ms 492 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Correct 76 ms 5356 KB Output is correct
8 Correct 4 ms 620 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 75 ms 5356 KB Output is correct
11 Correct 71 ms 5228 KB Output is correct
12 Correct 70 ms 5484 KB Output is correct
13 Correct 76 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 2 ms 492 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Correct 76 ms 5356 KB Output is correct
8 Correct 4 ms 620 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 75 ms 5356 KB Output is correct
11 Correct 71 ms 5228 KB Output is correct
12 Correct 70 ms 5484 KB Output is correct
13 Correct 76 ms 5356 KB Output is correct
14 Correct 98 ms 6380 KB Output is correct
15 Correct 496 ms 15856 KB Output is correct
16 Correct 100 ms 6320 KB Output is correct
17 Correct 509 ms 15980 KB Output is correct
18 Correct 366 ms 15468 KB Output is correct
19 Correct 346 ms 15980 KB Output is correct
20 Correct 537 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 69 ms 4972 KB Output is correct
4 Correct 315 ms 17196 KB Output is correct
5 Correct 346 ms 15468 KB Output is correct
6 Correct 414 ms 15468 KB Output is correct
7 Correct 466 ms 15724 KB Output is correct
8 Correct 504 ms 15852 KB Output is correct
9 Correct 321 ms 15340 KB Output is correct
10 Correct 312 ms 15084 KB Output is correct
11 Correct 288 ms 15084 KB Output is correct
12 Correct 305 ms 15340 KB Output is correct
13 Correct 352 ms 15212 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 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 3 ms 620 KB Output is correct
7 Correct 17 ms 1388 KB Output is correct
8 Correct 31 ms 1736 KB Output is correct
9 Correct 18 ms 1388 KB Output is correct
10 Correct 31 ms 1772 KB Output is correct
11 Correct 17 ms 1388 KB Output is correct
12 Correct 19 ms 1388 KB Output is correct
13 Correct 57 ms 2668 KB Output is correct

Subtask #6
0 / 15.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 Incorrect 2 ms 364 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 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 63 ms 4204 KB Output is correct
7 Incorrect 89 ms 6268 KB Output isn't correct
8 Halted 0 ms 0 KB -