oj.uz

Submission #800236

# Submission time Handle Problem Language Result Execution time Memory
800236 2023-08-01T12:33:36 Z becaido Comparing Plants (IOI20_plants) C++17
25 / 100
 856 ms 2097152 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);
        mn[pos] += INF;
        return;
    }
    int mid = (l + r) / 2;
    dfs(lpos, l, mid);
    dfs(rpos, mid + 1, r);
    pull(pos, l, r);
}

int mnp[SIZE * 4];
bool vs[SIZE];
int cmp(int l, int r) {
    int mnl = p[l], mnr = p[r];
    return (!vs[l] && (vs[r] || mnl < mnr)) ? l : r;
}
void build2(int pos, int l, int r) {
    if (l == r) {
        mnp[pos] = l;
        return;
    }
    int mid = (l + r) / 2;
    build2(lpos, l, mid);
    build2(rpos, mid + 1, r);
    mnp[pos] = cmp(mnp[lpos], mnp[rpos]);
}
void upd2(int pos, int l, int r, int p) {
    if (l == r) {
        vs[l] = 1;
        return;
    }
    int mid = (l + r) / 2;
    if (p <= mid) upd2(lpos, l, mid, p);
    else upd2(rpos, mid + 1, r, p);
    mnp[pos] = cmp(mnp[lpos], mnp[rpos]);
}
int que(int pos, int l, int r, int L, int R) {
    if (l == L && r == R) return mnp[pos];
    int mid = (L + R) / 2;
    if (r <= mid) return que(lpos, l, r, L, mid);
    if (l > mid) return que(rpos, l, r, mid + 1, R);
    return cmp(que(lpos, l, mid, L, mid), que(rpos, mid + 1, r, mid + 1, R));
}
int que(int l, int r) {
    int re = l <= r ? que(1, l, r, 0, n - 1) : cmp(que(1, l, n - 1, 0, n - 1), que(1, 0, r, 0, n - 1));
    if (vs[re]) re = -1;
    //debug(l, r, re);
    return re;
}

const int KSIZ = 2e5;
int id[SIZE], deg[SIZE];
vector<bitset<KSIZ>> is;
void init(int _k, vector<int> r) {
    n = r.size();
    k = _k;
    is.resize(n);
    FOR (i, 0, n - 1) a[i] = r[i], p[i] = -1;
    build(1, 0, n - 1);
    int sz = n;
    FOR (i, 0, n - 1) {
        if (sz == 0) break;
        dfs(1, 0, n - 1);
        vector<int> all;
        assert(d.size() > 0);
        for (auto it = d.rbegin(); it != d.rend(); it++) {
            auto [ld, j] = *it;
            if (ld < k) break;
            all.pb(j);
        }
        assert(all.size() > 0);
        sz -= all.size();
        for (int j : all) {
            del(j);
            p[j] = i;
            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);
            }
        }
    }
    iota(id, id + n, 0);
    sort(id, id + n, [](int l, int r) {
        return p[l] < p[r];
    });
    build2(1, 0, n - 1);
    FOR (i, 0, n - 1) {
        int cur = id[i];
        //debug(cur);
        int l = cur - k + 1, r = cur - 1;
        if (l < 0) l += n;
        if (r < 0) r += n;
        int to = que(l, r);
        if (to != -1) adj[cur].pb(to), deg[to]++;
        l = cur + 1, r = cur + k - 1;
        if (l >= n) l -= n;
        if (r >= n) r -= n;
        to = que(l, r);
        if (to != -1) adj[cur].pb(to), deg[to]++;
        upd2(1, 0, n - 1, cur);
    }
    //FOR (i, 0, n - 1) for (int j : adj[i]) debug(i, j);
    queue<int> q;
    FOR (i, 0, n - 1) if (!deg[i]) q.push(i);
    while (q.size()) {
        int pos = q.front();
        q.pop();
        is[pos][pos] = 1;
        //debug(pos);
        //FOR (i, 0, n - 1) cout << is[pos][i]; cout << '\n';
        for (int np : adj[pos]) {
            is[np] |= is[pos];
            if (--deg[np] == 0) q.push(np);
        }
    }
}

int compare_plants(int x, int y) {
    return is[x][y] ? 1 : is[y][x] ? -1 : 0;
}

/*
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

ex1(4 1 2 5 3 0)
6 4 5
1 3 2 0 1 3
0 1
3 4
2 0
1 3
5 2
*/

/*

    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;
    }
*/

#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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9812 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 7 ms 9988 KB Output is correct
6 Correct 43 ms 12960 KB Output is correct
7 Correct 301 ms 504028 KB Output is correct
8 Runtime error 856 ms 2097152 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9832 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 24 ms 34332 KB Output is correct
7 Correct 128 ms 135256 KB Output is correct
8 Correct 8 ms 12244 KB Output is correct
9 Correct 25 ms 34308 KB Output is correct
10 Correct 137 ms 135336 KB Output is correct
11 Correct 128 ms 135204 KB Output is correct
12 Correct 125 ms 135476 KB Output is correct
13 Correct 127 ms 135252 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9832 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 24 ms 34332 KB Output is correct
7 Correct 128 ms 135256 KB Output is correct
8 Correct 8 ms 12244 KB Output is correct
9 Correct 25 ms 34308 KB Output is correct
10 Correct 137 ms 135336 KB Output is correct
11 Correct 128 ms 135204 KB Output is correct
12 Correct 125 ms 135476 KB Output is correct
13 Correct 127 ms 135252 KB Output is correct
14 Correct 347 ms 503704 KB Output is correct
15 Runtime error 668 ms 2097152 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 5 ms 10196 KB Output is correct
3 Correct 78 ms 61692 KB Output is correct
4 Runtime error 696 ms 2097152 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9744 KB Output is correct
2 Correct 5 ms 9812 KB Output is correct
3 Correct 7 ms 9892 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 8 ms 12244 KB Output is correct
7 Correct 21 ms 18004 KB Output is correct
8 Correct 20 ms 18004 KB Output is correct
9 Correct 20 ms 17992 KB Output is correct
10 Correct 19 ms 18084 KB Output is correct
11 Correct 19 ms 18040 KB Output is correct
12 Correct 19 ms 17996 KB Output is correct
13 Correct 19 ms 18004 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9700 KB Output is correct
2 Correct 6 ms 9812 KB Output is correct
3 Correct 7 ms 9828 KB Output is correct
4 Correct 5 ms 9940 KB Output is correct
5 Correct 25 ms 34272 KB Output is correct
6 Runtime error 615 ms 2097152 KB Execution killed with signal 9
7 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 9812 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 7 ms 9988 KB Output is correct
6 Correct 43 ms 12960 KB Output is correct
7 Correct 301 ms 504028 KB Output is correct
8 Runtime error 856 ms 2097152 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -