Submission #835139

#	Time	Username	Problem	Language	Result	Execution time	Memory
835139		gagik_2007	Radio Towers (IOI22_towers)	C++17	14 / 100	830 ms	3940 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=100007;
ll n,m,k;
vector<int>a;
vector<int>d;
struct Node{
    int sum;
    Node():sum(0){}
    void bld(int vl){
        sum=vl;
    }
    void join(const Node& lft, const Node& rgh){
        sum=lft.sum+rgh.sum;
    }
};
Node t[4*N];

void build(int v, int tl, int tr){
    if(tl==tr){
        t[v].bld(d[tl]);
    }
    else{
        int tm=(tl+tr)/2;
        build(2*v,tl,tm);
        build(2*v+1,tm+1,tr);
        t[v].join(t[2*v],t[2*v+1]);
    }
}

int get_sum(int v, int tl, int tr, int l, int r){
    if(l>r)return 0;
    if(tl==l&&tr==r)return t[v].sum;
    else{
        int tm=(tl+tr)/2;
        return get_sum(2*v,tl,tm,l,min(tm,r))+
            get_sum(2*v+1,tm+1,tr,max(tm+1,l),r);
    }
}

void init(int NN, vector<int> H) {
    n=NN;
    a=H;
    a.insert(a.begin(),MOD);
    a.push_back(MOD);
    for(int i=1;i<=n;i++){
        if(a[i]<a[i+1]&&a[i]<a[i-1])d.push_back(1);
        else d.push_back(0);
    }
    build(1,0,n-1);
}

int max_towers(int L, int R, int D) {
    if(L==R)return 1;
    int res=get_sum(1,0,n-1,L,R);
    if(a[L+1]<a[L+2]&&a[L+1]>a[L])res++;
    if(a[R+1]<a[R]&&a[R+1]>a[R+2])res++;
    return res;
}

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