oj.uz

답안 #694850

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
694850 2023-02-04T10:31:24 Z Tien_Noob Two Antennas (JOI19_antennas) C++17
100 / 100
 538 ms 49800 KB 
//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
using namespace std;
const int N = 2e5;
int n, q, h[N + 1], a[N + 1], b[N + 1], res[N + 1];
vector<pair<int, int> > query[N + 1];
vector<int> add[N + 1], del[N + 1];
void read()
{
    cin >> n;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> h[i] >> a[i] >> b[i];
        if (i + a[i] <= n)
        {
            add[i + a[i]].push_back(i);
            del[min(n, i + b[i])].push_back(i);
        }
    }
    cin >> q;
    for (int i = 1; i <= q; ++ i)
    {
        int l, r;
        cin >> l >> r;
        query[r].emplace_back(l, i);
    }
}
struct SegmentTree
{
    int val[4 * N + 1], mna[4 * N + 1], mxa[4 * N + 1];
    int lazy_mnb[4 * N + 1], lazy_mxb[4 * N + 1];
    SegmentTree()
    {
        for (int i = 1; i <= 4 * N; ++ i)
        {
            val[i] = -1;
            mxa[i] = lazy_mxb[i] = 0;
            mna[i] = lazy_mnb[i] = 1e9;
        }
    }
    void refine(int v)
    {
        if (min(mxa[v], lazy_mxb[v]) == 0)
        {
            return ;
        }
        val[v] = max({val[v], abs(mna[v] - lazy_mnb[v]), abs(mna[v] - lazy_mxb[v]), abs(mxa[v] - lazy_mnb[v]), abs(mxa[v] - lazy_mxb[v])});
    }
    void push(int v)
    {
        if (lazy_mxb[v] == 0)
        {
            return ;
        }
        lazy_mxb[2 * v] = max(lazy_mxb[2 * v], lazy_mxb[v]);
        lazy_mnb[2 * v] = min(lazy_mnb[2 * v], lazy_mnb[v]);
        refine(2 * v);
        lazy_mxb[2 * v + 1] = max(lazy_mxb[2 * v + 1], lazy_mxb[v]);
        lazy_mnb[2 * v + 1] = min(lazy_mnb[2 * v + 1], lazy_mnb[v]);
        refine(2 * v + 1);
        lazy_mxb[v] = 0;
        lazy_mnb[v] = 1e9;
    }
    void upd_b(int v, int TreeL, int TreeR, int L, int R, int B)
    {
        if (L > R)
        {
            return ;
        }
        if (TreeL == L && TreeR == R)
        {
            lazy_mnb[v] = min(lazy_mnb[v], B);
            lazy_mxb[v] = max(lazy_mxb[v], B);
            refine(v);
            return ;
        }
        push(v);
        int mid = (TreeL + TreeR)/2;
        upd_b(v * 2, TreeL, mid, L, min(R, mid), B);
        upd_b(v * 2 + 1, mid + 1, TreeR, max(L, mid + 1), R, B);
        val[v] = max({val[v], val[2 * v], val[2 * v + 1]});
    }
    void upd_a(int v, int TreeL, int TreeR, int pos, int A)
    {
        if (TreeL == TreeR)
        {
            if (A == 0)
            {
                mxa[v] = 0;
                mna[v] = 1e9;
            }
            else
            {
                mxa[v] = mna[v] = A;
            }
            lazy_mxb[v] = 0;
            lazy_mnb[v] = 1e9;
            return ;
        }
        push(v);
        int mid = (TreeL + TreeR)/2;
        if (pos <= mid)
        {
            upd_a(v * 2, TreeL, mid, pos, A);
        }
        else
        {
            upd_a(v * 2 + 1, mid + 1, TreeR, pos, A);
        }
        mxa[v] = max(mxa[2 * v], mxa[2 * v + 1]);
        mna[v] = min(mna[2 * v], mna[2 * v + 1]);
        val[v] = max({val[v], val[2 * v], val[2 * v + 1]});
    }
    int get(int v, int TreeL, int TreeR, int L, int R)
    {
        if (L > R)
        {
            return -1;
        }
        if (TreeL == L && TreeR == R)
        {
            return val[v];
        }
        push(v);
        int mid = (TreeL + TreeR)/2;
        return max(get(v * 2, TreeL, mid, L, min(R, mid)), get(v * 2 + 1, mid + 1, TreeR, max(L, mid + 1), R));
    }
} tree;
void solve()
{
    for (int r = 1; r <= n; ++ r)
    {
        for (int i : add[r])
        {
            tree.upd_a(1, 1, n, i, h[i]);
        }
        int L = max(1, r - b[r]), R = r - a[r];
        tree.upd_b(1, 1, n, L, R, h[r]);
        for (auto [l, i] : query[r])
        {
            res[i] = tree.get(1, 1, n, l, r);
        }
        for (int i : del[r])
        {
            tree.upd_a(1, 1, n, i, 0);
        }
    }
    for (int i = 1; i <= q; ++ i)
    {
        cout << res[i] << '\n';
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}

Compilation message

antennas.cpp: In function 'int main()':
antennas.cpp:161:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 30092 KB Output is correct
2 Correct 16 ms 30076 KB Output is correct
3 Correct 15 ms 30080 KB Output is correct
4 Correct 15 ms 30036 KB Output is correct
5 Correct 15 ms 30036 KB Output is correct
6 Correct 15 ms 30036 KB Output is correct
7 Correct 14 ms 30104 KB Output is correct
8 Correct 19 ms 30112 KB Output is correct
9 Correct 18 ms 30004 KB Output is correct
10 Correct 15 ms 30064 KB Output is correct
11 Correct 14 ms 30076 KB Output is correct
12 Correct 15 ms 30036 KB Output is correct
13 Correct 14 ms 30036 KB Output is correct
14 Correct 15 ms 29984 KB Output is correct
15 Correct 15 ms 30036 KB Output is correct
16 Correct 14 ms 30056 KB Output is correct
17 Correct 14 ms 30044 KB Output is correct
18 Correct 16 ms 30076 KB Output is correct
19 Correct 14 ms 30036 KB Output is correct
20 Correct 16 ms 30036 KB Output is correct
21 Correct 15 ms 30084 KB Output is correct
22 Correct 15 ms 30012 KB Output is correct
23 Correct 14 ms 30184 KB Output is correct
24 Correct 14 ms 30036 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 30092 KB Output is correct
2 Correct 16 ms 30076 KB Output is correct
3 Correct 15 ms 30080 KB Output is correct
4 Correct 15 ms 30036 KB Output is correct
5 Correct 15 ms 30036 KB Output is correct
6 Correct 15 ms 30036 KB Output is correct
7 Correct 14 ms 30104 KB Output is correct
8 Correct 19 ms 30112 KB Output is correct
9 Correct 18 ms 30004 KB Output is correct
10 Correct 15 ms 30064 KB Output is correct
11 Correct 14 ms 30076 KB Output is correct
12 Correct 15 ms 30036 KB Output is correct
13 Correct 14 ms 30036 KB Output is correct
14 Correct 15 ms 29984 KB Output is correct
15 Correct 15 ms 30036 KB Output is correct
16 Correct 14 ms 30056 KB Output is correct
17 Correct 14 ms 30044 KB Output is correct
18 Correct 16 ms 30076 KB Output is correct
19 Correct 14 ms 30036 KB Output is correct
20 Correct 16 ms 30036 KB Output is correct
21 Correct 15 ms 30084 KB Output is correct
22 Correct 15 ms 30012 KB Output is correct
23 Correct 14 ms 30184 KB Output is correct
24 Correct 14 ms 30036 KB Output is correct
25 Correct 77 ms 34856 KB Output is correct
26 Correct 25 ms 30704 KB Output is correct
27 Correct 108 ms 36872 KB Output is correct
28 Correct 108 ms 36936 KB Output is correct
29 Correct 74 ms 34892 KB Output is correct
30 Correct 76 ms 34636 KB Output is correct
31 Correct 80 ms 36048 KB Output is correct
32 Correct 102 ms 36956 KB Output is correct
33 Correct 94 ms 36452 KB Output is correct
34 Correct 58 ms 33424 KB Output is correct
35 Correct 105 ms 36820 KB Output is correct
36 Correct 108 ms 36896 KB Output is correct
37 Correct 71 ms 33452 KB Output is correct
38 Correct 95 ms 36044 KB Output is correct
39 Correct 34 ms 30900 KB Output is correct
40 Correct 97 ms 35968 KB Output is correct
41 Correct 73 ms 34304 KB Output is correct
42 Correct 98 ms 35996 KB Output is correct
43 Correct 43 ms 32064 KB Output is correct
44 Correct 96 ms 35916 KB Output is correct
45 Correct 31 ms 31052 KB Output is correct
46 Correct 92 ms 35992 KB Output is correct
47 Correct 37 ms 31596 KB Output is correct
48 Correct 96 ms 36012 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 272 ms 36152 KB Output is correct
2 Correct 299 ms 36424 KB Output is correct
3 Correct 225 ms 34940 KB Output is correct
4 Correct 296 ms 36544 KB Output is correct
5 Correct 131 ms 33484 KB Output is correct
6 Correct 331 ms 36432 KB Output is correct
7 Correct 308 ms 35952 KB Output is correct
8 Correct 307 ms 40780 KB Output is correct
9 Correct 45 ms 31616 KB Output is correct
10 Correct 292 ms 40580 KB Output is correct
11 Correct 177 ms 36588 KB Output is correct
12 Correct 306 ms 40656 KB Output is correct
13 Correct 165 ms 38052 KB Output is correct
14 Correct 156 ms 38244 KB Output is correct
15 Correct 149 ms 38196 KB Output is correct
16 Correct 145 ms 38604 KB Output is correct
17 Correct 153 ms 38144 KB Output is correct
18 Correct 162 ms 38568 KB Output is correct
19 Correct 145 ms 37900 KB Output is correct
20 Correct 162 ms 38128 KB Output is correct
21 Correct 157 ms 37848 KB Output is correct
22 Correct 163 ms 38216 KB Output is correct
23 Correct 148 ms 37952 KB Output is correct
24 Correct 131 ms 38052 KB Output is correct

Subtask #4
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 30092 KB Output is correct
2 Correct 16 ms 30076 KB Output is correct
3 Correct 15 ms 30080 KB Output is correct
4 Correct 15 ms 30036 KB Output is correct
5 Correct 15 ms 30036 KB Output is correct
6 Correct 15 ms 30036 KB Output is correct
7 Correct 14 ms 30104 KB Output is correct
8 Correct 19 ms 30112 KB Output is correct
9 Correct 18 ms 30004 KB Output is correct
10 Correct 15 ms 30064 KB Output is correct
11 Correct 14 ms 30076 KB Output is correct
12 Correct 15 ms 30036 KB Output is correct
13 Correct 14 ms 30036 KB Output is correct
14 Correct 15 ms 29984 KB Output is correct
15 Correct 15 ms 30036 KB Output is correct
16 Correct 14 ms 30056 KB Output is correct
17 Correct 14 ms 30044 KB Output is correct
18 Correct 16 ms 30076 KB Output is correct
19 Correct 14 ms 30036 KB Output is correct
20 Correct 16 ms 30036 KB Output is correct
21 Correct 15 ms 30084 KB Output is correct
22 Correct 15 ms 30012 KB Output is correct
23 Correct 14 ms 30184 KB Output is correct
24 Correct 14 ms 30036 KB Output is correct
25 Correct 77 ms 34856 KB Output is correct
26 Correct 25 ms 30704 KB Output is correct
27 Correct 108 ms 36872 KB Output is correct
28 Correct 108 ms 36936 KB Output is correct
29 Correct 74 ms 34892 KB Output is correct
30 Correct 76 ms 34636 KB Output is correct
31 Correct 80 ms 36048 KB Output is correct
32 Correct 102 ms 36956 KB Output is correct
33 Correct 94 ms 36452 KB Output is correct
34 Correct 58 ms 33424 KB Output is correct
35 Correct 105 ms 36820 KB Output is correct
36 Correct 108 ms 36896 KB Output is correct
37 Correct 71 ms 33452 KB Output is correct
38 Correct 95 ms 36044 KB Output is correct
39 Correct 34 ms 30900 KB Output is correct
40 Correct 97 ms 35968 KB Output is correct
41 Correct 73 ms 34304 KB Output is correct
42 Correct 98 ms 35996 KB Output is correct
43 Correct 43 ms 32064 KB Output is correct
44 Correct 96 ms 35916 KB Output is correct
45 Correct 31 ms 31052 KB Output is correct
46 Correct 92 ms 35992 KB Output is correct
47 Correct 37 ms 31596 KB Output is correct
48 Correct 96 ms 36012 KB Output is correct
49 Correct 272 ms 36152 KB Output is correct
50 Correct 299 ms 36424 KB Output is correct
51 Correct 225 ms 34940 KB Output is correct
52 Correct 296 ms 36544 KB Output is correct
53 Correct 131 ms 33484 KB Output is correct
54 Correct 331 ms 36432 KB Output is correct
55 Correct 308 ms 35952 KB Output is correct
56 Correct 307 ms 40780 KB Output is correct
57 Correct 45 ms 31616 KB Output is correct
58 Correct 292 ms 40580 KB Output is correct
59 Correct 177 ms 36588 KB Output is correct
60 Correct 306 ms 40656 KB Output is correct
61 Correct 165 ms 38052 KB Output is correct
62 Correct 156 ms 38244 KB Output is correct
63 Correct 149 ms 38196 KB Output is correct
64 Correct 145 ms 38604 KB Output is correct
65 Correct 153 ms 38144 KB Output is correct
66 Correct 162 ms 38568 KB Output is correct
67 Correct 145 ms 37900 KB Output is correct
68 Correct 162 ms 38128 KB Output is correct
69 Correct 157 ms 37848 KB Output is correct
70 Correct 163 ms 38216 KB Output is correct
71 Correct 148 ms 37952 KB Output is correct
72 Correct 131 ms 38052 KB Output is correct
73 Correct 439 ms 46516 KB Output is correct
74 Correct 313 ms 41440 KB Output is correct
75 Correct 387 ms 46032 KB Output is correct
76 Correct 534 ms 49744 KB Output is correct
77 Correct 252 ms 40940 KB Output is correct
78 Correct 479 ms 46964 KB Output is correct
79 Correct 484 ms 48144 KB Output is correct
80 Correct 498 ms 49744 KB Output is correct
81 Correct 233 ms 39116 KB Output is correct
82 Correct 404 ms 45312 KB Output is correct
83 Correct 405 ms 45132 KB Output is correct
84 Correct 538 ms 49800 KB Output is correct
85 Correct 243 ms 42820 KB Output is correct
86 Correct 336 ms 46004 KB Output is correct
87 Correct 166 ms 39424 KB Output is correct
88 Correct 305 ms 46536 KB Output is correct
89 Correct 295 ms 44116 KB Output is correct
90 Correct 305 ms 46488 KB Output is correct
91 Correct 205 ms 40716 KB Output is correct
92 Correct 298 ms 45892 KB Output is correct
93 Correct 213 ms 39492 KB Output is correct
94 Correct 322 ms 46108 KB Output is correct
95 Correct 259 ms 40372 KB Output is correct
96 Correct 298 ms 46044 KB Output is correct