oj.uz

Submission #434657

# Submission time Handle Problem Language Result Execution time Memory
434657 2021-06-21T14:03:09 Z 79brue Comparing Plants (IOI20_plants) C++14
32 / 100
 2722 ms 149864 KB 
#include <bits/stdc++.h>
#include "plants.h"

using namespace std;

typedef long long ll;

struct segTree{
    pair<int, int> tree[1600002];
    int lazy[1600002];

    void init(int i, int l, int r, int *A){
        lazy[i] = 0;
        if(l==r){
            tree[i] = make_pair(A[l], l);
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, A);
        init(i*2+1, m+1, r, A);
        tree[i] = min(tree[i*2], tree[i*2+1]);
    }

    void propagate(int i, int l, int r){
        tree[i].first += lazy[i];
        if(l!=r){
            lazy[i*2] += lazy[i];
            lazy[i*2+1] += lazy[i];
        }
        lazy[i] = 0;
    }

    void add(int i, int l, int r, int s, int e, int val){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            lazy[i] += val;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        add(i*2, l, m, s, e, val);
        add(i*2+1, m+1, r, s, e, val);
        tree[i] = min(tree[i*2], tree[i*2+1]);
    }

    pair<int, int> findMin(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if(r<s || e<l) return make_pair(INT_MAX, INT_MAX);
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return min(findMin(i*2, l, m, s, e), findMin(i*2+1, m+1, r, s, e));
    }
} tree;

struct mineSeg{
    struct Node {
        ll lmax; int lidx;
        ll rmax; int ridx;
        ll ans; int ansl, ansr;
        ll sum;

        Node(){}
        Node(ll x, int idx){
            lmax = rmax = ans = sum = x;
            lidx = ridx = ansl = ansr = idx;
        }

        Node merge(const Node &r)const{
            Node ret = *this;
            if(ret.lmax < sum + r.lmax){
                ret.lmax = sum + r.lmax;
                ret.lidx = r.lidx;
            }

            ret.rmax += r.sum;
            if(ret.rmax < r.rmax){
                ret.rmax = r.rmax;
                ret.ridx = r.ridx;
            }

            if(ret.ans < r.ans) ret.ans = r.ans, ret.ansl = r.ansl, ret.ansr = r.ansr;
            if(ret.ans < rmax + r.lmax){
                ret.ans = rmax + r.lmax;
                ret.ansl = ridx, ret.ansr = r.lidx;
            }

            ret.sum += r.sum;
            return ret;
        }
    } tree[1600002];

    void init(int i, int l, int r, int *A){
        if(l==r){
            tree[i] = Node(A[l] ? 1 : -1e9, l);
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, A);
        init(i*2+1, m+1, r, A);
        tree[i] = tree[i*2].merge(tree[i*2+1]);
    }

    void change(int i, int l, int r, int idx, int x){
        if(l==r){
            tree[i] = Node(x ? 1 : -1e9, l);
            return;
        }
        int m = (l+r)>>1;
        if(idx <= m) change(i*2, l, m, idx, x);
        else change(i*2+1, m+1, r, idx, x);
        tree[i] = tree[i*2].merge(tree[i*2+1]);
    }
} mineTree;

struct checkSeg{
    int tree[1600002];

    void init(int i, int l, int r){
        if(l==r){
            tree[i] = 0;
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m);
        init(i*2+1, m+1, r);
        tree[i] = max(tree[i*2], tree[i*2+1]);
    }

    void update(int i, int l, int r, int idx, int val){
        if(l==r){
            tree[i] = val;
            return;
        }
        int m = (l+r)>>1;
        if(idx <= m) update(i*2, l, m, idx, val);
        else update(i*2+1, m+1, r, idx, val);
        tree[i] = max(tree[i*2], tree[i*2+1]);
    }

    int query(int i, int l, int r, int s, int e){
        if(r<s || e<l) return 0;
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return max(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
    }
} chkseg;

int n, k;
int arr[400002];
int sum[400002];
int ans[400002];
int ord[400002];
int L[400002], R[400002];
int Lsp[400002][20], Rsp[400002][20];
int Lg[400002][20], Rg[400002][20];

void init(int _k, vector<int> r) {
	n = (int)r.size();
	k = _k;
	for(int i=1; i<=n; i++) arr[i] = r[i-1];
	for(int i=n+1; i<=n*2; i++) arr[i] = arr[i-n];

    tree.init(1, 1, n*2, arr);
    mineTree.init(1, 1, n*2, arr);

    for(int turn=n; turn>=1; turn--){
        auto tmp = mineTree.tree[1];
        if(tmp.ans < k-1) exit(1);
        int loc = tmp.ansr % n + 1;
        ans[loc] = turn;
        ord[turn] = loc;

        /// 1에서 0이 되는 위치들을 검색
        int lim = loc+n, leftmost = lim-k+1;
        while(leftmost < lim){
            pair<int, int> tmp2 = tree.findMin(1, 1, n*2, leftmost, lim-1);
            if(tmp2.first > 1) break;
            int x = tmp2.second;
            mineTree.change(1, 1, n*2, (x-1)%n+1, 0);
            mineTree.change(1, 1, n*2, (x-1)%n+1+n, 0);
            leftmost = x+1;
        }
        mineTree.change(1, 1, n*2, loc, 1);
        mineTree.change(1, 1, n*2, loc+n, 1);

        /// tree 변경
        tree.add(1, 1, n*2, loc, loc, 1000000000);
        tree.add(1, 1, n*2, loc+n, loc+n, 1000000000);

        if(loc >= k){
            tree.add(1, 1, n*2, loc-k+1, loc, -1);
            tree.add(1, 1, n*2, loc-k+1+n, loc+n, -1);
        }
        else{
            tree.add(1, 1, n*2, 1, loc, -1);
            tree.add(1, 1, n*2, loc-k+1+n, loc+n, -1);
            tree.add(1, 1, n*2, 2*n-(k-loc)+1, n*2, -1);
        }
    }

    chkseg.init(1, 1, n*2);
    for(int turn=1; turn<=n; turn++){
        int x = ord[turn];

        L[turn] = chkseg.query(1, 1, n*2, x+n-(k-1), x+n);
        R[turn] = chkseg.query(1, 1, n*2, x, x+(k-1));

        chkseg.update(1, 1, n*2, x, turn);
        chkseg.update(1, 1, n*2, x+n, turn);
    }

    for(int i=1; i<=n; i++){
        Lsp[i][0] = L[i], Rsp[i][0] = R[i];
        if(ord[i] < ord[L[i]]) Lg[i][0] = -1;
        if(ord[i] > ord[R[i]]) Rg[i][0] = 1;
    }
    for(int d=1; d<20; d++){
        for(int i=1; i<=n; i++){
            Lsp[i][d] = Lsp[Lsp[i][d-1]][d-1];
            Rsp[i][d] = Rsp[Rsp[i][d-1]][d-1];
            Lg[i][d] = Lg[i][d-1] + Lg[Lsp[i][d-1]][d-1];
            Rg[i][d] = Rg[i][d-1] + Rg[Rsp[i][d-1]][d-1];
        }
    }
}

int compare_plants(int x, int y) {
	x++, y++;
	int def = ans[x] > ans[y] ? 1 : -1;
	if(ans[x] < ans[y]) swap(x, y);

	int tmp = ans[x];
	ll lLim=0, rLim=0;
    for(int d=19; d>=0; d--){
        if(Lsp[tmp][d] == 0 || Lsp[tmp][d] < ans[y]) continue;
        lLim += Lg[tmp][d];
        tmp = Lsp[tmp][d];
    }
    lLim += ord[tmp];

    tmp = ans[x];
    for(int d=19; d>=0; d--){
        if(Rsp[tmp][d] == 0 || Rsp[tmp][d] < ans[y]) continue;
        rLim += Rg[tmp][d];
        tmp = Rsp[tmp][d];
    }
    rLim += ord[tmp];

    ll l = lLim, r = rLim;
    if((r-l) >= n) return def;

    l = (n - (-l%n))%n;
    if(!l) l=n;

    r = (n - (-r%n))%n;
    if(!r) r=n;
    if(r<l) r+=n;

    if(l<=y && y<=r) return def;
    if(l<=y+n && y+n<=r) return def;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12876 KB Output is correct
2 Correct 7 ms 12876 KB Output is correct
3 Correct 7 ms 12876 KB Output is correct
4 Correct 9 ms 12876 KB Output is correct
5 Correct 9 ms 12804 KB Output is correct
6 Correct 88 ms 15684 KB Output is correct
7 Correct 183 ms 30884 KB Output is correct
8 Correct 1022 ms 149740 KB Output is correct
9 Correct 1067 ms 149684 KB Output is correct
10 Correct 1104 ms 149752 KB Output is correct
11 Correct 1083 ms 149828 KB Output is correct
12 Correct 1127 ms 149820 KB Output is correct
13 Correct 1172 ms 149808 KB Output is correct
14 Correct 1273 ms 149864 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12876 KB Output is correct
2 Correct 7 ms 12876 KB Output is correct
3 Correct 7 ms 12876 KB Output is correct
4 Correct 7 ms 12896 KB Output is correct
5 Correct 10 ms 12928 KB Output is correct
6 Correct 15 ms 13516 KB Output is correct
7 Correct 180 ms 19424 KB Output is correct
8 Correct 10 ms 13004 KB Output is correct
9 Correct 14 ms 13516 KB Output is correct
10 Correct 185 ms 19432 KB Output is correct
11 Correct 130 ms 19408 KB Output is correct
12 Correct 129 ms 19524 KB Output is correct
13 Correct 163 ms 19420 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12876 KB Output is correct
2 Correct 7 ms 12876 KB Output is correct
3 Correct 7 ms 12876 KB Output is correct
4 Correct 7 ms 12896 KB Output is correct
5 Correct 10 ms 12928 KB Output is correct
6 Correct 15 ms 13516 KB Output is correct
7 Correct 180 ms 19424 KB Output is correct
8 Correct 10 ms 13004 KB Output is correct
9 Correct 14 ms 13516 KB Output is correct
10 Correct 185 ms 19432 KB Output is correct
11 Correct 130 ms 19408 KB Output is correct
12 Correct 129 ms 19524 KB Output is correct
13 Correct 163 ms 19420 KB Output is correct
14 Correct 348 ms 30760 KB Output is correct
15 Correct 2722 ms 149744 KB Output is correct
16 Correct 321 ms 30916 KB Output is correct
17 Correct 2654 ms 149708 KB Output is correct
18 Correct 1449 ms 149732 KB Output is correct
19 Correct 1526 ms 149804 KB Output is correct
20 Correct 2683 ms 149800 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12876 KB Output is correct
2 Correct 7 ms 12876 KB Output is correct
3 Incorrect 111 ms 16836 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12812 KB Output is correct
2 Correct 7 ms 12876 KB Output is correct
3 Correct 7 ms 12876 KB Output is correct
4 Correct 7 ms 12876 KB Output is correct
5 Correct 8 ms 12876 KB Output is correct
6 Correct 9 ms 13004 KB Output is correct
7 Correct 31 ms 13660 KB Output is correct
8 Incorrect 32 ms 13668 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12808 KB Output is correct
2 Correct 7 ms 12876 KB Output is correct
3 Correct 7 ms 12876 KB Output is correct
4 Correct 7 ms 12876 KB Output is correct
5 Incorrect 11 ms 13516 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12876 KB Output is correct
2 Correct 7 ms 12876 KB Output is correct
3 Correct 7 ms 12876 KB Output is correct
4 Correct 9 ms 12876 KB Output is correct
5 Correct 9 ms 12804 KB Output is correct
6 Correct 88 ms 15684 KB Output is correct
7 Correct 183 ms 30884 KB Output is correct
8 Correct 1022 ms 149740 KB Output is correct
9 Correct 1067 ms 149684 KB Output is correct
10 Correct 1104 ms 149752 KB Output is correct
11 Correct 1083 ms 149828 KB Output is correct
12 Correct 1127 ms 149820 KB Output is correct
13 Correct 1172 ms 149808 KB Output is correct
14 Correct 1273 ms 149864 KB Output is correct
15 Correct 7 ms 12876 KB Output is correct
16 Correct 7 ms 12876 KB Output is correct
17 Correct 7 ms 12876 KB Output is correct
18 Correct 7 ms 12896 KB Output is correct
19 Correct 10 ms 12928 KB Output is correct
20 Correct 15 ms 13516 KB Output is correct
21 Correct 180 ms 19424 KB Output is correct
22 Correct 10 ms 13004 KB Output is correct
23 Correct 14 ms 13516 KB Output is correct
24 Correct 185 ms 19432 KB Output is correct
25 Correct 130 ms 19408 KB Output is correct
26 Correct 129 ms 19524 KB Output is correct
27 Correct 163 ms 19420 KB Output is correct
28 Correct 348 ms 30760 KB Output is correct
29 Correct 2722 ms 149744 KB Output is correct
30 Correct 321 ms 30916 KB Output is correct
31 Correct 2654 ms 149708 KB Output is correct
32 Correct 1449 ms 149732 KB Output is correct
33 Correct 1526 ms 149804 KB Output is correct
34 Correct 2683 ms 149800 KB Output is correct
35 Correct 7 ms 12876 KB Output is correct
36 Correct 7 ms 12876 KB Output is correct
37 Incorrect 111 ms 16836 KB Output isn't correct
38 Halted 0 ms 0 KB -