oj.uz

Submission #842375

# Submission time Handle Problem Language Result Execution time Memory
842375 2023-09-02T19:30:58 Z serifefedartar Osumnjičeni (COCI21_osumnjiceni) C++17
10 / 110
 432 ms 51572 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 22
#define MAXN 400005
 
int sg[4*MAXN], lazy[4*MAXN];
int up[LOGN][MAXN];
vector<pair<int,int>> segments;
vector<int> cc;

void update(int k, int a, int b, int q_l, int q_r, int val) {
    if (lazy[k]) {
        sg[k] += lazy[k];
        if (a != b) {
            lazy[2*k] += lazy[k];
            lazy[2*k+1] += lazy[k];
        }
        lazy[k] = 0;
    }
 
    if (b < q_l || a > q_r)
        return ;
    if (q_l <= a && b <= q_r) {
        sg[k] += val;
        if (a != b) {
            lazy[2*k] += val;
            lazy[2*k+1] += val;
        }
        return ;
    }
    update(2*k, a, (a+b)/2, q_l, q_r, val);
    update(2*k+1, (a+b)/2+1, b, q_l, q_r, val);
    sg[k] = max(sg[2*k], sg[2*k+1]);
}
 
int index(int k) {
    return upper_bound(cc.begin(), cc.end(), k) - cc.begin();
}
 
int main() {
    fast
    int N;
    cin >> N;
    
    segments = vector<pair<int,int>>(N+1);
    for (int i = 1; i <= N; i++) {
        cin >> segments[i].f >> segments[i].s;
        cc.push_back(segments[i].f);
        cc.push_back(segments[i].s);
    }
    sort(cc.begin(), cc.end());
    cc.erase(unique(cc.begin(), cc.end()), cc.end());
    int n = cc.size();

    int L = 1;
    for (int R = 1; R <= N; R++) {
        update(1, 1, n, index(segments[R].f), index(segments[R].s), 1);
        while (sg[1] > 1) {
            up[0][L] = R;
            update(1, 1, n, index(segments[L].f), index(segments[L].s), -1);
            L++;
        }
    }
    for (int i = 1; i <= N; i++) {
        if (up[0][i] == 0)
            up[0][i] = N+1;
    }
 
    for (int i = 0; i < LOGN; i++)
        up[i][N+1] = N+1;
    for (int i = 1; i < LOGN; i++) {
        for (int j = 1; j <= N; j++)
            up[i][j] = up[i-1][up[i-1][j]];
    }
 
    int Q; 
    cin >> Q;
    while (Q--) {
        int a, b;
        cin >> a >> b;
        b = up[0][b];
 
        int cnt = 0;
        int now = a;
        for (int i = LOGN-1; i >= 0; i--) {
            if (up[i][now] < b) {
                now = up[i][now];
                cnt += (1<<i);
            }
        }
        cout << cnt + 1 << "\n";
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 47924 KB Output is correct
2 Correct 411 ms 51536 KB Output is correct
3 Correct 365 ms 50892 KB Output is correct
4 Correct 432 ms 51572 KB Output is correct
5 Correct 423 ms 51356 KB Output is correct
6 Correct 54 ms 42564 KB Output is correct
7 Correct 58 ms 42672 KB Output is correct
8 Correct 81 ms 42700 KB Output is correct
9 Correct 60 ms 42700 KB Output is correct
10 Correct 68 ms 42540 KB Output is correct
11 Correct 155 ms 49516 KB Output is correct
12 Correct 151 ms 48248 KB Output is correct
13 Correct 149 ms 48464 KB Output is correct
14 Correct 278 ms 50380 KB Output is correct
15 Correct 234 ms 49424 KB Output is correct
16 Correct 4 ms 35164 KB Output is correct
17 Correct 47 ms 43020 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 35416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 35416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 412 ms 47560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 47924 KB Output is correct
2 Correct 411 ms 51536 KB Output is correct
3 Correct 365 ms 50892 KB Output is correct
4 Correct 432 ms 51572 KB Output is correct
5 Correct 423 ms 51356 KB Output is correct
6 Correct 54 ms 42564 KB Output is correct
7 Correct 58 ms 42672 KB Output is correct
8 Correct 81 ms 42700 KB Output is correct
9 Correct 60 ms 42700 KB Output is correct
10 Correct 68 ms 42540 KB Output is correct
11 Correct 155 ms 49516 KB Output is correct
12 Correct 151 ms 48248 KB Output is correct
13 Correct 149 ms 48464 KB Output is correct
14 Correct 278 ms 50380 KB Output is correct
15 Correct 234 ms 49424 KB Output is correct
16 Correct 4 ms 35164 KB Output is correct
17 Correct 47 ms 43020 KB Output is correct
18 Incorrect 14 ms 35416 KB Output isn't correct
19 Halted 0 ms 0 KB -