oj.uz

Submission #1059767

# Submission time Handle Problem Language Result Execution time Memory
1059767 2024-08-15T08:03:36 Z becaido Radio Towers (IOI22_towers) C++17
17 / 100
 811 ms 12020 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "towers.h"
#else
#include "stub.cpp"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int INF = 2e9 + 1;
const int SIZE = 1e5 + 5;

int n;
int a[SIZE], ty[SIZE];
vector<pair<int, int>> ans;

void init(int N, vector<int> H) {
    n = N;
    if (n == 1) return;
    FOR (i, 1, n) a[i] = H[i - 1];
    FOR (i, 1, n) {
        if ((i == 1 || a[i] < a[i - 1]) && (i == n || a[i] < a[i + 1])) ty[i] = 1;
        if ((i == 1 || a[i] > a[i - 1]) && (i == n || a[i] > a[i + 1])) ty[i] = 2;
    }
    set<int> s;
    multiset<pair<int, int>> ms;
    for (int i = 1, x = 1; i <= n; i++) if (ty[i] == x) {
        s.insert(i);
        x ^= 3;
    }
    if (ty[*s.rbegin()] == 2) s.erase(*s.rbegin());
    a[0] = a[n + 1] = INF;
    s.insert(0), s.insert(n + 1);
    ans.pb(0, s.size() / 2);
    bool f = 0;
    for (auto it = s.begin(); it != s.end(); it++) {
        f ^= 1;
        if (f == 0) continue;
        int i = *it;
        if (it != s.begin()) {
            int l = *prev(it);
            ms.emplace(a[i] - a[l], i);
        }
        if (next(it) != s.end()) {
            int r = *next(it);
            ms.emplace(a[i] - a[r], i);
        }
    }
    while (s.size() > 3) {
        int d = ms.begin()->F;
        while (ms.size() && ms.begin()->F == d) {
            auto [_, i] = *ms.begin();
            auto it = s.lower_bound(i), lit = prev(it), rit = next(it);
            int l = *lit, r = *rit;
            int il = *prev(lit), ir = *next(rit);
            if (a[l] > a[r]) {
                ms.erase(ms.find({a[i] - a[l], i}));
                ms.erase(ms.find({a[il] - a[l], il}));
                if (a[i] < a[il]) {
                    ms.erase({a[i] - a[r], i});
                    ms.emplace(a[il] - a[r], il);
                    s.erase(i);
                } else {
                    int j = *prev(s.find(il));
                    ms.erase(ms.find({a[il] - a[j], il}));
                    ms.emplace(a[i] - a[j], i);
                    s.erase(il);
                }
                s.erase(l);
            } else {
                ms.erase(ms.find({a[i] - a[r], i}));
                ms.erase(ms.find({a[ir] - a[r], ir}));
                if (a[i] < a[ir]) {
                    ms.erase({a[i] - a[l], i});
                    ms.emplace(a[ir] - a[l], ir);
                    s.erase(i);
                } else {
                    int j = *next(s.find(ir));
                    ms.erase(ms.find({a[ir] - a[j], ir}));
                    ms.emplace(a[i] - a[j], i);
                    s.erase(ir);
                }
                s.erase(r);
            }
        }
        ans.pb(d + 1, s.size() / 2);
    }
}

int max_towers(int L, int R, int D) {
    L++, R++;
    if (L == R) return 1;
    int i = lower_bound(ans.begin(), ans.end(), make_pair(D + 1, 0)) - ans.begin() - 1;
    return ans[i].S;
}

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

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 249 ms 1112 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '131'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '131'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 493 ms 8524 KB 1st lines differ - on the 1st token, expected: '11903', found: '33010'
2 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 2424 KB Output is correct
2 Correct 729 ms 8896 KB Output is correct
3 Correct 682 ms 8824 KB Output is correct
4 Correct 750 ms 11980 KB Output is correct
5 Correct 811 ms 11980 KB Output is correct
6 Correct 753 ms 11964 KB Output is correct
7 Correct 745 ms 12020 KB Output is correct
8 Correct 644 ms 1368 KB Output is correct
9 Correct 602 ms 1368 KB Output is correct
10 Correct 598 ms 1624 KB Output is correct
11 Correct 571 ms 1624 KB Output is correct
12 Correct 78 ms 8652 KB Output is correct
13 Correct 121 ms 11980 KB Output is correct
14 Correct 121 ms 11964 KB Output is correct
15 Correct 8 ms 1624 KB Output is correct
16 Correct 9 ms 1624 KB Output is correct
17 Correct 73 ms 8344 KB Output is correct
18 Correct 76 ms 8908 KB Output is correct
19 Correct 77 ms 8916 KB Output is correct
20 Correct 124 ms 11980 KB Output is correct
21 Correct 128 ms 11984 KB Output is correct
22 Correct 122 ms 11980 KB Output is correct
23 Correct 126 ms 11980 KB Output is correct
24 Correct 9 ms 1624 KB Output is correct
25 Correct 9 ms 1368 KB Output is correct
26 Correct 10 ms 1604 KB Output is correct
27 Correct 10 ms 1624 KB Output is correct
28 Correct 1 ms 600 KB Output is correct
29 Correct 1 ms 600 KB Output is correct
30 Correct 1 ms 600 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 600 KB Output is correct
35 Correct 1 ms 600 KB Output is correct
36 Correct 1 ms 600 KB Output is correct
37 Correct 2 ms 600 KB Output is correct
38 Correct 1 ms 680 KB Output is correct
39 Correct 2 ms 600 KB Output is correct
40 Correct 1 ms 344 KB Output is correct
41 Correct 0 ms 344 KB Output is correct
42 Correct 0 ms 344 KB Output is correct
43 Correct 1 ms 344 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '131'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 249 ms 1112 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -