제출 #835287

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
835287		Wael	송신탑 (IOI22_towers)	C++17	100 / 100	1830 ms	675748 KiB

towers

#include <bits/stdc++.h>
using namespace std;
#include "towers.h"
typedef int ll;
int const M = 2e5 + 10 , lg = 20 , Mx = M * 31;
int n , s[M] , Size = (1 << 30) , sparse[M][lg + 2] , Left[M] , Right[M];

struct sgtree {

    int Left[Mx] , Right[Mx] , cur = 1;
    vector<ll>elem[Mx];

    inline void Init() {
        for(int i = 0 ; i < Mx ; ++i) Left[i] = Right[i] = 0;
    } 

    inline void Update(int i , int val , int node = 1 , int lx = 1 , int rx = Size) {
        if(lx == rx) {
            elem[node].push_back(val);
            return;
        }
        int mid = (lx + rx) / 2;
        if(i <= mid) {
            if(Left[node] == 0) Left[node] = ++cur;
            Update(i , val , Left[node] , lx , mid);
        } else {
            if(Right[node] == 0) Right[node] = ++cur;
            Update(i , val , Right[node] , mid + 1 , rx);
        }
    }

    inline void Build(int node = 1 , int lx = 1 , int rx = Size) {
        if(node == 0 || lx == rx) return;
        int mid = (lx + rx) / 2;
        Build(Left[node] , lx , mid);
        Build(Right[node] , mid + 1 , rx);
        int l = 0 , r = 0;
        while(l < elem[Left[node]].size() || r < elem[Right[node]].size()) {
            if(l == elem[Left[node]].size()) {
                elem[node].push_back(elem[Right[node]][r]);
                ++r;
            }
            else if(r == elem[Right[node]].size()) {
                elem[node].push_back(elem[Left[node]][l]);
                ++l;
            }
            else if(elem[Left[node]][l] < elem[Right[node]][r]) {
                elem[node].push_back(elem[Left[node]][l]);
                ++l;
            }
            else {
                elem[node].push_back(elem[Right[node]][r]);
                ++r;
            }
        }
    }

    inline ll GetAfter(int i , int k , int node = 1 , int lx = 1 , int rx = Size) {
        if(rx < k || node == 0) return 1e9;
        if(lx >= k) {
            auto it = lower_bound(elem[node].begin() , elem[node].end() , i);
            if(it == elem[node].end()) return 1e9;
            return *it;
        }
        int mid = (lx + rx) / 2;
        return min(GetAfter(i , k , Left[node] , lx , mid) , GetAfter(i , k , Right[node] , mid + 1 , rx));
    }

    inline ll GetBefore(int i , int k , int node = 1 , int lx = 1 , int rx = Size) {
        if(rx < k || node == 0) return 0;
        if(lx >= k) {
            auto it = upper_bound(elem[node].begin() , elem[node].end() , i);
            if(it == elem[node].begin()) return 0;
            return *prev(it);
        }
        int mid = (lx + rx) / 2;
        return max(GetBefore(i , k , Left[node] , lx , mid) , GetBefore(i , k , Right[node] , mid + 1 , rx));
    }

    inline ll GetCount(int l , int r , int k , int node = 1 , int lx = 1 , int rx = Size) {
        if(rx < k || node == 0) return 0;
        if(lx >= k) {
            auto it1 = lower_bound(elem[node].begin() , elem[node].end() , l);
            auto it2 = upper_bound(elem[node].begin() , elem[node].end() , r);
            return it2 - it1;
        }
        int mid = (lx + rx) / 2;
        return GetCount(l , r , k , Left[node] , lx , mid) + GetCount(l , r , k , Right[node] , mid + 1 , rx);
    }
} Tree1 , Tree2 , Tree3;

inline ll GetMax(int l , int r) {
    if(r < l) return 0;
    int Lg = log2(r - l + 1);
    return max(sparse[l][Lg] , sparse[r - (1 << Lg) + 1][Lg]);
}

void init(int N, vector<ll> H) {
    n = N;
    Tree1.Init();
    Tree2.Init();
    Tree3.Init();
    for(int i = 1 ; i <= n ; ++i) s[i] = H[i - 1];
    for(int i = 1 ; i <= n ; ++i) sparse[i][0] = s[i];
    for(int j = 1 ; j <= lg ; ++j) 
     for(int i = 1 ; i <= n ; ++i) {
        int After = min(n , i + (1 << (j - 1)));
        sparse[i][j] = max(sparse[i][j - 1] , sparse[After][j - 1]);
     }

    stack<ll>st;
    for(int i = 1 ; i <= n ; ++i) {
        while(st.size() && s[i] < s[st.top()]) {
            Right[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
    while(st.size()) {
        Right[st.top()] = n + 1;
        st.pop(); 
    }

    for(int i = n ; i >= 1 ; --i) {
        while(st.size() && s[i] < s[st.top()]) {
            Left[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
    while(st.size()) {
        Left[st.top()] = 0;
        st.pop();
    }

    //for(int i = 1 ; i <= n ; ++i) cout << Left[i] << " " << Right[i] << endl;

    for(int i = 1 ; i <= n ; ++i) {
        int max1 = GetMax(Left[i] + 1 , i - 1);
        int max2 = GetMax(i + 1 , Right[i] - 1);
        if(max1 > s[i]) {
            Tree2.Update(max1 - s[i] , i);
        }
        if(max2 > s[i]) {
            Tree1.Update(max2 - s[i] , i);
        }
        if(max1 > s[i] && max2 > s[i]) {
            Tree3.Update(min(max1 , max2) - s[i] , i);
        }
    }
    Tree1.Build();
    Tree2.Build();
    Tree3.Build();
}

int max_towers(int L, int R, int D) {
    int k = D;
    ++L , ++R;
    int l = Tree1.GetAfter(L , k);
    int r = Tree2.GetBefore(R , k);
    if(r < l) return 1;
    int cnt =  Tree3.GetCount(l + 1 , r - 1 , k);
    return cnt + 2;
}

컴파일 시 표준 에러 (stderr) 메시지

towers.cpp: In member function 'void sgtree::Build(int, int, int)':
towers.cpp:38:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         while(l < elem[Left[node]].size() || r < elem[Right[node]].size()) {
      |               ~~^~~~~~~~~~~~~~~~~~~~~~~~~
towers.cpp:38:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         while(l < elem[Left[node]].size() || r < elem[Right[node]].size()) {
      |                                              ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
towers.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             if(l == elem[Left[node]].size()) {
      |                ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
towers.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             else if(r == elem[Right[node]].size()) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 17 / 17
• Subtask 6: 19 / 19
• Subtask 7: 23 / 23