oj.uz

Submission #970689

# Submission time Handle Problem Language Result Execution time Memory
970689 2024-04-27T05:05:49 Z VinhLuu Osumnjičeni (COCI21_osumnjiceni) C++17
110 / 110
 651 ms 111368 KB 
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()

using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 1e6 + 5;
int block = 555;
//const ll oo = 5e18;

int n, L[N], R[N], q, kq[N], le[N];
vector<pii> Q[N];
int st[N << 2], lz[N << 2], g[N << 2];

void build(int i,int l,int r){
    if(l == r){
        st[i] = 0;
        g[i] = -1;
        lz[i] = 0;
        return;
    }
    int mid = (l + r) / 2;
    build(i << 1, l, mid);
    build(i << 1|1, mid + 1, r);
    st[i] = lz[i] = 0, g[i] = -1;
}

void dolz(int i){
    if(g[i] != -1){
        g[i << 1] = g[i << 1|1] = st[i << 1] = st[i << 1|1] = g[i];
        lz[i << 1] = lz[i << 1|1] = 0;
        g[i] = -1;
    }
    if(lz[i]){
        st[i << 1] += lz[i];
        if(g[i << 1] != -1) g[i << 1] += lz[i];
        else lz[i << 1] += lz[i];
        st[i << 1|1] += lz[i];
        if(g[i << 1|1] != -1) g[i << 1|1] += lz[i];
        else lz[i << 1|1] += lz[i];
        lz[i] = 0;
    }
}

void update(int i,int l,int r,int u, int v,int x){
    if(l > r || l > v || r < u) return;
    if(u <= l && r <= v){
        st[i] += x;
//        cerr << l << " " << r << " " << i << " " << st[i] << " " << x << " d\n";
        if(g[i] != -1) g[i] += x;
        else lz[i] += x;
        return;
    }
    int mid = (l + r) / 2;
    dolz(i);
    update(i << 1, l, mid, u, v, x);
    update(i << 1|1, mid + 1, r, u, v, x);
    st[i] = max(st[i << 1], st[i << 1|1]);
}

void gan(int i,int l,int r,int u,int v,int x){
    if(l > r || l > v || r < u) return;
    if(u <= l && r <= v){
        g[i] = x;
        lz[i] = 0;
        st[i] = x;
        return;
    }
    int mid = (l + r) / 2;
    dolz(i);
    gan(i << 1, l, mid, u, v, x);
    gan(i << 1|1, mid + 1, r, u, v, x);
    st[i] = max(st[i << 1], st[i << 1|1]);
}

int get(int i,int l,int r,int u,int v){
    if(l > r || l > v || r < u) return 0;
    if(u <= l && r <= v){
//        cerr << i << " " << st[i] << " " << u << " " << v << "\n";
        return st[i];
    }
    int mid = (l + r) / 2;
    dolz(i);
    return max(get(i << 1, l, mid, u, v), get(i << 1|1, mid + 1, r, u, v));
}

int f[N][22], d[N];
vector<int> p[N];

void dfs(int u,int v){
    if(v == 0) for(int i = 0; i <= 20; i ++) f[u][i] = u;
    else{
        f[u][0] = v;
        for(int i = 1; i <= 20; i ++) f[u][i] = f[f[u][i - 1]][i - 1];
    }
    for(auto j : p[u]){
        d[j] = d[u] + 1;
        dfs(j, u);
    }
}

int fin(int l,int r){
    int kq = r, u = r;
    for(int i = 20; i >= 0; i --){
        if(f[u][i] >= l){
            kq = f[u][i];
            u = f[u][i];
        }
    }
    return d[r] - d[kq] + 1;
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #define task "v"
    if(fopen(task ".inp","r")){
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }

    cin >> n;
    vector<int> rrh;
    for(int i = 1; i <= n; i ++){
        cin >> L[i] >> R[i];
        rrh.pb(L[i]);
        rrh.pb(R[i]);
    }
    sort(all(rrh)); rrh.resize(unique(all(rrh)) - rrh.begin());
    for(int i = 1; i <= n; i ++){
        L[i] = lower_bound(all(rrh), L[i]) - rrh.begin() + 1;
        R[i] = lower_bound(all(rrh), R[i]) - rrh.begin() + 1;
    }

    int m = (int)rrh.size();
    int ptr = 1;
    le[1] = 1;
    p[le[1] - 1].pb(1);
    build(1, 1, m);
    update(1, 1, m, L[1], R[1], 1);
    for(int i = 2; i <= n; i ++){
        while(ptr < i && get(1, 1, m, L[i], R[i]) > 0){
            update(1, 1, m, L[ptr], R[ptr], -1);
            ptr++;
        }
        update(1, 1, m, L[i], R[i], 1);
        le[i] = ptr;
        p[le[i] - 1].pb(i);
//        cerr << i << " " << le[i] - 1 << " t\n";
    }
    dfs(0, 0);

    cin >> q; for(int i = 1; i <= q; i ++){
        int l, r; cin >> l >> r; cout << fin(l, r) << "\n";
    }

}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(task ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen(task ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 102096 KB Output is correct
2 Correct 461 ms 105512 KB Output is correct
3 Correct 440 ms 105416 KB Output is correct
4 Correct 465 ms 107352 KB Output is correct
5 Correct 482 ms 108172 KB Output is correct
6 Correct 81 ms 95652 KB Output is correct
7 Correct 94 ms 91496 KB Output is correct
8 Correct 102 ms 91868 KB Output is correct
9 Correct 113 ms 90196 KB Output is correct
10 Correct 114 ms 88044 KB Output is correct
11 Correct 236 ms 97220 KB Output is correct
12 Correct 213 ms 95136 KB Output is correct
13 Correct 209 ms 95016 KB Output is correct
14 Correct 318 ms 96588 KB Output is correct
15 Correct 307 ms 96460 KB Output is correct
16 Correct 14 ms 62300 KB Output is correct
17 Correct 85 ms 99016 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 62296 KB Output is correct
2 Correct 22 ms 62416 KB Output is correct
3 Correct 21 ms 62296 KB Output is correct
4 Correct 21 ms 62556 KB Output is correct
5 Correct 21 ms 62280 KB Output is correct
6 Correct 17 ms 62552 KB Output is correct
7 Correct 16 ms 62300 KB Output is correct
8 Correct 16 ms 62300 KB Output is correct
9 Correct 18 ms 62408 KB Output is correct
10 Correct 18 ms 62300 KB Output is correct
11 Correct 19 ms 62408 KB Output is correct
12 Correct 17 ms 62296 KB Output is correct
13 Correct 18 ms 62296 KB Output is correct
14 Correct 19 ms 62296 KB Output is correct
15 Correct 19 ms 62300 KB Output is correct
16 Correct 13 ms 62044 KB Output is correct
17 Correct 15 ms 62556 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 62296 KB Output is correct
2 Correct 22 ms 62416 KB Output is correct
3 Correct 21 ms 62296 KB Output is correct
4 Correct 21 ms 62556 KB Output is correct
5 Correct 21 ms 62280 KB Output is correct
6 Correct 17 ms 62552 KB Output is correct
7 Correct 16 ms 62300 KB Output is correct
8 Correct 16 ms 62300 KB Output is correct
9 Correct 18 ms 62408 KB Output is correct
10 Correct 18 ms 62300 KB Output is correct
11 Correct 19 ms 62408 KB Output is correct
12 Correct 17 ms 62296 KB Output is correct
13 Correct 18 ms 62296 KB Output is correct
14 Correct 19 ms 62296 KB Output is correct
15 Correct 19 ms 62300 KB Output is correct
16 Correct 13 ms 62044 KB Output is correct
17 Correct 15 ms 62556 KB Output is correct
18 Correct 83 ms 63316 KB Output is correct
19 Correct 74 ms 63056 KB Output is correct
20 Correct 82 ms 63312 KB Output is correct
21 Correct 75 ms 63228 KB Output is correct
22 Correct 77 ms 63184 KB Output is correct
23 Correct 70 ms 63240 KB Output is correct
24 Correct 86 ms 63316 KB Output is correct
25 Correct 72 ms 63052 KB Output is correct
26 Correct 80 ms 63044 KB Output is correct
27 Correct 66 ms 63052 KB Output is correct
28 Correct 64 ms 62548 KB Output is correct
29 Correct 66 ms 62548 KB Output is correct
30 Correct 65 ms 62544 KB Output is correct
31 Correct 65 ms 62544 KB Output is correct
32 Correct 65 ms 62548 KB Output is correct
33 Correct 13 ms 62044 KB Output is correct
34 Correct 66 ms 63528 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 104116 KB Output is correct
2 Correct 484 ms 107776 KB Output is correct
3 Correct 426 ms 104388 KB Output is correct
4 Correct 425 ms 104392 KB Output is correct
5 Correct 442 ms 106952 KB Output is correct
6 Correct 80 ms 95708 KB Output is correct
7 Correct 98 ms 91360 KB Output is correct
8 Correct 98 ms 89408 KB Output is correct
9 Correct 106 ms 87612 KB Output is correct
10 Correct 127 ms 88880 KB Output is correct
11 Correct 203 ms 94876 KB Output is correct
12 Correct 220 ms 97384 KB Output is correct
13 Correct 215 ms 94876 KB Output is correct
14 Correct 327 ms 96312 KB Output is correct
15 Correct 387 ms 97016 KB Output is correct
16 Correct 13 ms 62108 KB Output is correct
17 Correct 82 ms 97992 KB Output is correct

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 102096 KB Output is correct
2 Correct 461 ms 105512 KB Output is correct
3 Correct 440 ms 105416 KB Output is correct
4 Correct 465 ms 107352 KB Output is correct
5 Correct 482 ms 108172 KB Output is correct
6 Correct 81 ms 95652 KB Output is correct
7 Correct 94 ms 91496 KB Output is correct
8 Correct 102 ms 91868 KB Output is correct
9 Correct 113 ms 90196 KB Output is correct
10 Correct 114 ms 88044 KB Output is correct
11 Correct 236 ms 97220 KB Output is correct
12 Correct 213 ms 95136 KB Output is correct
13 Correct 209 ms 95016 KB Output is correct
14 Correct 318 ms 96588 KB Output is correct
15 Correct 307 ms 96460 KB Output is correct
16 Correct 14 ms 62300 KB Output is correct
17 Correct 85 ms 99016 KB Output is correct
18 Correct 23 ms 62296 KB Output is correct
19 Correct 22 ms 62416 KB Output is correct
20 Correct 21 ms 62296 KB Output is correct
21 Correct 21 ms 62556 KB Output is correct
22 Correct 21 ms 62280 KB Output is correct
23 Correct 17 ms 62552 KB Output is correct
24 Correct 16 ms 62300 KB Output is correct
25 Correct 16 ms 62300 KB Output is correct
26 Correct 18 ms 62408 KB Output is correct
27 Correct 18 ms 62300 KB Output is correct
28 Correct 19 ms 62408 KB Output is correct
29 Correct 17 ms 62296 KB Output is correct
30 Correct 18 ms 62296 KB Output is correct
31 Correct 19 ms 62296 KB Output is correct
32 Correct 19 ms 62300 KB Output is correct
33 Correct 13 ms 62044 KB Output is correct
34 Correct 15 ms 62556 KB Output is correct
35 Correct 83 ms 63316 KB Output is correct
36 Correct 74 ms 63056 KB Output is correct
37 Correct 82 ms 63312 KB Output is correct
38 Correct 75 ms 63228 KB Output is correct
39 Correct 77 ms 63184 KB Output is correct
40 Correct 70 ms 63240 KB Output is correct
41 Correct 86 ms 63316 KB Output is correct
42 Correct 72 ms 63052 KB Output is correct
43 Correct 80 ms 63044 KB Output is correct
44 Correct 66 ms 63052 KB Output is correct
45 Correct 64 ms 62548 KB Output is correct
46 Correct 66 ms 62548 KB Output is correct
47 Correct 65 ms 62544 KB Output is correct
48 Correct 65 ms 62544 KB Output is correct
49 Correct 65 ms 62548 KB Output is correct
50 Correct 13 ms 62044 KB Output is correct
51 Correct 66 ms 63528 KB Output is correct
52 Correct 477 ms 104116 KB Output is correct
53 Correct 484 ms 107776 KB Output is correct
54 Correct 426 ms 104388 KB Output is correct
55 Correct 425 ms 104392 KB Output is correct
56 Correct 442 ms 106952 KB Output is correct
57 Correct 80 ms 95708 KB Output is correct
58 Correct 98 ms 91360 KB Output is correct
59 Correct 98 ms 89408 KB Output is correct
60 Correct 106 ms 87612 KB Output is correct
61 Correct 127 ms 88880 KB Output is correct
62 Correct 203 ms 94876 KB Output is correct
63 Correct 220 ms 97384 KB Output is correct
64 Correct 215 ms 94876 KB Output is correct
65 Correct 327 ms 96312 KB Output is correct
66 Correct 387 ms 97016 KB Output is correct
67 Correct 13 ms 62108 KB Output is correct
68 Correct 82 ms 97992 KB Output is correct
69 Correct 584 ms 110588 KB Output is correct
70 Correct 604 ms 111368 KB Output is correct
71 Correct 550 ms 107616 KB Output is correct
72 Correct 651 ms 110636 KB Output is correct
73 Correct 566 ms 108820 KB Output is correct
74 Correct 230 ms 103068 KB Output is correct
75 Correct 213 ms 94920 KB Output is correct
76 Correct 260 ms 96456 KB Output is correct
77 Correct 227 ms 91180 KB Output is correct
78 Correct 223 ms 91848 KB Output is correct
79 Correct 302 ms 100404 KB Output is correct
80 Correct 266 ms 97648 KB Output is correct
81 Correct 265 ms 97748 KB Output is correct
82 Correct 379 ms 99524 KB Output is correct
83 Correct 370 ms 96908 KB Output is correct
84 Correct 13 ms 62048 KB Output is correct
85 Correct 140 ms 99188 KB Output is correct