oj.uz

Submission #800193

# Submission time Handle Problem Language Result Execution time Memory
800193 2023-08-01T11:36:33 Z becaido Comparing Plants (IOI20_plants) C++17
5 / 100
 96 ms 27704 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);
        if (!d.size()) return;
        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 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 46 ms 12436 KB Output is correct
7 Correct 52 ms 14004 KB Output is correct
8 Correct 86 ms 27308 KB Output is correct
9 Correct 83 ms 27560 KB Output is correct
10 Correct 84 ms 27584 KB Output is correct
11 Correct 91 ms 27684 KB Output is correct
12 Correct 96 ms 27664 KB Output is correct
13 Correct 82 ms 27596 KB Output is correct
14 Correct 82 ms 27704 KB Output is correct

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9628 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Incorrect 5 ms 9684 KB Output isn't correct
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 15 ms 19460 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 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Incorrect 6 ms 9684 KB Output isn't correct
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 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Runtime error 12 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 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 46 ms 12436 KB Output is correct
7 Correct 52 ms 14004 KB Output is correct
8 Correct 86 ms 27308 KB Output is correct
9 Correct 83 ms 27560 KB Output is correct
10 Correct 84 ms 27584 KB Output is correct
11 Correct 91 ms 27684 KB Output is correct
12 Correct 96 ms 27664 KB Output is correct
13 Correct 82 ms 27596 KB Output is correct
14 Correct 82 ms 27704 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9628 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 5 ms 9684 KB Output is correct
19 Incorrect 5 ms 9684 KB Output isn't correct
20 Halted 0 ms 0 KB -