oj.uz

Submission #687311

# Submission time Handle Problem Language Result Execution time Memory
687311 2023-01-26T09:36:47 Z 79brue Radio Towers (IOI22_towers) C++17
18 / 100
 1947 ms 454576 KB 
#include "towers.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
int arr[100002];

/** 세그먼트 트리 */
struct segTree{
    int minV[400002], maxV[400002];

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

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

    int queryMax(int i, int l, int r, int s, int e){
        if(r<s || e<l) return INT_MIN;
        if(s<=l && r<=e) return maxV[i];
        int m = (l+r)>>1;
        return max(queryMax(i*2, l, m, s, e), queryMax(i*2+1, m+1, r, s, e));
    }
} segtree;

void calculateIntervals();

void init(int N, vector<int> H){
    n = N;
    for(int i=0; i<n; i++) arr[i] = H[i];

    segtree.init(1, 0, n-1, arr);
    calculateIntervals();
}

/** PST 구조체
 *  1. 구간 합 쿼리 처리 기능
 *  2. 어떤 pair (x, y)가 들어올 때, 지금까지 들어온 pair의 max 처리 기능
 */
struct PST{
    struct Node{
        Node *lc, *rc;
        int sum;
        pair<int, int> lPair, rPair;

        Node(Node* node){
            lc = node->lc, rc = node->rc;
            sum = node->sum;
            lPair = node->lPair, rPair = node->rPair;
        }

        Node(int l, int r){
            lc = rc = nullptr;
            sum = 0;
            lPair = rPair = make_pair(-1, -1);

            if(l==r) return;
            int m = (l+r)>>1;
            lc = new Node(l, m);
            rc = new Node(m+1, r);
        }

        Node* update(int l, int r, int x, int v){
            if(l==r){
                Node *node = new Node(this);
                node->sum += v;
                return node;
            }
            int m = (l+r)>>1;
            Node *node = new Node(this);
            if(x<=m){
                node->lc = lc->update(l, m, x, v);
                node->sum += v;
                return node;
            }
            else{
                node->rc = rc->update(m+1, r, x, v);
                node->sum += v;
                return node;
            }
        }

        Node* updateL(int l, int r, int s, int e, pair<int, int> p){
            if(r<s || e<l) return this;
            if(s<=l && r<=e){
                Node *node = new Node(this);
                node->lPair = p;
                return node;
            }
            int m = (l+r)>>1;
            Node *node = new Node(this);
            node->lc = lc->updateL(l, m, s, e, p);
            node->rc = rc->updateL(m+1, r, s, e, p);
            return node;
        }

        Node* updateR(int l, int r, int s, int e, pair<int, int> p){
            if(r<s || e<l) return this;
            if(s<=l && r<=e){
                Node *node = new Node(this);
                node->rPair = p;
                return node;
            }
            int m = (l+r)>>1;
            Node *node = new Node(this);
            node->lc = lc->updateR(l, m, s, e, p);
            node->rc = rc->updateR(m+1, r, s, e, p);
            return node;
        }

        int query(int l, int r, int s, int e){
            if(r<s || e<l) return 0;
            if(s<=l && r<=e) return sum;
            int m = (l+r)>>1;
            return lc->query(l, m, s, e) + rc->query(m+1, r, s, e);
        }

        pair<int, int> queryL(int l, int r, int x){
            if(l==r) return lPair;
            int m = (l+r)>>1;
            if(x<=m) return max(lPair, lc->queryL(l, m, x));
            else return max(lPair, rc->queryL(m+1, r, x));
        }

        pair<int, int> queryR(int l, int r, int x){
            if(l==r) return rPair;
            int m = (l+r)>>1;
            if(x<=m) return max(rPair, lc->queryR(l, m, x));
            else return max(rPair, rc->queryR(m+1, r, x));
        }
    } *root;
    int n, curD;
    Node *history[200002];

    PST(){}

    void init(int N){
        n = N;
        root = new Node(0, n-1);
        curD = 0;
        memset(history, 0, sizeof(history));
    }

    void nextD(){
        history[curD++] = root;
    }

    void update(int x, int v){
        root = root->update(0, n-1, x, v);
    }

    void updateL(int l, int r, int idx){
        root = root->updateL(0, n-1, l, r, make_pair(curD, idx));
    }

    void updateR(int l, int r, int idx){
        root = root->updateR(0, n-1, l, r, make_pair(curD, idx));
    }

    vector<int> query(int l, int r, int d){
        /// 정수 3개의 배열을 리턴
        vector<int> ret (3);
        ret[0] = history[d]->query(0, n-1, l, r);
        ret[1] = history[d]->queryL(0, n-1, l).second;
        ret[2] = history[d]->queryR(0, n-1, r).second;

        return ret;
    }

    int queryL(int x, int d){
        return history[d]->queryL(0, n-1, x).second;
    }

    int queryR(int x, int d){
        return history[d]->queryR(0, n-1, x).second;
    }
} tree;

struct Interval{
    int s, e, diff, idx;
    Interval(int s, int e, int diff, int idx): s(s), e(e), diff(diff), idx(idx){}
};

struct xOrder {
    bool operator() (const Interval &l, const Interval &r)const{
        return l.s < r.s;
    }
};

struct diffOrder {
    bool operator() (const Interval &l, const Interval &r)const{
        if(abs(l.diff) != abs(r.diff)) return abs(l.diff) < abs(r.diff);
        return l.s < r.s;
    }
};

set<Interval, xOrder> xSet;
set<Interval, diffOrder> diffSet;

int sgn(int x){
    return x > 0 ? 1 : x == 0 ? 0 : -1;
}

vector<int> diffScale;
vector<Interval> intervals;
int leftInt[200002], rightInt[200002];

void makeInitialIntervals(){ /// 초기의 구간들을 계산한다
    tree.init(n);

    int prv = 0;
    while(prv < n-1){
        int j = prv;
        while(j+1<n && sgn(arr[j] - arr[prv]) * sgn(arr[j+1] - arr[j]) >= 0) j++;
        if(arr[j] == arr[prv]) break;

        /// 현재 찾은 구간을 셋에 집어넣는다
        int idx = (int)intervals.size();
        Interval tmp = Interval(prv, j, arr[j] - arr[prv], idx);
        intervals.push_back(tmp);
        xSet.insert(tmp);
        diffSet.insert(tmp);

        /// 현재 찾은 구간을 트리에 업데이트한다
        tree.update(prv, 1);
        tree.updateL(prv+1, j, idx);
        tree.updateR(prv, j-1, idx);

        prv = j;
    }
    diffScale.push_back(0);
    leftInt[tree.curD] = (xSet.empty() ? -1 : xSet.begin()->idx);
    rightInt[tree.curD] = (xSet.empty() ? -1 : xSet.rbegin()->idx);
    tree.nextD();
}

void calculateChanges(){ /// D가 커짐에 따라 생기는 변화들을 구한다
    while((int)diffSet.size()){
        int D = abs(diffSet.begin()->diff); /// 현재의 차이값
        while(abs((int)diffSet.begin()->diff) == D){ /// 해당하는 차이의 모든 구간을 처리한다.
            /// 구간을 뽑는다
            Interval p = *diffSet.begin();
            diffSet.erase(diffSet.begin());

            /// Case 1. 직전에 구간이 존재하지 않음
            if(xSet.begin()->s == p.s){ /// 이 구간은 그냥 삭제한다.
                xSet.erase(xSet.begin());
                tree.updateL(0, p.e, -1);
            }
            /// Case 2. 직후에 구간이 존재하지 않음
            else if(xSet.rbegin()->s == p.s){ /// 이 구간 역시 그냥 삭제한다.
                xSet.erase(prev(xSet.end()));
                tree.updateR(p.s, n-1, -1);
            }
            /// Case 3. 양쪽 모두 잘 존재함
            else{ /// 새로운 구간을 만들어 준다.
                auto it = xSet.find(p);
                int ns = prev(it)->s, ne = next(it)->e;
                int idx = (int)intervals.size();
                Interval np = Interval(ns, ne, arr[ne] - arr[ns], idx);
                intervals.push_back(np);

                /// 셋에 반영한다.
                diffSet.erase(*prev(it)), diffSet.erase(*next(it));
                xSet.erase(prev(it)), xSet.erase(next(it));
                xSet.erase(it);
                xSet.insert(np), diffSet.insert(np);

                /// 트리에 반영한다
                tree.update(p.s, -1);
                tree.update(p.e, -1);
                tree.updateL(np.s+1, np.e, idx);
                tree.updateR(np.s, np.e-1, idx);
            }
        }

        diffScale.push_back(D+1);
        leftInt[tree.curD] = (xSet.empty() ? -1 : xSet.begin()->idx);
        rightInt[tree.curD] = (xSet.empty() ? -1 : xSet.rbegin()->idx);
        tree.nextD();
    }
    leftInt[tree.curD] = rightInt[tree.curD] = -1;
}

void calculateIntervals(){
    makeInitialIntervals();
    calculateChanges();
}

int max_towers(int L, int R, int D){
    int Rd = D;
    D = upper_bound(diffScale.begin(), diffScale.end(), D) - diffScale.begin() - 1;
    if(leftInt[D] == -1) return 1; /// 현 시기에 구간이 하나도 없는 경우

    vector<int> response = tree.query(L, R, D);
    int sum = response[0], ql = response[1], qr = response[2];

    /// 구간 시작점이 하나라도 있는 경우
    if(sum){
        /// 1. 완전히 속하는 구간의 개수를 센다.
        /// 왼쪽 끝 부분은 예외가 생기지 않는다.
        /// 오른쪽 끝 부분은 맨 오른쪽 점이 어느 구간에 포함되지 않았을 때를 제외하고는 1을 제외해야 한다.
        if(qr != -1) sum--; /// 시작점이

        /// 2. 왼쪽 끝을 본다.
        /// 위에서 본 구간 중 맨 왼쪽 구간을 찾는다.
        int lint = (ql == -1) ? leftInt[D] : tree.queryL(intervals[ql].e+1, D);
        assert(lint != -1);
        int lDir = sgn(intervals[lint].diff);
        bool lMore = abs(segtree.queryMin(1, 0, n-1, L, intervals[lint].s) - arr[intervals[lint].s]) >= Rd;

        /// 3. 오른쪽 끝을 본다
        /// 위에서 본 구간 중 맨 오른쪽 구간을 찾는다.
        int rint = (qr == -1) ? rightInt[D] : tree.queryR(intervals[qr].s-1, D);
        assert(rint != -1);
        int rDir = sgn(intervals[rint].diff);
        bool rMore = abs(segtree.queryMin(1, 0, n-1, intervals[rint].e, R) - arr[intervals[rint].e]) >= Rd;

        /// 4. 답을 계산한다
        int base = (sum - (sum >= 2 && lDir == -1)) / 2;
        if(sum == 0){
            if(lDir == -1 && lMore && rDir == 1 && rMore) return 2;
            else return 1;
        }
        if(lDir == -1 && lMore) base++;
        if(rDir == 1 && rMore) base++;
        return base+1;
    }

    /// 구간 시작점이 하나도 없는 경우
    return 1;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 608 ms 9144 KB Output is correct
2 Correct 963 ms 14500 KB Output is correct
3 Correct 1004 ms 14520 KB Output is correct
4 Correct 988 ms 14448 KB Output is correct
5 Correct 1010 ms 14392 KB Output is correct
6 Correct 915 ms 14408 KB Output is correct
7 Correct 820 ms 14416 KB Output is correct
8 Correct 1 ms 1872 KB Output is correct
9 Correct 2 ms 2128 KB Output is correct
10 Correct 1 ms 2128 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 8 ms 6168 KB Output is correct
3 Correct 7 ms 6196 KB Output is correct
4 Correct 9 ms 8144 KB Output is correct
5 Correct 10 ms 8156 KB Output is correct
6 Correct 9 ms 8144 KB Output is correct
7 Correct 12 ms 8232 KB Output is correct
8 Correct 2 ms 2128 KB Output is correct
9 Correct 1 ms 2128 KB Output is correct
10 Correct 2 ms 2128 KB Output is correct
11 Correct 1 ms 2128 KB Output is correct
12 Correct 1 ms 1872 KB Output is correct
13 Correct 2 ms 2080 KB Output is correct
14 Correct 2 ms 2104 KB Output is correct
15 Correct 9 ms 6352 KB Output is correct
16 Correct 11 ms 8116 KB Output is correct
17 Correct 10 ms 8140 KB Output is correct
18 Correct 1 ms 2128 KB Output is correct
19 Correct 1 ms 2128 KB Output is correct
20 Correct 7 ms 6224 KB Output is correct
21 Correct 10 ms 8144 KB Output is correct
22 Correct 10 ms 8144 KB Output is correct
23 Correct 1 ms 2128 KB Output is correct
24 Correct 2 ms 2128 KB Output is correct
25 Incorrect 4 ms 3684 KB 1st lines differ - on the 1st token, expected: '34', found: '36'
26 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 8 ms 6168 KB Output is correct
3 Correct 7 ms 6196 KB Output is correct
4 Correct 9 ms 8144 KB Output is correct
5 Correct 10 ms 8156 KB Output is correct
6 Correct 9 ms 8144 KB Output is correct
7 Correct 12 ms 8232 KB Output is correct
8 Correct 2 ms 2128 KB Output is correct
9 Correct 1 ms 2128 KB Output is correct
10 Correct 2 ms 2128 KB Output is correct
11 Correct 1 ms 2128 KB Output is correct
12 Correct 1 ms 1872 KB Output is correct
13 Correct 2 ms 2080 KB Output is correct
14 Correct 2 ms 2104 KB Output is correct
15 Correct 9 ms 6352 KB Output is correct
16 Correct 11 ms 8116 KB Output is correct
17 Correct 10 ms 8140 KB Output is correct
18 Correct 1 ms 2128 KB Output is correct
19 Correct 1 ms 2128 KB Output is correct
20 Correct 7 ms 6224 KB Output is correct
21 Correct 10 ms 8144 KB Output is correct
22 Correct 10 ms 8144 KB Output is correct
23 Correct 1 ms 2128 KB Output is correct
24 Correct 2 ms 2128 KB Output is correct
25 Incorrect 4 ms 3684 KB 1st lines differ - on the 1st token, expected: '34', found: '36'
26 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1484 ms 310764 KB Output is correct
2 Correct 1684 ms 314092 KB Output is correct
3 Correct 1607 ms 313876 KB Output is correct
4 Correct 1830 ms 454356 KB Output is correct
5 Correct 1894 ms 454456 KB Output is correct
6 Correct 1878 ms 454428 KB Output is correct
7 Correct 1947 ms 454368 KB Output is correct
8 Correct 1103 ms 14416 KB Output is correct
9 Correct 940 ms 14408 KB Output is correct
10 Correct 1049 ms 14428 KB Output is correct
11 Correct 947 ms 14512 KB Output is correct
12 Correct 901 ms 14380 KB Output is correct
13 Correct 920 ms 14416 KB Output is correct
14 Correct 1 ms 1872 KB Output is correct
15 Correct 1 ms 2128 KB Output is correct
16 Correct 1 ms 2128 KB Output is correct
17 Correct 581 ms 313544 KB Output is correct
18 Correct 881 ms 454416 KB Output is correct
19 Correct 832 ms 454576 KB Output is correct
20 Correct 29 ms 14392 KB Output is correct
21 Correct 19 ms 14500 KB Output is correct
22 Correct 573 ms 313648 KB Output is correct
23 Correct 821 ms 454348 KB Output is correct
24 Correct 819 ms 454360 KB Output is correct
25 Correct 19 ms 14512 KB Output is correct
26 Correct 27 ms 14512 KB Output is correct
27 Correct 7 ms 6292 KB Output is correct
28 Correct 14 ms 8144 KB Output is correct
29 Correct 10 ms 8144 KB Output is correct
30 Correct 1 ms 2128 KB Output is correct
31 Correct 1 ms 2128 KB Output is correct
32 Correct 7 ms 6224 KB Output is correct
33 Correct 10 ms 8144 KB Output is correct
34 Correct 9 ms 8128 KB Output is correct
35 Correct 1 ms 2128 KB Output is correct
36 Correct 1 ms 2128 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 418 ms 69072 KB 3rd lines differ - on the 1st token, expected: '150', found: '153'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 8 ms 6168 KB Output is correct
3 Correct 7 ms 6196 KB Output is correct
4 Correct 9 ms 8144 KB Output is correct
5 Correct 10 ms 8156 KB Output is correct
6 Correct 9 ms 8144 KB Output is correct
7 Correct 12 ms 8232 KB Output is correct
8 Correct 2 ms 2128 KB Output is correct
9 Correct 1 ms 2128 KB Output is correct
10 Correct 2 ms 2128 KB Output is correct
11 Correct 1 ms 2128 KB Output is correct
12 Correct 1 ms 1872 KB Output is correct
13 Correct 2 ms 2080 KB Output is correct
14 Correct 2 ms 2104 KB Output is correct
15 Correct 9 ms 6352 KB Output is correct
16 Correct 11 ms 8116 KB Output is correct
17 Correct 10 ms 8140 KB Output is correct
18 Correct 1 ms 2128 KB Output is correct
19 Correct 1 ms 2128 KB Output is correct
20 Correct 7 ms 6224 KB Output is correct
21 Correct 10 ms 8144 KB Output is correct
22 Correct 10 ms 8144 KB Output is correct
23 Correct 1 ms 2128 KB Output is correct
24 Correct 2 ms 2128 KB Output is correct
25 Incorrect 4 ms 3684 KB 1st lines differ - on the 1st token, expected: '34', found: '36'
26 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 608 ms 9144 KB Output is correct
2 Correct 963 ms 14500 KB Output is correct
3 Correct 1004 ms 14520 KB Output is correct
4 Correct 988 ms 14448 KB Output is correct
5 Correct 1010 ms 14392 KB Output is correct
6 Correct 915 ms 14408 KB Output is correct
7 Correct 820 ms 14416 KB Output is correct
8 Correct 1 ms 1872 KB Output is correct
9 Correct 2 ms 2128 KB Output is correct
10 Correct 1 ms 2128 KB Output is correct
11 Correct 2 ms 2640 KB Output is correct
12 Correct 8 ms 6168 KB Output is correct
13 Correct 7 ms 6196 KB Output is correct
14 Correct 9 ms 8144 KB Output is correct
15 Correct 10 ms 8156 KB Output is correct
16 Correct 9 ms 8144 KB Output is correct
17 Correct 12 ms 8232 KB Output is correct
18 Correct 2 ms 2128 KB Output is correct
19 Correct 1 ms 2128 KB Output is correct
20 Correct 2 ms 2128 KB Output is correct
21 Correct 1 ms 2128 KB Output is correct
22 Correct 1 ms 1872 KB Output is correct
23 Correct 2 ms 2080 KB Output is correct
24 Correct 2 ms 2104 KB Output is correct
25 Correct 9 ms 6352 KB Output is correct
26 Correct 11 ms 8116 KB Output is correct
27 Correct 10 ms 8140 KB Output is correct
28 Correct 1 ms 2128 KB Output is correct
29 Correct 1 ms 2128 KB Output is correct
30 Correct 7 ms 6224 KB Output is correct
31 Correct 10 ms 8144 KB Output is correct
32 Correct 10 ms 8144 KB Output is correct
33 Correct 1 ms 2128 KB Output is correct
34 Correct 2 ms 2128 KB Output is correct
35 Incorrect 4 ms 3684 KB 1st lines differ - on the 1st token, expected: '34', found: '36'
36 Halted 0 ms 0 KB -