oj.uz

Submission #1058908

# Submission time Handle Problem Language Result Execution time Memory
1058908 2024-08-14T14:58:23 Z Thanhs Osumnjičeni (COCI21_osumnjiceni) C++14
110 / 110
 389 ms 89512 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define double long double
 
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
#define fi first
#define se second
#define all(x) x.begin(), x.end()
 
// mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
// int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}

const int NM = 4e5 + 5;
const int LG = 30 + 5;
const int inf = 1e9;

vector<int> v;
int n, q, sz, up[NM][LG];

struct segtree
{
    int dt[4 * NM], lz[4 * NM];
    void prop(int x, int l, int r)
    {
        if (!lz[x])
            return;
        int m = l + r >> 1;
        dt[x << 1] += lz[x] * (m - l + 1);
        lz[x << 1] += lz[x];
        dt[x << 1 | 1] += lz[x] * (r - m);
        lz[x << 1 | 1] += lz[x];
        lz[x] = 0;
    }
    void upd(int l, int r, int v, int x = 1, int lx = 1, int rx = sz)
    {
        if (l > rx || lx > r)
            return;
        if (lx >= l && rx <= r)
        {
            dt[x] += v * (rx - lx + 1);
            lz[x] += v;
            return;
        }
        prop(x, lx, rx);
        int m = lx + rx >> 1;
        upd(l, r, v, x << 1, lx, m);
        upd(l, r, v, x << 1 | 1, m + 1, rx);
        dt[x] = dt[x << 1] + dt[x << 1 | 1];
    }
    int get(int l, int r, int x = 1, int lx = 1, int rx = sz)
    {
        if (l > rx || lx > r)
            return 0;
        if (lx >= l && rx <= r)
            return dt[x];
        prop(x, lx, rx);
        int m = lx + rx >> 1;
        return get(l, r, x << 1, lx, m) + get(l, r, x << 1 | 1, m + 1, rx);
    }
}st;

struct range
{
    int l, r;
    range() : l(0), r(0){}
}a[NM];

int mp(int x)
{
    return upper_bound(v.begin(), v.end(), x) - v.begin();
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].l >> a[i].r;
        v.push_back(a[i].l);
        v.push_back(a[i].r);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    sz = v.size();
    for (int i = 1; i <= n; i++)
    {
        a[i].l = mp(a[i].l);
        a[i].r = mp(a[i].r);
    }
    int r = 0;
    for (int i = 1; i <= n; i++)
    {
        while (r < n && !st.get(a[r + 1].l, a[r + 1].r))
        {
            r++;
            st.upd(a[r].l, a[r].r, 1);
        }
        up[i][0] = r + 1;
        st.upd(a[i].l, a[i].r, -1);
    }
    up[n + 1][0] = n + 1;
    for (int j = 1; (1 << j) <= n + 1; j++)
        for (int i = 1; i <= n + 1; i++)
            up[i][j] = up[up[i][j - 1]][j - 1];
    cin >> q;
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        int res = 0, cur = l;
        for (int i = __lg(n); i >= 0; i--)
            if (up[cur][i] <= r)
            {
                res += (1 << i);
                cur = up[cur][i];
            }
        cout << res + 1 << endl;
    }
}

signed main()
{
    fastIO
    if (fopen("in.txt", "r")) 
    {
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    }
    int tc = 1;
    // cin >> tc;
    while (tc--)
        solve();
}

Compilation message

Main.cpp: In member function 'void segtree::prop(long long int, long long int, long long int)':
Main.cpp:34:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |         int m = l + r >> 1;
      |                 ~~^~~
Main.cpp: In member function 'void segtree::upd(long long int, long long int, long long int, long long int, long long int, long long int)':
Main.cpp:52:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |         int m = lx + rx >> 1;
      |                 ~~~^~~~
Main.cpp: In member function 'long long int segtree::get(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:64:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |         int m = lx + rx >> 1;
      |                 ~~~^~~~
Main.cpp: In function 'int main()':
Main.cpp:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         freopen("in.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:134:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 84512 KB Output is correct
2 Correct 286 ms 82884 KB Output is correct
3 Correct 299 ms 84416 KB Output is correct
4 Correct 290 ms 83392 KB Output is correct
5 Correct 309 ms 87232 KB Output is correct
6 Correct 38 ms 63168 KB Output is correct
7 Correct 43 ms 64464 KB Output is correct
8 Correct 46 ms 64720 KB Output is correct
9 Correct 51 ms 67088 KB Output is correct
10 Correct 53 ms 64960 KB Output is correct
11 Correct 184 ms 82368 KB Output is correct
12 Correct 170 ms 80576 KB Output is correct
13 Correct 170 ms 80384 KB Output is correct
14 Correct 201 ms 85188 KB Output is correct
15 Correct 191 ms 82624 KB Output is correct
16 Correct 2 ms 8796 KB Output is correct
17 Correct 48 ms 67184 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9564 KB Output is correct
2 Correct 7 ms 9648 KB Output is correct
3 Correct 8 ms 9636 KB Output is correct
4 Correct 8 ms 9668 KB Output is correct
5 Correct 7 ms 9564 KB Output is correct
6 Correct 3 ms 9040 KB Output is correct
7 Correct 3 ms 9052 KB Output is correct
8 Correct 3 ms 9052 KB Output is correct
9 Correct 4 ms 9052 KB Output is correct
10 Correct 3 ms 9196 KB Output is correct
11 Correct 5 ms 9564 KB Output is correct
12 Correct 5 ms 9564 KB Output is correct
13 Correct 5 ms 9564 KB Output is correct
14 Correct 5 ms 9508 KB Output is correct
15 Correct 5 ms 9564 KB Output is correct
16 Correct 2 ms 8796 KB Output is correct
17 Correct 3 ms 9052 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9564 KB Output is correct
2 Correct 7 ms 9648 KB Output is correct
3 Correct 8 ms 9636 KB Output is correct
4 Correct 8 ms 9668 KB Output is correct
5 Correct 7 ms 9564 KB Output is correct
6 Correct 3 ms 9040 KB Output is correct
7 Correct 3 ms 9052 KB Output is correct
8 Correct 3 ms 9052 KB Output is correct
9 Correct 4 ms 9052 KB Output is correct
10 Correct 3 ms 9196 KB Output is correct
11 Correct 5 ms 9564 KB Output is correct
12 Correct 5 ms 9564 KB Output is correct
13 Correct 5 ms 9564 KB Output is correct
14 Correct 5 ms 9508 KB Output is correct
15 Correct 5 ms 9564 KB Output is correct
16 Correct 2 ms 8796 KB Output is correct
17 Correct 3 ms 9052 KB Output is correct
18 Correct 52 ms 12248 KB Output is correct
19 Correct 42 ms 12036 KB Output is correct
20 Correct 47 ms 12116 KB Output is correct
21 Correct 44 ms 12012 KB Output is correct
22 Correct 44 ms 12116 KB Output is correct
23 Correct 48 ms 11604 KB Output is correct
24 Correct 45 ms 11604 KB Output is correct
25 Correct 42 ms 11600 KB Output is correct
26 Correct 39 ms 11612 KB Output is correct
27 Correct 35 ms 11532 KB Output is correct
28 Correct 27 ms 11612 KB Output is correct
29 Correct 28 ms 11612 KB Output is correct
30 Correct 29 ms 11680 KB Output is correct
31 Correct 32 ms 11632 KB Output is correct
32 Correct 29 ms 11604 KB Output is correct
33 Correct 2 ms 8828 KB Output is correct
34 Correct 29 ms 11348 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 85920 KB Output is correct
2 Correct 294 ms 85952 KB Output is correct
3 Correct 268 ms 82768 KB Output is correct
4 Correct 267 ms 79248 KB Output is correct
5 Correct 275 ms 82800 KB Output is correct
6 Correct 39 ms 63684 KB Output is correct
7 Correct 43 ms 63164 KB Output is correct
8 Correct 54 ms 63704 KB Output is correct
9 Correct 56 ms 63124 KB Output is correct
10 Correct 57 ms 67940 KB Output is correct
11 Correct 168 ms 78524 KB Output is correct
12 Correct 196 ms 82624 KB Output is correct
13 Correct 165 ms 79300 KB Output is correct
14 Correct 191 ms 81600 KB Output is correct
15 Correct 204 ms 82624 KB Output is correct
16 Correct 2 ms 8796 KB Output is correct
17 Correct 38 ms 64532 KB Output is correct

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 84512 KB Output is correct
2 Correct 286 ms 82884 KB Output is correct
3 Correct 299 ms 84416 KB Output is correct
4 Correct 290 ms 83392 KB Output is correct
5 Correct 309 ms 87232 KB Output is correct
6 Correct 38 ms 63168 KB Output is correct
7 Correct 43 ms 64464 KB Output is correct
8 Correct 46 ms 64720 KB Output is correct
9 Correct 51 ms 67088 KB Output is correct
10 Correct 53 ms 64960 KB Output is correct
11 Correct 184 ms 82368 KB Output is correct
12 Correct 170 ms 80576 KB Output is correct
13 Correct 170 ms 80384 KB Output is correct
14 Correct 201 ms 85188 KB Output is correct
15 Correct 191 ms 82624 KB Output is correct
16 Correct 2 ms 8796 KB Output is correct
17 Correct 48 ms 67184 KB Output is correct
18 Correct 8 ms 9564 KB Output is correct
19 Correct 7 ms 9648 KB Output is correct
20 Correct 8 ms 9636 KB Output is correct
21 Correct 8 ms 9668 KB Output is correct
22 Correct 7 ms 9564 KB Output is correct
23 Correct 3 ms 9040 KB Output is correct
24 Correct 3 ms 9052 KB Output is correct
25 Correct 3 ms 9052 KB Output is correct
26 Correct 4 ms 9052 KB Output is correct
27 Correct 3 ms 9196 KB Output is correct
28 Correct 5 ms 9564 KB Output is correct
29 Correct 5 ms 9564 KB Output is correct
30 Correct 5 ms 9564 KB Output is correct
31 Correct 5 ms 9508 KB Output is correct
32 Correct 5 ms 9564 KB Output is correct
33 Correct 2 ms 8796 KB Output is correct
34 Correct 3 ms 9052 KB Output is correct
35 Correct 52 ms 12248 KB Output is correct
36 Correct 42 ms 12036 KB Output is correct
37 Correct 47 ms 12116 KB Output is correct
38 Correct 44 ms 12012 KB Output is correct
39 Correct 44 ms 12116 KB Output is correct
40 Correct 48 ms 11604 KB Output is correct
41 Correct 45 ms 11604 KB Output is correct
42 Correct 42 ms 11600 KB Output is correct
43 Correct 39 ms 11612 KB Output is correct
44 Correct 35 ms 11532 KB Output is correct
45 Correct 27 ms 11612 KB Output is correct
46 Correct 28 ms 11612 KB Output is correct
47 Correct 29 ms 11680 KB Output is correct
48 Correct 32 ms 11632 KB Output is correct
49 Correct 29 ms 11604 KB Output is correct
50 Correct 2 ms 8828 KB Output is correct
51 Correct 29 ms 11348 KB Output is correct
52 Correct 317 ms 85920 KB Output is correct
53 Correct 294 ms 85952 KB Output is correct
54 Correct 268 ms 82768 KB Output is correct
55 Correct 267 ms 79248 KB Output is correct
56 Correct 275 ms 82800 KB Output is correct
57 Correct 39 ms 63684 KB Output is correct
58 Correct 43 ms 63164 KB Output is correct
59 Correct 54 ms 63704 KB Output is correct
60 Correct 56 ms 63124 KB Output is correct
61 Correct 57 ms 67940 KB Output is correct
62 Correct 168 ms 78524 KB Output is correct
63 Correct 196 ms 82624 KB Output is correct
64 Correct 165 ms 79300 KB Output is correct
65 Correct 191 ms 81600 KB Output is correct
66 Correct 204 ms 82624 KB Output is correct
67 Correct 2 ms 8796 KB Output is correct
68 Correct 38 ms 64532 KB Output is correct
69 Correct 367 ms 84412 KB Output is correct
70 Correct 389 ms 89512 KB Output is correct
71 Correct 350 ms 82884 KB Output is correct
72 Correct 382 ms 87744 KB Output is correct
73 Correct 369 ms 84896 KB Output is correct
74 Correct 143 ms 72128 KB Output is correct
75 Correct 126 ms 68144 KB Output is correct
76 Correct 121 ms 72124 KB Output is correct
77 Correct 111 ms 66964 KB Output is correct
78 Correct 115 ms 68208 KB Output is correct
79 Correct 223 ms 85696 KB Output is correct
80 Correct 209 ms 82024 KB Output is correct
81 Correct 207 ms 81028 KB Output is correct
82 Correct 232 ms 85444 KB Output is correct
83 Correct 222 ms 83648 KB Output is correct
84 Correct 2 ms 8796 KB Output is correct
85 Correct 82 ms 67176 KB Output is correct