oj.uz

Submission #842390

# Submission time Handle Problem Language Result Execution time Memory
842390 2023-09-02T19:50:00 Z serifefedartar Osumnjičeni (COCI21_osumnjiceni) C++17
10 / 110
 405 ms 48100 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]];
    }

    for (int i = 0; i < LOGN; i++) {
        for (int j = 2; j <= N; j++)
            up[i][j] = max(up[i][j], up[i][j-1]);
    }
 
    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 368 ms 47948 KB Output is correct
2 Correct 369 ms 47888 KB Output is correct
3 Correct 358 ms 47316 KB Output is correct
4 Correct 368 ms 48100 KB Output is correct
5 Correct 384 ms 47540 KB Output is correct
6 Correct 53 ms 38868 KB Output is correct
7 Correct 60 ms 39068 KB Output is correct
8 Correct 66 ms 39028 KB Output is correct
9 Correct 71 ms 39116 KB Output is correct
10 Correct 77 ms 39044 KB Output is correct
11 Correct 175 ms 46100 KB Output is correct
12 Correct 160 ms 45260 KB Output is correct
13 Correct 163 ms 45444 KB Output is correct
14 Correct 283 ms 46948 KB Output is correct
15 Correct 263 ms 46280 KB Output is correct
16 Correct 4 ms 35160 KB Output is correct
17 Correct 57 ms 39116 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 47948 KB Output is correct
2 Correct 369 ms 47888 KB Output is correct
3 Correct 358 ms 47316 KB Output is correct
4 Correct 368 ms 48100 KB Output is correct
5 Correct 384 ms 47540 KB Output is correct
6 Correct 53 ms 38868 KB Output is correct
7 Correct 60 ms 39068 KB Output is correct
8 Correct 66 ms 39028 KB Output is correct
9 Correct 71 ms 39116 KB Output is correct
10 Correct 77 ms 39044 KB Output is correct
11 Correct 175 ms 46100 KB Output is correct
12 Correct 160 ms 45260 KB Output is correct
13 Correct 163 ms 45444 KB Output is correct
14 Correct 283 ms 46948 KB Output is correct
15 Correct 263 ms 46280 KB Output is correct
16 Correct 4 ms 35160 KB Output is correct
17 Correct 57 ms 39116 KB Output is correct
18 Incorrect 11 ms 35420 KB Output isn't correct
19 Halted 0 ms 0 KB -