oj.uz

Submission #800191

# Submission time Handle Problem Language Result Execution time Memory
800191 2023-08-01T11:33:40 Z becaido Comparing Plants (IOI20_plants) C++17
5 / 100
 93 ms 30620 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "plants.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

#define lpos pos*2
#define rpos pos*2+1

const int INF = 1e9;
const int SIZE = 2e5 + 5;

int n, k;
int a[SIZE], p[SIZE];
vector<int> adj[SIZE];
vector<pair<int, int>> g[SIZE];

set<int> s;
set<pair<int, int>> d;
int dis(int l, int r) {
    return l < r ? r - l : r + n - l;
}
void add(int i) {
    if (s.size() == 0) {
        s.insert(i);
        d.emplace(n, i);
        return;
    }
    auto it = s.lower_bound(i);
    int L = (it == s.begin() ? *s.rbegin() : *prev(it));
    int R = (it == s.end() ? *s.begin() : *it);
    d.erase({dis(L, R), R});
    d.emplace(dis(L, i), i);
    d.emplace(dis(i, R), R);
    s.insert(i);
}
void del(int i) {
    if (s.size() == 1) {
        s.clear();
        d.clear();
        return;
    }
    auto it = s.lower_bound(i);
    int L = (it == s.begin() ? *s.rbegin() : *prev(it));
    int R = (next(it) == s.end() ? *s.begin() : *next(it));
    s.erase(it);
    d.erase({dis(L, i), i});
    d.erase({dis(i, R), R});
    d.emplace(dis(L, R), R);
}

int mn[SIZE * 4], lazy[SIZE * 4];
void push(int pos, int l, int r) {
    mn[pos] += lazy[pos];
    if (l < r) {
        lazy[lpos] += lazy[pos];
        lazy[rpos] += lazy[pos];
    }
    lazy[pos] = 0;
}
void pull(int pos, int l, int r) {
    int mid = (l + r) / 2;
    push(lpos, l, mid);
    push(rpos, mid + 1, r);
    mn[pos] = min(mn[lpos], mn[rpos]);
}
void build(int pos, int l, int r) {
    if (l == r) {
        mn[pos] = k - 1 - a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(lpos, l, mid);
    build(rpos, mid + 1, r);
    mn[pos] = min(mn[lpos], mn[rpos]);
}
void upd(int pos, int l, int r, int L, int R, int x) {
    if (l == L && r == R) {
        lazy[pos] += x;
        return;
    }
    push(pos, L, R);
    int mid = (L + R) / 2;
    if (r <= mid) upd(lpos, l, r, L, mid, x);
    else if (l > mid) upd(rpos, l, r, mid + 1, R, x);
    else {
        upd(lpos, l, mid, L, mid, x);
        upd(rpos, mid + 1, r, mid + 1, R, x);
    }
    pull(pos, L, R);
}
void dfs(int pos, int l, int r) {
    push(pos, l, r);
    if (mn[pos] != 0) return;
    if (l == r) {
        add(l);
        return;
    }
    int mid = (l + r) / 2;
    dfs(lpos, l, mid);
    dfs(rpos, mid + 1, r);
}

void init(int _k, vector<int> r) {
    n = r.size();
    k = _k;
    FOR (i, 0, n - 1) a[i] = r[i], p[i] = -1;
    if (k == 2) {
        FOR (i, 0, n - 1) {
            if (a[i] == 1) adj[i].pb((i + 1) % n);
            else adj[(i + 1) % n].pb(i);
        }
        int sz = 0;
        FOR (i, 0, n - 1) if (adj[i].size() == 2) {
            for (int x : adj[i]) {
                int cnt = 0;
                g[i].pb(sz, cnt++);
                while (adj[x].size()) {
                    g[x].pb(sz, cnt++);
                    x = adj[x][0];
                }
                g[x].pb(sz, cnt++);
                sz++;
            }
        }
        return;
    }
    build(1, 0, n - 1);
    FOR (i, 0, n - 1) {
        dfs(1, 0, n - 1);
        auto [ld, j] = *d.rbegin();
        assert(ld >= k);
        del(j);
        p[j] = i;
        upd(1, j, j, 0, n - 1, INF);
        int l = j - k + 1, r = j - 1;
        if (l < 0) l += n;
        if (r < 0) r += n;
        if (l <= r) upd(1, l, r, 0, n - 1, -1);
        else {
            upd(1, l, n - 1, 0, n - 1, -1);
            upd(1, 0, r, 0, n - 1, -1);
        }
    }
}

int compare_plants(int x, int y) {
    if (k == 2) {
        for (auto [gx, px] : g[x]) for (auto [gy, py] : g[y]) if (gx == gy) {
            return px < py ? -1 : 1;
        }
        return 0;
	}
    return p[x] < p[y] ? -1 : 1;
}

/*
in1
4 3 2
0 1 1 2
0 2
1 2
out1
1
-1

in2
4 2 2
0 1 0 1
0 3
1 3
out2
1
0
*/

#ifdef WAIMAI
int main() {
    int n, k, q;
    vector<int> r;
    vector<int> x;
    vector<int> y;
    vector<int> answer;
	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;
}
#endif

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 8 ms 9716 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 7 ms 9708 KB Output is correct
5 Correct 7 ms 9684 KB Output is correct
6 Correct 45 ms 13416 KB Output is correct
7 Correct 60 ms 16228 KB Output is correct
8 Correct 82 ms 30236 KB Output is correct
9 Correct 84 ms 30492 KB Output is correct
10 Correct 93 ms 30492 KB Output is correct
11 Correct 83 ms 30516 KB Output is correct
12 Correct 80 ms 30556 KB Output is correct
13 Correct 78 ms 30536 KB Output is correct
14 Correct 83 ms 30620 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9708 KB Output is correct
2 Correct 6 ms 9716 KB Output is correct
3 Correct 6 ms 9708 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Runtime error 13 ms 19540 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9708 KB Output is correct
2 Correct 6 ms 9716 KB Output is correct
3 Correct 6 ms 9708 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Runtime error 13 ms 19540 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Runtime error 13 ms 19412 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 7 ms 9712 KB Output is correct
3 Correct 5 ms 9708 KB Output is correct
4 Runtime error 12 ms 19460 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9708 KB Output is correct
3 Correct 6 ms 9712 KB Output is correct
4 Runtime error 13 ms 19472 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 8 ms 9716 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 7 ms 9708 KB Output is correct
5 Correct 7 ms 9684 KB Output is correct
6 Correct 45 ms 13416 KB Output is correct
7 Correct 60 ms 16228 KB Output is correct
8 Correct 82 ms 30236 KB Output is correct
9 Correct 84 ms 30492 KB Output is correct
10 Correct 93 ms 30492 KB Output is correct
11 Correct 83 ms 30516 KB Output is correct
12 Correct 80 ms 30556 KB Output is correct
13 Correct 78 ms 30536 KB Output is correct
14 Correct 83 ms 30620 KB Output is correct
15 Correct 6 ms 9708 KB Output is correct
16 Correct 6 ms 9716 KB Output is correct
17 Correct 6 ms 9708 KB Output is correct
18 Correct 5 ms 9684 KB Output is correct
19 Runtime error 13 ms 19540 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -