oj.uz

Submission #622591

# Submission time Handle Problem Language Result Execution time Memory
622591 2022-08-04T12:03:11 Z wiwiho Comparing Plants (IOI20_plants) C++14
30 / 100
 1297 ms 52460 KB 
#include "plants.h"

#include <bits/stdc++.h>

#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define ef emplace_front
#define pob pop_back()
#define pof pop_front()
#define mp make_pair
#define F first
#define S second
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

const ll MAX = 1e6;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

void waassert(bool t){
    if(t) return;
    exit(0);
}

int n, K;
vector<int> rec;
vector<bool> use;

struct Node{
    int mn = 0, pos = 0, tag = 0;
};

Node operator+(Node a, Node b){
    Node c;
    c.mn = min(a.mn, b.mn);
    if(a.mn == c.mn) c.pos = a.pos;
    else c.pos = b.pos;
    return c;
}

vector<Node> st;
#define lc 2 * id + 1
#define rc 2 * id + 2

void build(vector<int>& o, int L = 0, int R = n - 1, int id = 0){
    if(L == R){
        st[id].mn = o[L];
        st[id].pos = L;
        return;
    }
    int M = (L + R) / 2;
    build(o, L, M, lc);
    build(o, M + 1, R, rc);
    st[id] = st[lc] + st[rc];
}

void addtag(int v, int id){
    st[id].tag += v;
    st[id].mn += v;
}

void push(int id){
    addtag(st[id].tag, lc);
    addtag(st[id].tag, rc);
    st[id].tag = 0;
}

void _modify(int l, int r, int v, int L = 0, int R = n - 1, int id = 0){
    if(l <= L && R <= r){
        addtag(v, id);
        return;
    }
    push(id);
    int M = (L + R) / 2;
    if(r <= M) _modify(l, r, v, L, M, lc);
    else if(l > M) _modify(l, r, v, M + 1, R, rc);
    else{
        _modify(l, r, v, L, M, lc);
        _modify(l, r, v, M + 1, R, rc);
    }
    st[id] = st[lc] + st[rc];
}

void modify(int l, int r, int v){
    l = (l % n + n) % n;
    r = (r % n + n) % n;
    if(l <= r) _modify(l, r, v);
    else{
        _modify(l, n - 1, v);
        _modify(0, r, v);
    }
}

Node _query(int l, int r, int L = 0, int R = n - 1, int id = 0){
    if(l <= L && R <= r) return st[id];
    push(id);
    int M = (L + R) / 2;
    if(r <= M) return _query(l, r, L, M, lc);
    else if(l > M) return _query(l, r, M + 1, R, rc);
    else return _query(l, r, L, M, lc) + _query(l, r, M + 1, R, rc);
}

Node query(int l, int r){
    l = (l % n + n) % n;
    r = (r % n + n) % n;
    if(l <= r) return _query(l, r);
    else{
        return _query(l, n - 1) + _query(0, r);
    }
}

void _print(int L = 0, int R = n - 1, int id = 0){
    if(L == R){
        cerr << st[id].mn << " ";
        return;
    }
    push(id);
    int M = (L + R) / 2;
    _print(L, M, lc);
    _print(M + 1, R, rc);
}

void print(){
    _print();
    cerr << "\n";
}

int getdis(int l, int r){
    l = (l % n + n) % n;
    r = (r % n + n) % n;
    if(l == r) return n;
    if(l > r) r += n;
    return r - l;
}

set<int> zero;
set<pii> sep;
vector<int> rk;

void solve(int _rk){
    
    while(st[0].mn == 0){
        int pos = st[0].pos;
        modify(pos, pos, MAX);

        if(zero.empty()){
            zero.insert(pos);
            sep.insert(mp(n, pos));
            continue;
        }
        
        auto it = zero.lower_bound(pos);
        if(it == zero.end()) it = zero.begin();
        int nxt = *it;
        int lst = it == zero.begin() ? *zero.rbegin() : *prev(it);
        sep.erase(mp(getdis(lst, nxt), nxt));
        sep.insert(mp(getdis(lst, pos), pos));
        sep.insert(mp(getdis(pos, nxt), nxt));
        zero.insert(pos);
    }

    int pos = sep.rbegin()->S;
    if(zero.size() == 1){
        sep.clear();
        zero.clear();
    }
    else{
        auto it = zero.lower_bound(pos);
        int nxt = next(it) == zero.end() ? *zero.begin() : *next(it);
        int lst = it == zero.begin() ? *zero.rbegin() : *prev(it);
        sep.erase(mp(getdis(lst, pos), pos));
        sep.erase(mp(getdis(pos, nxt), nxt));
        sep.insert(mp(getdis(lst, nxt), nxt));
        zero.erase(pos);
    }

    use[pos] = true;
    rk[pos] = _rk;
    modify(pos - K + 1, pos - 1, -1);
}

vector<int> ans;
vector<vector<int>> ri, le;

void init(int k, vector<int> _r){
    K = k;
    rec = _r;
    n = rec.size();
    st.resize(4 * n);
    use.resize(n);
    rk.resize(n);
    ans.resize(n);
    build(rec);

    for(int i = n - 1; i >= 0; i--){
        solve(i);
    }

    le.resize(20, vector<int>(n));
    ri.resize(20, vector<int>(n));
    
    {
        vector<int> tmp(n, 1);
        build(tmp);
    }
    vector<int> pos(n);
    for(int i = 0; i < n; i++) pos[rk[i]] = i;
    
    for(int i = 0; i < n; i++){
        Node tmp = query(pos[i] + 1, pos[i] + k - 1);
        if(tmp.mn != 1){
            int nxt = tmp.pos;
            ri[0][pos[i]] = getdis(pos[i], nxt);
            /*cerr << "right " << pos[i] << " : " << nxt << "\n";
            cerr << pos[i] + 1 << " " << pos[i] + k - 1 << "\n";*/
        }
        tmp = query(pos[i] - k + 1, pos[i] - 1);
        if(tmp.mn != 1){
            int nxt = tmp.pos;
            le[0][pos[i]] = getdis(nxt, pos[i]);
            /*cerr << "left " << pos[i] << " : " << nxt << "\n";
            cerr << pos[i] - k + 1 << " " << pos[i] - 1 << "\n";*/
        }
        modify(pos[i], pos[i], -i);
    }
    
    for(int i = 1; i < 20; i++){
        for(int j = 0; j < n; j++){
            int nxt = j - le[i - 1][j];
            nxt = (nxt % n + n) % n;
            le[i][j] = le[i - 1][j] + le[i - 1][nxt];

            nxt = j + ri[i - 1][j];
            nxt = nxt % n;
            ri[i][j] = ri[i - 1][j] + ri[i - 1][nxt];
        }
    }

    /*cerr << "rank ";
    printv(rk, cerr);
    cerr << "left ";
    printv(le[0], cerr);
    cerr << "right ";
    printv(ri[0], cerr);*/

}

bool checkgreater(int x, int y){
    // right
    {
        int dis = getdis(x, y);
        int tmp = 0;
        int now = x;
        for(int i = 19; i >= 0; i--){
            if(tmp + ri[i][now] >= dis - K + 1) continue;
            tmp += ri[i][now];
            now = (x + tmp) % n;
        }
        if(tmp < dis - K + 1){
            tmp += ri[0][now];
            now = (x + tmp) % n;
        }
        if(tmp >= dis - K + 1 && rk[now] > rk[y]) return true;
    }
    // left
    {
        int dis = getdis(y, x);
        int tmp = 0;
        int now = x;
        for(int i = 19; i >= 0; i--){
            if(tmp + le[i][now] >= dis - K + 1) continue;
            tmp += le[i][now];
            now = ((x - tmp) % n + n) % n;
        }
        if(tmp < dis - K + 1){
            tmp += le[0][now];
            now = ((x - tmp) % n + n) % n;
        }
        if(tmp >= dis - K + 1 && rk[now] > rk[y]) return true;
    }
    return false;
}

int compare_plants(int x, int y){
    if(checkgreater(x, y)) return 1;
    if(checkgreater(y, x)) return -1;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 151 ms 4016 KB Output is correct
7 Correct 300 ms 9856 KB Output is correct
8 Correct 1239 ms 51624 KB Output is correct
9 Correct 1297 ms 51504 KB Output is correct
10 Correct 1257 ms 52216 KB Output is correct
11 Correct 1256 ms 51800 KB Output is correct
12 Correct 1252 ms 51304 KB Output is correct
13 Correct 856 ms 51772 KB Output is correct
14 Correct 1279 ms 51024 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 620 KB Output is correct
7 Correct 74 ms 6140 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 81 ms 6120 KB Output is correct
11 Correct 68 ms 6072 KB Output is correct
12 Correct 143 ms 6252 KB Output is correct
13 Correct 74 ms 6092 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 620 KB Output is correct
7 Correct 74 ms 6140 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 81 ms 6120 KB Output is correct
11 Correct 68 ms 6072 KB Output is correct
12 Correct 143 ms 6252 KB Output is correct
13 Correct 74 ms 6092 KB Output is correct
14 Correct 137 ms 10012 KB Output is correct
15 Incorrect 1072 ms 51924 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 296 KB Output is correct
3 Correct 111 ms 5236 KB Output is correct
4 Correct 1030 ms 51360 KB Output is correct
5 Correct 1064 ms 52460 KB Output is correct
6 Correct 999 ms 51508 KB Output is correct
7 Correct 934 ms 51640 KB Output is correct
8 Incorrect 1052 ms 51796 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 304 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 5 ms 412 KB Output is correct
7 Correct 38 ms 1220 KB Output is correct
8 Correct 16 ms 1276 KB Output is correct
9 Correct 26 ms 1208 KB Output is correct
10 Correct 15 ms 1288 KB Output is correct
11 Correct 36 ms 1280 KB Output is correct
12 Correct 29 ms 1220 KB Output is correct
13 Correct 14 ms 1320 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 903 ms 50564 KB Output is correct
7 Correct 852 ms 50656 KB Output is correct
8 Correct 760 ms 50764 KB Output is correct
9 Incorrect 930 ms 50992 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 151 ms 4016 KB Output is correct
7 Correct 300 ms 9856 KB Output is correct
8 Correct 1239 ms 51624 KB Output is correct
9 Correct 1297 ms 51504 KB Output is correct
10 Correct 1257 ms 52216 KB Output is correct
11 Correct 1256 ms 51800 KB Output is correct
12 Correct 1252 ms 51304 KB Output is correct
13 Correct 856 ms 51772 KB Output is correct
14 Correct 1279 ms 51024 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 4 ms 620 KB Output is correct
21 Correct 74 ms 6140 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 4 ms 596 KB Output is correct
24 Correct 81 ms 6120 KB Output is correct
25 Correct 68 ms 6072 KB Output is correct
26 Correct 143 ms 6252 KB Output is correct
27 Correct 74 ms 6092 KB Output is correct
28 Correct 137 ms 10012 KB Output is correct
29 Incorrect 1072 ms 51924 KB Output isn't correct
30 Halted 0 ms 0 KB -