oj.uz

Submission #787206

# Submission time Handle Problem Language Result Execution time Memory
787206 2023-07-18T23:01:28 Z MilosMilutinovic Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 35288 KB 
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int L = 22;
int n, a[N], pl[N], pr[N], ord[N], go_l[N], go_r[N];
bool cmp(int i, int j) { return a[i] < a[j]; }
int mx[N][L], logs[N];
int qmx(int l, int r) {
    if (l > r) return (int) -1e9;
    int k = logs[r - l + 1];
    return max(mx[l][k], mx[r - (1 << k) + 1][k]);
}
void buildST() {
    for (int i = 1; i <= n; i++) mx[i][0] = a[i];
    for (int i = 2; i <= n; i++) logs[i] = logs[i >> 1] + 1;
    for (int j = 1; j < L; j++)
        for (int i = 1; i + (1 << j) <= n + 1; i++)
            mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
}
const int M = N * L;
int tsz, ls[M], rs[M], sum[M];
void modify(int& v, int p, int tl, int tr, int i, int x) {
    v = ++tsz;
    ls[v] = ls[p];
    rs[v] = rs[p];
    sum[v] = sum[p] + x;
    if (tl == tr) {
        return;
    }
    int mid = tl + tr >> 1;
    if (i <= mid) {
        modify(ls[v], ls[p], tl, mid, i, x);
    } else {
        modify(rs[v], rs[p], mid + 1, tr, i, x);
    }
}
int query(int v, int tl, int tr, int ql, int qr) {
    if (tl > tr || tl > qr || tr < ql) {
        return 0;
    }
    if (ql <= tl && tr <= qr) {
        return sum[v];
    }
    int mid = tl + tr >> 1;
    return query(ls[v], tl, mid, ql, qr) + query(rs[v], mid + 1, tr, ql, qr);
}
int find_first(int v, int tl, int tr, int p) {
    if (tr < p || !sum[v]) {
        return n + 1;
    }
    if (tl == tr) {
        return sum[v] > 0 ? tl : n + 1;
    }
    int mid = tl + tr >> 1;
    int ans_l = find_first(ls[v], tl, mid, p);
    if (ans_l == n + 1)
        return find_first(rs[v], mid + 1, tr, p);
    else
        return ans_l;
}
int find_last(int v, int tl, int tr, int p) {
    if (tl > p || !sum[v]) {
        return 0;
    }
    if (tl == tr) {
        return sum[v] > 0 ? tl : 0;
    }
    int mid = tl + tr >> 1;
    int ans_r = find_last(ls[v], mid + 1, tr, p);
    if (ans_r == 0)
        return find_last(ls[v], tl, mid, p);
    else
        return ans_r;
}
vector<pair<int, int>> qs;
vector<int> roots;
void init(int N, vector<int> H) {
    n = N;
    for (int i = 1; i <= n; i++) {
        a[i] = H[i - 1];
    }
    go_r[1] = 1;
    for (int i = 2; i <= n; i++) {
        go_r[i] = (a[i - 1] < a[i] ? go_r[i - 1] : i - 1);
    }
    go_l[n] = n;
    for (int i = n - 1; i >= 1; i--) {
        go_l[i] = (a[i + 1] < a[i] ? go_l[i + 1] : i + 1);
    }
    vector <int> stk;
    for (int i = 1; i <= n; i++) {
        while (!stk.empty() && a[stk.back()] > a[i]) stk.pop_back();
        pl[i] = (stk.empty() ? -1 : stk.back());
        stk.push_back(i);
    }
    stk.clear();
    for (int i = n; i >= 1; i--) {
        while (!stk.empty() && a[stk.back()] > a[i]) stk.pop_back();
        pr[i] = (stk.empty() ? -1 : stk.back());
        stk.push_back(i);
    }
    buildST();
    for (int i = 1; i <= n; i++) ord[i] = i;
    sort(ord + 1, ord + n + 1, cmp);
    for (int _i = 2; _i <= n; _i++) {
        int i = ord[_i];
        int D = 1.001e9;
        if (pl[i] != -1) D = min(D, qmx(pl[i] + 1, i) - a[i]);
        if (pr[i] != -1) D = min(D, qmx(i, pr[i] - 1) - a[i]);
        qs.emplace_back(D, i);
    }
    sort(qs.begin(), qs.end());
    roots.push_back(0);
    modify(roots.back(), roots.back(), 1, n, ord[1], 1);
    int sz = (int) qs.size();
    for (int i = sz - 1; i >= 0; i--) {
        int prv = (int) roots.back();
        roots.push_back(0);
        modify(roots.back(), prv, 1, n, qs[i].second, 1);
    }
    reverse(roots.begin(), roots.end());
}
int get_pos(int d) {
    int low = 0, high = (int) qs.size() - 1, res = high + 1;
    while (low <= high) {
        int mid = low + high >> 1;
        if (qs[mid].first >= d) {
            res = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return res;
}
int find_first_bs(int rt, int p) {
    int low = p, high = n, res = n;
    while (low <= high) {
        int mid = low + high >> 1;
        if (query(rt, 1, n, p, mid) > 0) {
            res = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return res;
}
int find_last_bs(int rt, int p) {
    int low = 1, high = p, res = 1;
    while (low <= high) {
        int mid = low + high >> 1;
        if (query(rt, 1, n, mid, p) > 0) {
            res = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return res;
}
int max_towers(int L, int R, int D) {
    if (L == R) {
        return 1;
    }
    ++L; ++R;
    int p = get_pos(D);
    int ans = query(roots[p], 1, n, L, R);
    if (ans == 0) {
        int fl = go_l[L];
        //while (fl + 1 <= R && a[fl] > a[fl + 1]) fl++;
        int fr = go_r[R];
//        while (fr - 1 >= L && a[fr - 1] < a[fr]) fr--;
        if (fl >= fr) {
            return 1;
        }
        return (max(a[fl], a[fr]) <= qmx(fl, fr) - D) ? 2 : 1;
    }
    int l = find_first_bs(roots[p], L);
    int r = find_last_bs(roots[p], R);
    for (int i = L; i < l; i++) {
        if (max(a[i], a[l]) <= qmx(i, l) - D) {
            ans += 1;
            break;
        }
    }
    for (int i = R; i > r; i--) {
        if (max(a[r], a[i]) <= qmx(r, i) - D) {
            ans += 1;
            break;
        }
    }
    return ans;
}

/*
7 3
10 20 60 40 50 30 70
1 5 10
2 2 100
0 6 17


3
1
2
*/

Compilation message

towers.cpp: In function 'void modify(int&, int, int, int, int, int)':
towers.cpp:31:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |     int mid = tl + tr >> 1;
      |               ~~~^~~~
towers.cpp: In function 'int query(int, int, int, int, int)':
towers.cpp:45:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |     int mid = tl + tr >> 1;
      |               ~~~^~~~
towers.cpp: In function 'int find_first(int, int, int, int)':
towers.cpp:55:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |     int mid = tl + tr >> 1;
      |               ~~~^~~~
towers.cpp: In function 'int find_last(int, int, int, int)':
towers.cpp:69:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |     int mid = tl + tr >> 1;
      |               ~~~^~~~
towers.cpp: In function 'int get_pos(int)':
towers.cpp:127:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  127 |         int mid = low + high >> 1;
      |                   ~~~~^~~~~~
towers.cpp: In function 'int find_first_bs(int, int)':
towers.cpp:140:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  140 |         int mid = low + high >> 1;
      |                   ~~~~^~~~~~
towers.cpp: In function 'int find_last_bs(int, int)':
towers.cpp:153:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  153 |         int mid = low + high >> 1;
      |                   ~~~~^~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 20468 KB Output is correct
2 Incorrect 694 ms 35288 KB 59242nd lines differ - on the 1st token, expected: '2', found: '1'
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 848 KB Output is correct
3 Correct 1 ms 848 KB Output is correct
4 Correct 1 ms 848 KB Output is correct
5 Correct 2 ms 848 KB Output is correct
6 Correct 2 ms 828 KB Output is correct
7 Correct 1 ms 848 KB Output is correct
8 Correct 1 ms 848 KB Output is correct
9 Correct 1 ms 848 KB Output is correct
10 Correct 1 ms 848 KB Output is correct
11 Correct 1 ms 848 KB Output is correct
12 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 848 KB Output is correct
3 Correct 1 ms 848 KB Output is correct
4 Correct 1 ms 848 KB Output is correct
5 Correct 2 ms 848 KB Output is correct
6 Correct 2 ms 828 KB Output is correct
7 Correct 1 ms 848 KB Output is correct
8 Correct 1 ms 848 KB Output is correct
9 Correct 1 ms 848 KB Output is correct
10 Correct 1 ms 848 KB Output is correct
11 Correct 1 ms 848 KB Output is correct
12 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1278 ms 34572 KB Output is correct
2 Correct 1499 ms 34844 KB Output is correct
3 Correct 1468 ms 34876 KB Output is correct
4 Correct 1662 ms 34820 KB Output is correct
5 Correct 1591 ms 34796 KB Output is correct
6 Correct 1630 ms 34816 KB Output is correct
7 Correct 1527 ms 34940 KB Output is correct
8 Correct 709 ms 35264 KB Output is correct
9 Correct 628 ms 35244 KB Output is correct
10 Execution timed out 4081 ms 35112 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 8048 KB Output is correct
2 Correct 1164 ms 34892 KB Output is correct
3 Correct 1171 ms 34876 KB Output is correct
4 Correct 1186 ms 34876 KB Output is correct
5 Correct 1111 ms 34840 KB Output is correct
6 Correct 1200 ms 34796 KB Output is correct
7 Correct 1215 ms 34832 KB Output is correct
8 Execution timed out 4077 ms 35248 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 848 KB Output is correct
3 Correct 1 ms 848 KB Output is correct
4 Correct 1 ms 848 KB Output is correct
5 Correct 2 ms 848 KB Output is correct
6 Correct 2 ms 828 KB Output is correct
7 Correct 1 ms 848 KB Output is correct
8 Correct 1 ms 848 KB Output is correct
9 Correct 1 ms 848 KB Output is correct
10 Correct 1 ms 848 KB Output is correct
11 Correct 1 ms 848 KB Output is correct
12 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 20468 KB Output is correct
2 Incorrect 694 ms 35288 KB 59242nd lines differ - on the 1st token, expected: '2', found: '1'
3 Halted 0 ms 0 KB -