제출 #1068676

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1068676		n1k	송신탑 (IOI22_towers)	C++17	0 / 100	884 ms	13012 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct V{
    int lb=0, rb=0;
	ll mx = 0;
    V *l=nullptr, *r=nullptr;
    V(){};
    V(int lb_, int rb_){lb=lb_, rb=rb_;};
    void ext(){
        if(lb!=rb and not l){
            int mb=(lb+rb)/2;
            l=new V(lb, mb);
            r=new V(mb+1, rb);
        }
    }
    void upd(int id, ll x){
        if(lb==rb and lb==id){
			mx = x;
        }
        ext();
        if(l){
            if(id<=l->rb){
                l->upd(id, x);
            }else{
                r->upd(id, x);
            }
			mx = max(l->mx, r->mx);
        }
    }
    ll qry(int lo, int hi){
        if(lo<=lb and rb<=hi){
            return mx;
        }
        if(hi<lb or rb<lo) return 0;
        ext();
        return max(l->qry(lo, hi), r->qry(lo, hi));
    }
};


vector<int> sl, sr;
vector<ll> order;

vector<int> get(vector<int> h){
	vector<int> sl(h.size());
	vector<pair<int, int>> st;
	for(int i=0; i<h.size(); i++){
		while(st.size() and st.back().first>h[i]){
			st.pop_back();
		}
		if(st.empty()){
			sl[i]=i;
		}else{
			sl[i]=st.back().second;
		}
		st.push_back({h[i], i});
	}
	return sl;
}

void init(int N, std::vector<int> H) {
	order.clear();

	sl = get(H);
	reverse(H.begin(), H.end());
	sr = get(H);
	reverse(H.begin(), H.end());
	reverse(sr.begin(), sr.end());
	V seg(0, N-1);
	for(int i=0; i<sr.size(); i++){
		seg.upd(i, H[i]);
		sr[i]=N-sr[i]-1;
	}
	for(int i=0; i<N; i++){
		ll minh = int(1e9) + 5;
		if(sl[i]!=i){
			minh = min(minh, seg.qry(sl[i]+1, i));
		}
		if(sr[i]!=i){
			minh = min(minh, seg.qry(i, sr[i]-1));
		}
		order.push_back(minh - H[i]);
	}	
	sort(order.begin(), order.end());
	for(auto x:order) cerr<<x<<" ";cerr<<endl;
}

int max_towers(int L, int R, int D) {
	return order.end() - lower_bound(order.begin(), order.end(), D);
}

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

towers.cpp: In function 'std::vector<int> get(std::vector<int>)':
towers.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i=0; i<h.size(); i++){
      |               ~^~~~~~~~~
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:75:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for(int i=0; i<sr.size(); i++){
      |               ~^~~~~~~~~~
towers.cpp:90:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   90 |  for(auto x:order) cerr<<x<<" ";cerr<<endl;
      |  ^~~
towers.cpp:90:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   90 |  for(auto x:order) cerr<<x<<" ";cerr<<endl;
      |                                 ^~~~

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