Submission #719426

#	Time	Username	Problem	Language	Result	Execution time	Memory
719426		somethingnew	Radio Towers (IOI22_towers)	C++17	56 / 100	2058 ms	2120 KiB

towers

//  ↘ ⬇ ⬇ ⬇ ⬇ ⬇ ↙
//  ➡ @roadfromroi ⬅
//  ↗ ⬆ ⬆ ⬆ ⬆ ⬆ ↖
#include <iostream>
#include "vector"
#include "algorithm"
#include "numeric"
#include "climits"
#include "iomanip"
#include "bitset"
#include "cmath"
#include "map"
#include "deque"
#include "array"
#include "set"
#include "queue"
#include "towers.h"
#define all(x) x.begin(), x.end()
using namespace std;

vector<int> h;
int dd;
struct node {
    int lval;
    int rval;
    int cnt;
    int lstenka;
    int rstenka;
    node() {}
    node(int x) {
        lval = rval = x;
        cnt = 1;
        lstenka = 0;
        rstenka = 0;
    }
    void swapchik() {
        swap(lval, rval);
        swap(lstenka, rstenka);
    }
};

node merge(node a, node b) {
    bool swp = 0;
    if (a.rval > b.lval) {
        swp = 1;
        a.swapchik();
        b.swapchik();
        swap(a, b);
    }
    node c = a;
    if (max(a.rstenka, b.lstenka) - dd >= max(a.rval, b.lval)) {
        c.cnt = a.cnt + b.cnt;
        c.rstenka = b.rstenka;
        c.rval = b.rval;
        if (swp)
            c.swapchik();
        return c;
    } else {
        c.cnt = a.cnt + b.cnt - 1;
        if (b.cnt != 1) {
            c.rstenka = b.rstenka;
            c.rval = b.rval;
        } else {
          //  cout << c.rstenka << ' ';
            c.rstenka = max(c.rstenka, max(b.rstenka, max(b.lstenka, b.rval)));
          //  cout << c.rstenka << '\n';
        }
        if (swp)
            c.swapchik();
        return c;
    }
}
struct kornihunka{
    vector<int> elems;
    node nd;
    void push(int x) {
        elems.push_back(x);
    }
    node get(int l, int r) {
        r = min(r, (int)elems.size() - 1);
        node nres(elems[l]);
        for (int i = l + 1; i <= r; ++i) {
            nres = merge(nres, node(elems[i]));
        }
        return nres;
    }
    void calc() {
        nd = node(elems[0]);
        for (int i = 1; i < elems.size(); ++i) {
            nd = merge(nd, elems[i]);
        }
    }
    node getnode() {
        return nd;
    }
};
int K = 337;
vector<kornihunka> vecnode;
int calcedd = 0;
void init(int n, vector<int> hh) {
    h = hh;
    vecnode.assign((n + K - 1) / K, {});
    for (int i = 0; i < n; ++i) {
        vecnode[i/K].push(h[i]);
    }
}
int max_towers(int L, int R, int D) {
    node res(2e9);
    if (calcedd != D) {
        if (calcedd != 0)
            exit(1);
        calcedd = D;
        dd = D;
        for (int i = 0; i < vecnode.size(); ++i) {
            vecnode[i].calc();
        }
    }
    if (L / K == R / K) {
   //     cout << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';
        res = merge(res, vecnode[L/K].get(L % K, R % K));
        return res.cnt;
    }
    if (L % K != 0) {
      //  cout << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';
        res = merge(res, vecnode[L/K].get(L % K, K - 1));
        L = L / K * K + K;
    }
    while (L + K <= R + 1) {
        //cout << "TT " << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';
        node res2 = vecnode[L/K].getnode();
        //cout << "TT2 " << res2.lval << ' ' << res2.lstenka << ' ' << res2.cnt << '\n';
        res = merge(res, vecnode[L/K].getnode());
        //cout << "TT3 " << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';

        L += K;
    }
    if (L <= R) {
       // cout << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';
        res = merge(res, vecnode[L/K].get(L % K, R % K));
    }
   // cout << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';
    return res.cnt;
}
/*
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    init(n, a);
    for (int i = 0; i < m; ++i) {
        int q1, q2, q3;
        cin >> q1 >> q2 >> q3;
        cout << max_towers(q1,q2,q3) << '\n';
    }
}*/
/*
7 1
10 20 60 40 50 30 70
0 6 17
 */

Compilation message (stderr)

towers.cpp: In member function 'void kornihunka::calc()':
towers.cpp:89:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for (int i = 1; i < elems.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:114:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<kornihunka>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         for (int i = 0; i < vecnode.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~~
towers.cpp:130:14: warning: variable 'res2' set but not used [-Wunused-but-set-variable]
  130 |         node res2 = vecnode[L/K].getnode();
      |              ^~~~

• 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