oj.uz

Submission #800258

# Submission time Handle Problem Language Result Execution time Memory
800258 2023-08-01T12:51:16 Z becaido Comparing Plants (IOI20_plants) C++17
15 / 100
 583 ms 42768 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;
}

int id[SIZE];
bool big[SIZE], sml[SIZE];
vector<int> rev[SIZE];
void init(int _k, vector<int> r) {
    n = r.size();
    k = _k;
    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);
        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);
        upd2(1, 0, n - 1, cur);
    }
    FOR (i, 0, n - 1) for (int j : adj[i]) rev[j].pb(i);
    queue<int> q;
    q.push(0);
    while (q.size()) {
        int pos = q.front();
        q.pop();
        for (int np : adj[pos]) if (!big[np]) {
            big[np] = 1;
            q.push(np);
        }
    }
    q.push(0);
    while (q.size()) {
        int pos = q.front();
        q.pop();
        for (int np : rev[pos]) if (!sml[np]) {
            sml[np] = 1;
            q.push(np);
        }
    }
}

int compare_plants(int x, int y) {
    return big[y] ? -1 : sml[y] ? 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 9 ms 14420 KB Output is correct
2 Correct 10 ms 14420 KB Output is correct
3 Incorrect 8 ms 14420 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Incorrect 8 ms 14332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Incorrect 8 ms 14332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Incorrect 10 ms 14380 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 9 ms 14392 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 10 ms 14556 KB Output is correct
6 Correct 552 ms 41680 KB Output is correct
7 Correct 548 ms 42240 KB Output is correct
8 Correct 556 ms 42612 KB Output is correct
9 Correct 539 ms 42700 KB Output is correct
10 Correct 411 ms 41680 KB Output is correct
11 Correct 416 ms 42768 KB Output is correct
12 Correct 342 ms 41860 KB Output is correct
13 Correct 435 ms 42112 KB Output is correct
14 Correct 504 ms 42440 KB Output is correct
15 Correct 583 ms 42620 KB Output is correct
16 Correct 389 ms 41824 KB Output is correct
17 Correct 444 ms 41988 KB Output is correct

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 10 ms 14420 KB Output is correct
3 Incorrect 8 ms 14420 KB Output isn't correct
4 Halted 0 ms 0 KB -