Submission #848810

#	Time	Username	Problem	Language	Result	Execution time	Memory
848810		Itamar	Radio Towers (IOI22_towers)	C++17	56 / 100	1104 ms	14144 KiB

towers

#include <vector>
#include <cassert>
#include <cstdio>

#include <vector>
using namespace std;
#define vi vector<int>
#include <set>
vi st;
const int siz = 1e5;
int h[siz];
int d;
#define pi pair<int,int>
#pragma warning(disable : 4996)
struct node {
    int l, r, mid, maxi,ans,repl,repr;
    node* sl, * sr,*t=NULL;
    node(int li, int ri) {
        l = li, r = ri, mid = (l + r) / 2;
        if (l < r) {
            sl = new node(l, mid);
            sr = new node(mid + 1, r);
            maxi = max(sl->maxi, sr->maxi);
        }
        else {
            maxi = h[l];
            ans = 1;
            repl = l, repr=l;
        }
    }
    int qm(int a, int b) {
        if (a > b)return 0;
        if (a > r || b < l)return 0;
        if (a <= l && b >= r)return maxi;
        return max(sl->qm(a, b), sr->qm(a, b));
    }
    void calc(node* top) {
        t = top;
        if (l < r) {
            sl->calc(top), sr->calc(top);
            int l1 = sl->repr, r1 = sr->repl;
            if (t->qm(l1 + 1, r1 - 1) - d >= max(h[l1], h[r1])) {
                ans = sl->ans + sr->ans;
                repl = sl->repl;
                repr = sr->repr;
            }
            else {
                ans = sl->ans - 1 + sr->ans;
                if (sl->repl == l1 && h[l1] > h[r1]) {
                    repl = sr->repl, repr = sr->repr;
                }
                else if (r1 == sr->repr && h[r1] > h[l1]) {
                    repl = sl->repl, repr = sl->repr;
                }
                else {
                    repl = sl->repl, repr = sr->repr;
                }
            }
        }
    }
    int query(int a, int b, int &rep) {
        if (a > r || b < l)return 0;
        if (a <= l && b >= r) {
            if (rep != -1) {
                int l1 = rep, r1 = repl;
                if (t->qm(l1 + 1, r1 - 1) - d >= max(h[l1], h[r1])) {
                    rep = repr;
                    return ans;
                }
                else {
                    if (repl != repr || h[repl] < h[rep]) {
                        rep = repr;
                    }
                    return ans - 1;
                }
            }
            else {
                rep = repr;
                return ans;
            }
        }
        else {
            return sl->query(a, b, rep) + sr->query(a, b, rep);
        }
    }
};
node* seg;
void init(int N, std::vector<int> H) {
    for (int i = 0; i < N; i++)h[i] = H[i];
    seg = new node(0, N - 1);
    /*set<int> s;
    multiset<pi> d;
    for (int i = 0; i < N; i++)s.insert(i);
    for (int i = 0; i < N; i++)d.insert({ 0,i });
    while (s.size()>1) {
        auto it = d.begin(); pi p = *it;
        if(d.fi)
    }*/
}
bool f = 0;
int max_towers(int L, int R, int D) {
    if (f == 0) {
        f = 1;
        d = D;
        seg->calc(seg);
    }
    int k = -1;
    return seg->query(L, R, k);
}
/*
int main() {
    int N, Q;
    assert(2 == scanf("%d %d", &N, &Q));
    std::vector<int> H(N);
    for (int i = 0; i < N; ++i) {
        assert(1 == scanf("%d", &H[i]));
    }
    init(N, H);

    for (int i = 0; i < Q; ++i) {
        int L, R, D;
        assert(3 == scanf("%d %d %d", &L, &R, &D));
        printf("%d\n", max_towers(L, R, D));
    }
    return 0;
}*/

Compilation message (stderr)

towers.cpp:14: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
   14 | #pragma warning(disable : 4996)
      |

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