oj.uz

Submission #906626

# Submission time Handle Problem Language Result Execution time Memory
906626 2024-01-14T15:09:33 Z Itamar Bridges (APIO19_bridges) C++14
16 / 100
 682 ms 34812 KB 
#include <iostream>
using namespace std;
#include <vector>
#define vi vector<int>
#define ll long long
#include <algorithm>
#include <set>
#include <string>
#include <bitset>
#include <cmath>
#include <math.h>
#define pll pair<ll,ll>
#define vll vector<ll>
#define pi pair<int,int>
#include <map>
#include <queue>
#define x first
#define y second
#define pd pair<double,double>

const int siz = 1e5 + 1;
int ans[siz];
vi ed[siz];
vector<vi> e;
vector<vi> q2;
multiset<pi> fr[siz];

void dfs(int i, int b,bitset<siz>&v) {
    if (v[i])return;
    v[i] = 1;
    for (pi f : fr[i]) {
        if (f.y >= b) {
            dfs(f.x,b,v);
        }
    }
}
vi c[siz];
int my[siz];
void con(int a, int b) {
    int u = my[a], v = my[b];
    if (u == v)return;
    if (c[u].size() > c[v].size())swap(u, v);
    for (int i : c[u]) {
        my[i] = v;
        c[v].push_back(i);
    }
}
struct node {
    int l, r, mini, mid;
    node* sl, * sr;
    node(int li, int ri) {
        l = li, r = ri, mid = (l + r) / 2;
        if (l < r) {
            sl = new node(li, mid);
            sr = new node(mid + 1, ri);
            mini = min(sl->mini, sr->mini);
        }
        else {
            mini = e[l][0];
        }
    }
    void update(int i, int val) {
        if (l == r) {
            mini = val;
        }
        else {
            if (i <= mid)sl->update(i, val);
            else sr->update(i, val);
            mini = min(sl->mini, sr->mini);
        }
    }
    int query(int a, int b) {
        if (a > r || b < l)return 1e9 + 1;
        if (l >= a && r <= b)return mini;
        if (l == r)return 1e9+1;
        return min(sl->query(a, b), sr->query(a, b));
    }
};
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, d;
        cin >> u >> v >> d;
        u--, v--;
        fr[u].insert({ v,d });
        fr[v].insert({ u,d });
        ed[i] = { d,u,v };
        e.push_back({ d,u,v });
    }for (int i = 0; i < n; i++) {
        c[i].push_back(i);
        my[i] = i;
    }
    int q;
    cin >> q;
    if (n > 1) {
        node* seg;
        seg = new node(0, n - 2);
        for (int i = 0; i < q; i++) {
            int t, a, b;
            cin >> t >> a >> b;
            a--;
            if (t == 1) {
                seg->update(a, b);
            }
            else {
                if (n == 1) { cout << 1; continue; }
                int l1 = 0, r1 = a, l2 = a - 1, r2 = n - 2;
                while (l1 < r1) {
                    int mid = (l1 + r1) / 2;
                    if (seg->query(mid, a - 1) >= b) {
                        r1 = mid;
                    }
                    else l1 = mid + 1;
                }
                while (l2 < r2) {
                    int mid = (1 + l2 + r2) / 2;
                    if (seg->query(a, mid) >= b) {
                        l2 = mid;
                    }
                    else r2 = mid - 1;
                }
                cout << l2 - l1 + 2 << "\n";
            }
        }
    }else {
        for (int i = 0; i < q; i++) {
            int t, a, b;
            cin >> t >> a >> b;
            a--;
            if (t == 2)cout << 1 << "\n";
        }
    }
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 10076 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 369 ms 26048 KB Output is correct
2 Correct 382 ms 25568 KB Output is correct
3 Correct 352 ms 25756 KB Output is correct
4 Correct 350 ms 25688 KB Output is correct
5 Correct 350 ms 25792 KB Output is correct
6 Correct 369 ms 25936 KB Output is correct
7 Correct 378 ms 25960 KB Output is correct
8 Correct 351 ms 25604 KB Output is correct
9 Correct 24 ms 10076 KB Output is correct
10 Correct 378 ms 26664 KB Output is correct
11 Correct 368 ms 26540 KB Output is correct
12 Correct 604 ms 27324 KB Output is correct
13 Correct 130 ms 26880 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 26048 KB Output is correct
2 Correct 382 ms 25568 KB Output is correct
3 Correct 352 ms 25756 KB Output is correct
4 Correct 350 ms 25688 KB Output is correct
5 Correct 350 ms 25792 KB Output is correct
6 Correct 369 ms 25936 KB Output is correct
7 Correct 378 ms 25960 KB Output is correct
8 Correct 351 ms 25604 KB Output is correct
9 Correct 24 ms 10076 KB Output is correct
10 Correct 378 ms 26664 KB Output is correct
11 Correct 368 ms 26540 KB Output is correct
12 Correct 604 ms 27324 KB Output is correct
13 Correct 130 ms 26880 KB Output is correct
14 Incorrect 306 ms 20212 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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