oj.uz

Submission #772386

# Submission time Handle Problem Language Result Execution time Memory
772386 2023-07-04T04:54:34 Z phoebe Bridges (APIO19_bridges) C++17
16 / 100
 871 ms 9356 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define FOR(i, n) for (int i = 0; i < n; i++)
#define PB push_back
#define ALL(x) x.begin(), x.end()
#define NYOOM ios::sync_with_stdio(0); cin.tie(0);
const int INF = 1e9 + 7;

// solving ST 4: offline query 

const int maxn = 1e5 + 10;
int n, m, u[maxn], v[maxn], d[maxn], q, tree[maxn * 4];

void update(int x, int v, int tl = 0, int tr = maxn, int i = 1){
    if (tl > x || tr < x) return;
    if (tl == tr){
        tree[i] = v; return;
    }
    int tm = (tl + tr) / 2;
    update(x, v, tl, tm, i * 2); update(x, v, tm + 1, tr, i * 2 + 1);
    tree[i] = min(tree[i * 2], tree[i * 2 + 1]);
}

int query(int l, int r, int tl = 0, int tr = maxn, int i = 1){
    if (tl > r || tr < l) return INF;
    if (l <= tl && tr <= r) return tree[i];
    int tm = (tl + tr) / 2;
    return min(query(l, r, tl, tm, i * 2),
    query(l, r, tm + 1, tr, i * 2 + 1));
}

int get_left(int s, int w){
    int l = 1, r = s - 1, ans = s;
    while (l <= r){
        int mid = (l + r) / 2;
        int mn = query(mid, s - 1);
        if (mn >= w) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    return ans;
}

int get_right(int s, int w){
    int l = s + 1, r = n, ans = s;
    while (l <= r){
        int mid = (l + r) / 2;
        int mn = query(s, mid - 1);
        if (mn >= w) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    return ans;
}

signed main(){
    fill(tree, tree + maxn * 4, INF);
    NYOOM;
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        cin >> u[i] >> v[i] >> d[i];
        update(i, d[i]);
    }
    cin >> q;
    FOR(i, q){
        int t; cin >> t; 
        if (t == 1){
            int b, r; cin >> b >> r;
            update(b, r);
        }   
        if (t == 2){
            int s, w; cin >> s >> w;
            int left = get_left(s, w);
            int right = get_right(s, w);
            cout << right - left + 1 << endl;
        }
    }
}

Subtask #1
0 / 13.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 6676 KB Output is correct
2 Correct 433 ms 7460 KB Output is correct
3 Correct 401 ms 7396 KB Output is correct
4 Correct 429 ms 7520 KB Output is correct
5 Correct 403 ms 7520 KB Output is correct
6 Correct 496 ms 7432 KB Output is correct
7 Correct 465 ms 7396 KB Output is correct
8 Correct 471 ms 7444 KB Output is correct
9 Correct 129 ms 5020 KB Output is correct
10 Correct 497 ms 6436 KB Output is correct
11 Correct 500 ms 6408 KB Output is correct
12 Correct 871 ms 7452 KB Output is correct
13 Correct 162 ms 7376 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 6676 KB Output is correct
2 Correct 433 ms 7460 KB Output is correct
3 Correct 401 ms 7396 KB Output is correct
4 Correct 429 ms 7520 KB Output is correct
5 Correct 403 ms 7520 KB Output is correct
6 Correct 496 ms 7432 KB Output is correct
7 Correct 465 ms 7396 KB Output is correct
8 Correct 471 ms 7444 KB Output is correct
9 Correct 129 ms 5020 KB Output is correct
10 Correct 497 ms 6436 KB Output is correct
11 Correct 500 ms 6408 KB Output is correct
12 Correct 871 ms 7452 KB Output is correct
13 Correct 162 ms 7376 KB Output is correct
14 Incorrect 395 ms 6716 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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