oj.uz

Submission #434659

# Submission time Handle Problem Language Result Execution time Memory
434659 2021-06-21T14:05:17 Z 79brue Comparing Plants (IOI20_plants) C++14
100 / 100
 2857 ms 216168 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];
ll Lsp[400002][20], Rsp[400002][20];
ll 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] * n;
        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] * n;
        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 8 ms 12876 KB Output is correct
2 Correct 7 ms 12832 KB Output is correct
3 Correct 7 ms 12876 KB Output is correct
4 Correct 7 ms 12876 KB Output is correct
5 Correct 7 ms 12876 KB Output is correct
6 Correct 86 ms 15660 KB Output is correct
7 Correct 259 ms 37100 KB Output is correct
8 Correct 1161 ms 212588 KB Output is correct
9 Correct 1177 ms 212500 KB Output is correct
10 Correct 1197 ms 212448 KB Output is correct
11 Correct 1204 ms 212420 KB Output is correct
12 Correct 1288 ms 212324 KB Output is correct
13 Correct 1245 ms 212424 KB Output is correct
14 Correct 1377 ms 212548 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 12876 KB Output is correct
5 Correct 8 ms 13004 KB Output is correct
6 Correct 15 ms 13876 KB Output is correct
7 Correct 184 ms 21260 KB Output is correct
8 Correct 10 ms 13004 KB Output is correct
9 Correct 14 ms 13880 KB Output is correct
10 Correct 176 ms 21188 KB Output is correct
11 Correct 137 ms 21104 KB Output is correct
12 Correct 138 ms 21312 KB Output is correct
13 Correct 190 ms 21160 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 12876 KB Output is correct
5 Correct 8 ms 13004 KB Output is correct
6 Correct 15 ms 13876 KB Output is correct
7 Correct 184 ms 21260 KB Output is correct
8 Correct 10 ms 13004 KB Output is correct
9 Correct 14 ms 13880 KB Output is correct
10 Correct 176 ms 21188 KB Output is correct
11 Correct 137 ms 21104 KB Output is correct
12 Correct 138 ms 21312 KB Output is correct
13 Correct 190 ms 21160 KB Output is correct
14 Correct 421 ms 37284 KB Output is correct
15 Correct 2755 ms 212616 KB Output is correct
16 Correct 397 ms 36996 KB Output is correct
17 Correct 2763 ms 212496 KB Output is correct
18 Correct 1599 ms 212716 KB Output is correct
19 Correct 1636 ms 212460 KB Output is correct
20 Correct 2569 ms 212660 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12876 KB Output is correct
2 Correct 8 ms 12876 KB Output is correct
3 Correct 124 ms 17480 KB Output is correct
4 Correct 1469 ms 212568 KB Output is correct
5 Correct 1654 ms 212552 KB Output is correct
6 Correct 2256 ms 212568 KB Output is correct
7 Correct 2551 ms 212564 KB Output is correct
8 Correct 2857 ms 212568 KB Output is correct
9 Correct 1554 ms 212572 KB Output is correct
10 Correct 1541 ms 212668 KB Output is correct
11 Correct 1239 ms 212516 KB Output is correct
12 Correct 1464 ms 212572 KB Output is correct
13 Correct 1530 ms 212544 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12876 KB Output is correct
2 Correct 7 ms 12912 KB Output is correct
3 Correct 7 ms 12876 KB Output is correct
4 Correct 7 ms 12876 KB Output is correct
5 Correct 7 ms 12876 KB Output is correct
6 Correct 9 ms 13004 KB Output is correct
7 Correct 28 ms 13800 KB Output is correct
8 Correct 29 ms 13752 KB Output is correct
9 Correct 29 ms 13772 KB Output is correct
10 Correct 30 ms 13776 KB Output is correct
11 Correct 28 ms 13796 KB Output is correct
12 Correct 32 ms 13760 KB Output is correct
13 Correct 30 ms 13836 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12876 KB Output is correct
2 Correct 7 ms 12816 KB Output is correct
3 Correct 7 ms 12876 KB Output is correct
4 Correct 7 ms 12876 KB Output is correct
5 Correct 12 ms 13776 KB Output is correct
6 Correct 1600 ms 212384 KB Output is correct
7 Correct 2104 ms 214844 KB Output is correct
8 Correct 2289 ms 214972 KB Output is correct
9 Correct 2514 ms 215328 KB Output is correct
10 Correct 1362 ms 214456 KB Output is correct
11 Correct 1753 ms 215108 KB Output is correct
12 Correct 1327 ms 214472 KB Output is correct
13 Correct 1577 ms 214664 KB Output is correct
14 Correct 2017 ms 214812 KB Output is correct
15 Correct 2520 ms 215108 KB Output is correct
16 Correct 1424 ms 214620 KB Output is correct
17 Correct 1545 ms 214820 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12876 KB Output is correct
2 Correct 7 ms 12832 KB Output is correct
3 Correct 7 ms 12876 KB Output is correct
4 Correct 7 ms 12876 KB Output is correct
5 Correct 7 ms 12876 KB Output is correct
6 Correct 86 ms 15660 KB Output is correct
7 Correct 259 ms 37100 KB Output is correct
8 Correct 1161 ms 212588 KB Output is correct
9 Correct 1177 ms 212500 KB Output is correct
10 Correct 1197 ms 212448 KB Output is correct
11 Correct 1204 ms 212420 KB Output is correct
12 Correct 1288 ms 212324 KB Output is correct
13 Correct 1245 ms 212424 KB Output is correct
14 Correct 1377 ms 212548 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 12876 KB Output is correct
19 Correct 8 ms 13004 KB Output is correct
20 Correct 15 ms 13876 KB Output is correct
21 Correct 184 ms 21260 KB Output is correct
22 Correct 10 ms 13004 KB Output is correct
23 Correct 14 ms 13880 KB Output is correct
24 Correct 176 ms 21188 KB Output is correct
25 Correct 137 ms 21104 KB Output is correct
26 Correct 138 ms 21312 KB Output is correct
27 Correct 190 ms 21160 KB Output is correct
28 Correct 421 ms 37284 KB Output is correct
29 Correct 2755 ms 212616 KB Output is correct
30 Correct 397 ms 36996 KB Output is correct
31 Correct 2763 ms 212496 KB Output is correct
32 Correct 1599 ms 212716 KB Output is correct
33 Correct 1636 ms 212460 KB Output is correct
34 Correct 2569 ms 212660 KB Output is correct
35 Correct 7 ms 12876 KB Output is correct
36 Correct 8 ms 12876 KB Output is correct
37 Correct 124 ms 17480 KB Output is correct
38 Correct 1469 ms 212568 KB Output is correct
39 Correct 1654 ms 212552 KB Output is correct
40 Correct 2256 ms 212568 KB Output is correct
41 Correct 2551 ms 212564 KB Output is correct
42 Correct 2857 ms 212568 KB Output is correct
43 Correct 1554 ms 212572 KB Output is correct
44 Correct 1541 ms 212668 KB Output is correct
45 Correct 1239 ms 212516 KB Output is correct
46 Correct 1464 ms 212572 KB Output is correct
47 Correct 1530 ms 212544 KB Output is correct
48 Correct 7 ms 12876 KB Output is correct
49 Correct 7 ms 12912 KB Output is correct
50 Correct 7 ms 12876 KB Output is correct
51 Correct 7 ms 12876 KB Output is correct
52 Correct 7 ms 12876 KB Output is correct
53 Correct 9 ms 13004 KB Output is correct
54 Correct 28 ms 13800 KB Output is correct
55 Correct 29 ms 13752 KB Output is correct
56 Correct 29 ms 13772 KB Output is correct
57 Correct 30 ms 13776 KB Output is correct
58 Correct 28 ms 13796 KB Output is correct
59 Correct 32 ms 13760 KB Output is correct
60 Correct 30 ms 13836 KB Output is correct
61 Correct 108 ms 19136 KB Output is correct
62 Correct 267 ms 39168 KB Output is correct
63 Correct 1405 ms 215324 KB Output is correct
64 Correct 1639 ms 215520 KB Output is correct
65 Correct 2272 ms 215832 KB Output is correct
66 Correct 2565 ms 216000 KB Output is correct
67 Correct 2779 ms 216168 KB Output is correct
68 Correct 1464 ms 215532 KB Output is correct
69 Correct 1974 ms 216052 KB Output is correct
70 Correct 1461 ms 215368 KB Output is correct
71 Correct 1687 ms 215544 KB Output is correct
72 Correct 2174 ms 215720 KB Output is correct
73 Correct 2555 ms 216036 KB Output is correct
74 Correct 1401 ms 215552 KB Output is correct
75 Correct 1607 ms 215676 KB Output is correct