Submission #267761

#TimeUsernameProblemLanguageResultExecution timeMemory
267761blue다리 (APIO19_bridges)C++11
0 / 100
637 ms8184 KiB
#include <iostream>
using namespace std;

class segtree
{
public:
    int V = 0;
    int L;
    int R;
    segtree* left = NULL;
    segtree* right = NULL;

    void update(int x, int u)
    {
        if(L == R) V = u;
        else
        {
            if(x <= (L+R)/2) left->update(x, u);
            else right->update(x, u);
            V = min(left->V, right->V);
        }
    }

    int query(int l, int r) //rangemin
    {
        if(l <= L && R <= r) return V;
        if(r < L || R < l) return 0;
        return min(left->query(l, r), right->query(l, r));
    }

    segtree()
    {
        ;
    }

    segtree(int l, int r)
    {
        L = l;
        R = r;
        if(l == r) return;
        left = new segtree(l, (l+r)/2);
        right = new segtree((l+r)/2+1, r);
    }
};

int main()
{
    int n, m;
    cin >> n >> m;

    int u, v;
    int w[n+1];
    for(int i = 1; i <= n-1; i++) cin >> u >> v >> w[i];

    segtree S(1, n-1);
    for(int i = 1; i <= n-1; i++) S.update(i, w[i]);

    int q;
    cin >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> q >> u >> v; //query, weight, island
        if(q == 1)
        {
            S.update(u, v);
        }
        else
        {
            int X = v, Y = v;
            for(int Z = 20; Z >= 0; Z--)
            {
                if(X - (1 << Z) >= 1 && S.query(X - (1 << Z), X-1) >= u) X -= (1 << Z);
                if(Y + (1 << Z) <= n && S.query(Y, Y + (1 << Z) - 1) >= u) Y += (1 << Z);
            }
            cout << Y-X+1 << '\n';
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...