Submission #719695

#	Time	Username	Problem	Language	Result	Execution time	Memory
719695		somethingnew	Radio Towers (IOI22_towers)	C++17	60 / 100	4043 ms	133304 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 merge(node &a, node b) {
    if (a.rval <= b.lval) {
        if (max(a.rstenka, b.lstenka) - dd >= max(a.rval, b.lval)) {
            a.cnt = a.cnt + b.cnt;
            a.rstenka = b.rstenka;
            a.rval = b.rval;
            return;
        } else {
            a.cnt = a.cnt + b.cnt - 1;
            if (b.cnt != 1) {
                a.rstenka = b.rstenka;
                a.rval = b.rval;
            } else {
                //  cout << c.rstenka << ' ';
                a.rstenka = max(a.rstenka, max(b.rstenka, max(b.lstenka, b.rval)));
                //  cout << c.rstenka << '\n';
            }
            return;
        }
    } else {
        if (max(a.rstenka, b.lstenka) - dd >= max(a.rval, b.lval)) {
            b.cnt = a.cnt + b.cnt;
            b.lstenka = a.lstenka;
            b.lval = a.lval;
            swap(a, b);
            return;
        } else {
            b.cnt = a.cnt + b.cnt - 1;
            if (a.cnt != 1) {
                b.lstenka = a.lstenka;
                b.lval = a.lval;
            } else {
                //  cout << c.rstenka << ' ';
                b.lstenka = max(b.lstenka, max(a.lstenka, max(a.rstenka, a.lval)));
                //  cout << c.rstenka << '\n';
            }
            swap(a, b);
            return;
        }
    }
}
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) {
            merge(nres, node(elems[i]));
        }
        return nres;
    }
    int calc() {
        int incdd = -1;
        nd = node(elems[0]);
        int cc = 1;
        int pr3 = 2e9;
        for (int i = 1; i < elems.size(); ++i) {
            int pr = nd.rval, pr2 = nd.rstenka;
            merge(nd, elems[i]);
            if (nd.cnt != cc) {
                cc = nd.cnt;
                if (incdd == -1)
                    incdd = min(pr2 - dd - pr, pr3 - dd - pr);
                incdd = min(incdd, min(pr2 - dd - pr, pr3 - dd - pr));
                pr3 = pr2;
            }
        }
        incdd = min(incdd, pr3 - dd - nd.rval);
        if (nd.cnt == 1)
            return 0;
        return incdd + 1;
    }
    node getnode() {
        return nd;
    }
};
const int K = 340;
const int N = 100000;
vector<vector<kornihunka>> vecnode;
vector<vector<int>> detki;
int realdetki[N / K + 1][N];
vector<int> alex;
int calcedd = 0;
void init(int n, vector<int> hh) {
    h = hh;
    vecnode.assign((n + K - 1) / K, vector<kornihunka>(K));
    detki.assign((n + K - 1) / K, {});
    for (int i = 0; i < n; ++i) {
        vecnode[i/K][0].push(h[i]);
    }
    for (int i = 0; i < vecnode.size(); ++i) {
        int j = 0;
        int inc = 1;
        dd = 0;
        do {
            dd += inc;
            detki[i].push_back(dd);
            alex.push_back(dd);
            vecnode[i][j + 1] = vecnode[i][j];
            inc = vecnode[i][j].calc();
            j++;
        } while (inc != 0);
    }
    sort(all(alex));
    alex.erase(unique(all(alex)), alex.end());
    for (int i = 0; i < vecnode.size(); ++i) {
        int j = 0;
        for (int pvl = 0; pvl < alex.size(); ++pvl) {
            while (j + 1 != detki[i].size() and detki[i][j + 1] <= alex[pvl]) {
                j++;
            }
            realdetki[i][pvl] = j;
        }
    }
}
int max_towers(int L, int R, int D) {
    node res(2e9);
    dd = D;
    int dvl = upper_bound(all(alex), dd) - alex.begin()-1;
    if (L / K == R / K) {
        //cout << upper_bound(all(detki[L/K]), dd) - detki[L/K].begin()-1 << '\n';
        //     cout << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';
        merge(res, vecnode[L/K][realdetki[L/K][dvl]].get(L % K, R % K));
        return res.cnt;
    }
    if (L % K != 0) {
        //  cout << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';
        merge(res, vecnode[L/K][realdetki[L/K][dvl]].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][0].getnode();
        //cout << "TT2 " << res2.lval << ' ' << res2.lstenka << ' ' << res2.cnt << '\n';
        merge(res, vecnode[L/K][realdetki[L/K][dvl]].getnode());
        //cout << "TT3 " << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';

        L += K;
    }
    if (L <= R) {
        // cout << res.rval << ' ' << res.rstenka << ' ' << res.cnt << '\n';
        merge(res, vecnode[L/K][realdetki[L/K][dvl]].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 'int kornihunka::calc()':
towers.cpp:98:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         for (int i = 1; i < elems.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:132:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<kornihunka> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for (int i = 0; i < vecnode.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~~
towers.cpp:147:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<kornihunka> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |     for (int i = 0; i < vecnode.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~~
towers.cpp:149:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |         for (int pvl = 0; pvl < alex.size(); ++pvl) {
      |                           ~~~~^~~~~~~~~~~~~
towers.cpp:150:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |             while (j + 1 != detki[i].size() and detki[i][j + 1] <= alex[pvl]) {
      |                    ~~~~~~^~~~~~~~~~~~~~~~~~
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:174:14: warning: variable 'res2' set but not used [-Wunused-but-set-variable]
  174 |         node res2 = vecnode[L/K][0].getnode();
      |              ^~~~

• Subtask 1: 4 / 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