oj.uz

Submission #486387

# Submission time Handle Problem Language Result Execution time Memory
486387 2021-11-11T14:38:12 Z Lam_lai_cuoc_doi Two Antennas (JOI19_antennas) C++17
24 / 100
 3000 ms 26460 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 2e5 + 5;
constexpr int Inf = 1e9 + 7;

struct SegmentTree
{
    int st[N * 4], n;
    SegmentTree()
    {
        fill_n(st, N * 4, -Inf);
    }
    void Update(int id, int l, int r, const int &x, const int &v)
    {
        if (l > x || r < x)
            return;
        if (l == x && r == x)
        {
            st[id] = v;
            return;
        }

        Update(id << 1, l, (l + r) / 2, x, v);
        Update(id << 1 | 1, (l + r) / 2 + 1, r, x, v);

        st[id] = max(st[id << 1], st[id << 1 | 1]);
    }
    void Update(int x, int v)
    {
        Update(1, 1, n, x, v);
    }

    int Get(int id, int l, int r, const int &a, const int &b)
    {
        if (l > b || r < a)
            return -Inf;
        if (l >= a && r <= b)
            return st[id];
        return max(Get(id << 1, l, (l + r) / 2, a, b), Get(id << 1 | 1, (l + r) / 2 + 1, r, a, b));
    }

    int Get(int l, int r)
    {
        return Get(1, 1, n, l, r);
    }
} f, g;

int n, q, l[N], r[N], x[N], y[N], a[N];
vector<int> in[N], out[N];

void Read()
{
    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i] >> x[i] >> y[i];

        if (i - x[i] > 0)
            in[i - x[i]].emplace_back(i);
        if (i - y[i] - 1 > 0)
            out[i - y[i] - 1].emplace_back(i);
    }

    cin >> q;
}

void Solve()
{
    f.n = g.n = n;

    while (q--)
    {
        int l, r;
        cin >> l >> r;

        int ans(-Inf);

        for (int i = r; i >= l; --i)
        {
            for (auto j : in[i])
            {
                f.Update(j, a[j]);
                g.Update(j, -a[j]);
            }
            for (auto j : out[i])
            {
                f.Update(j, -Inf);
                g.Update(j, -Inf);
            }

            if (i + x[i] <= r)
            {
                int maxn = f.Get(i + x[i], min(r, i + y[i])),
                    minn = -g.Get(i + x[i], min(r, i + y[i]));

                if (maxn != -Inf && minn != Inf)
                    ans = max(ans, max(abs(a[i] - maxn), abs(a[i] - minn)));
                else if (maxn != -Inf)
                    ans = max(ans, abs(a[i] - maxn));
                else if (minn != Inf)
                    ans = max(ans, abs(a[i] - minn));
            }
        }

        for (int i = r; i >= l; --i)
            for (auto j : in[i])
            {
                f.Update(j, -Inf);
                g.Update(j, -Inf);
            }

        cout << (ans <= -Inf ? -1 : ans) << '\n';
    }
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("palesta.INP", "r"))
    {
        freopen("paletsa.inp", "r", stdin);
        freopen("palesta.out", "w", stdout);
    }
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        // cout << "Case #" << _ << ": ";
        Read();
        Solve();
    }
    // cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

/*
 */

Compilation message

antennas.cpp: In function 'void read(T&)':
antennas.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^
antennas.cpp: In function 'int32_t main()':
antennas.cpp:141:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         freopen("paletsa.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:142:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         freopen("palesta.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15948 KB Output is correct
2 Correct 10 ms 15992 KB Output is correct
3 Correct 11 ms 15948 KB Output is correct
4 Correct 11 ms 15988 KB Output is correct
5 Correct 8 ms 15984 KB Output is correct
6 Correct 9 ms 15948 KB Output is correct
7 Correct 10 ms 15948 KB Output is correct
8 Correct 11 ms 15968 KB Output is correct
9 Correct 8 ms 15908 KB Output is correct
10 Correct 11 ms 15948 KB Output is correct
11 Correct 10 ms 15948 KB Output is correct
12 Correct 15 ms 16044 KB Output is correct
13 Correct 10 ms 15944 KB Output is correct
14 Correct 11 ms 15984 KB Output is correct
15 Correct 9 ms 15948 KB Output is correct
16 Correct 10 ms 15984 KB Output is correct
17 Correct 11 ms 15988 KB Output is correct
18 Correct 12 ms 15984 KB Output is correct
19 Correct 8 ms 15996 KB Output is correct
20 Correct 9 ms 15948 KB Output is correct
21 Correct 9 ms 15956 KB Output is correct
22 Correct 10 ms 15948 KB Output is correct
23 Correct 9 ms 15948 KB Output is correct
24 Correct 10 ms 15976 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15948 KB Output is correct
2 Correct 10 ms 15992 KB Output is correct
3 Correct 11 ms 15948 KB Output is correct
4 Correct 11 ms 15988 KB Output is correct
5 Correct 8 ms 15984 KB Output is correct
6 Correct 9 ms 15948 KB Output is correct
7 Correct 10 ms 15948 KB Output is correct
8 Correct 11 ms 15968 KB Output is correct
9 Correct 8 ms 15908 KB Output is correct
10 Correct 11 ms 15948 KB Output is correct
11 Correct 10 ms 15948 KB Output is correct
12 Correct 15 ms 16044 KB Output is correct
13 Correct 10 ms 15944 KB Output is correct
14 Correct 11 ms 15984 KB Output is correct
15 Correct 9 ms 15948 KB Output is correct
16 Correct 10 ms 15984 KB Output is correct
17 Correct 11 ms 15988 KB Output is correct
18 Correct 12 ms 15984 KB Output is correct
19 Correct 8 ms 15996 KB Output is correct
20 Correct 9 ms 15948 KB Output is correct
21 Correct 9 ms 15956 KB Output is correct
22 Correct 10 ms 15948 KB Output is correct
23 Correct 9 ms 15948 KB Output is correct
24 Correct 10 ms 15976 KB Output is correct
25 Execution timed out 3062 ms 17120 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 25412 KB Output is correct
2 Correct 242 ms 26436 KB Output is correct
3 Correct 170 ms 23232 KB Output is correct
4 Correct 231 ms 26456 KB Output is correct
5 Correct 95 ms 20544 KB Output is correct
6 Correct 221 ms 26380 KB Output is correct
7 Correct 194 ms 24948 KB Output is correct
8 Correct 231 ms 26460 KB Output is correct
9 Correct 34 ms 17484 KB Output is correct
10 Correct 223 ms 26356 KB Output is correct
11 Correct 133 ms 22448 KB Output is correct
12 Correct 226 ms 26356 KB Output is correct
13 Correct 153 ms 25156 KB Output is correct
14 Correct 156 ms 24772 KB Output is correct
15 Correct 140 ms 24000 KB Output is correct
16 Correct 140 ms 23676 KB Output is correct
17 Correct 162 ms 25404 KB Output is correct
18 Correct 148 ms 24272 KB Output is correct
19 Correct 153 ms 24772 KB Output is correct
20 Correct 152 ms 24856 KB Output is correct
21 Correct 145 ms 25156 KB Output is correct
22 Correct 146 ms 24644 KB Output is correct
23 Correct 150 ms 24996 KB Output is correct
24 Correct 139 ms 23792 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15948 KB Output is correct
2 Correct 10 ms 15992 KB Output is correct
3 Correct 11 ms 15948 KB Output is correct
4 Correct 11 ms 15988 KB Output is correct
5 Correct 8 ms 15984 KB Output is correct
6 Correct 9 ms 15948 KB Output is correct
7 Correct 10 ms 15948 KB Output is correct
8 Correct 11 ms 15968 KB Output is correct
9 Correct 8 ms 15908 KB Output is correct
10 Correct 11 ms 15948 KB Output is correct
11 Correct 10 ms 15948 KB Output is correct
12 Correct 15 ms 16044 KB Output is correct
13 Correct 10 ms 15944 KB Output is correct
14 Correct 11 ms 15984 KB Output is correct
15 Correct 9 ms 15948 KB Output is correct
16 Correct 10 ms 15984 KB Output is correct
17 Correct 11 ms 15988 KB Output is correct
18 Correct 12 ms 15984 KB Output is correct
19 Correct 8 ms 15996 KB Output is correct
20 Correct 9 ms 15948 KB Output is correct
21 Correct 9 ms 15956 KB Output is correct
22 Correct 10 ms 15948 KB Output is correct
23 Correct 9 ms 15948 KB Output is correct
24 Correct 10 ms 15976 KB Output is correct
25 Execution timed out 3062 ms 17120 KB Time limit exceeded
26 Halted 0 ms 0 KB -