oj.uz

Submission #419124

# Submission time Handle Problem Language Result Execution time Memory
419124 2021-06-06T13:06:24 Z 79brue Comparing Plants (IOI20_plants) C++14
44 / 100
 2050 ms 83424 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;

int n, k;
int arr[400002];
int sum[400002];
int ans[400002];

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;

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

int compare_plants(int x, int y) {
	x++, y++;

	if(ans[x] > ans[y]) return 1;
	return -1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12872 KB Output is correct
2 Correct 8 ms 12748 KB Output is correct
3 Correct 7 ms 12804 KB Output is correct
4 Incorrect 7 ms 12748 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12800 KB Output is correct
2 Correct 7 ms 12824 KB Output is correct
3 Correct 7 ms 12816 KB Output is correct
4 Correct 7 ms 12748 KB Output is correct
5 Correct 7 ms 12876 KB Output is correct
6 Correct 15 ms 13156 KB Output is correct
7 Correct 89 ms 17636 KB Output is correct
8 Correct 10 ms 12900 KB Output is correct
9 Correct 13 ms 13132 KB Output is correct
10 Correct 88 ms 17656 KB Output is correct
11 Correct 79 ms 17604 KB Output is correct
12 Correct 84 ms 17732 KB Output is correct
13 Correct 90 ms 17648 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12800 KB Output is correct
2 Correct 7 ms 12824 KB Output is correct
3 Correct 7 ms 12816 KB Output is correct
4 Correct 7 ms 12748 KB Output is correct
5 Correct 7 ms 12876 KB Output is correct
6 Correct 15 ms 13156 KB Output is correct
7 Correct 89 ms 17636 KB Output is correct
8 Correct 10 ms 12900 KB Output is correct
9 Correct 13 ms 13132 KB Output is correct
10 Correct 88 ms 17656 KB Output is correct
11 Correct 79 ms 17604 KB Output is correct
12 Correct 84 ms 17732 KB Output is correct
13 Correct 90 ms 17648 KB Output is correct
14 Correct 189 ms 23660 KB Output is correct
15 Correct 2025 ms 80672 KB Output is correct
16 Correct 189 ms 23712 KB Output is correct
17 Correct 2013 ms 80676 KB Output is correct
18 Correct 966 ms 80608 KB Output is correct
19 Correct 1006 ms 80640 KB Output is correct
20 Correct 1853 ms 80672 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12748 KB Output is correct
2 Correct 8 ms 12876 KB Output is correct
3 Correct 75 ms 16092 KB Output is correct
4 Correct 849 ms 83404 KB Output is correct
5 Correct 1109 ms 83424 KB Output is correct
6 Correct 1597 ms 83396 KB Output is correct
7 Correct 1965 ms 83272 KB Output is correct
8 Correct 2050 ms 83360 KB Output is correct
9 Correct 931 ms 83292 KB Output is correct
10 Correct 992 ms 83424 KB Output is correct
11 Correct 628 ms 83268 KB Output is correct
12 Correct 836 ms 83356 KB Output is correct
13 Correct 930 ms 83340 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12872 KB Output is correct
2 Correct 8 ms 12748 KB Output is correct
3 Correct 7 ms 12804 KB Output is correct
4 Incorrect 7 ms 12748 KB Output isn't correct
5 Halted 0 ms 0 KB -