Submission #974793

#	Time	Username	Problem	Language	Result	Execution time	Memory
974793		Abito	다리 (APIO19_bridges)	C++17	0 / 100	3050 ms	524288 KiB

bridges

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
#define int long long
typedef unsigned long long ull;
using namespace std;
const int N=5e4+5;
int n,m,tin[N],sz[N],tree[N],seg[4*N+5],par[N],c,w[N],idx,val,lx,rx,W,u[N],v[N];
void dfs(int x){
    c++;
    tin[x]=c;
    tree[c]=w[x];
    sz[x]=1;
    if (x*2<=n) dfs(x*2),sz[x]+=sz[x*2];
    if (x*2+1<=n) dfs(x*2+1),sz[x]+=sz[x*2+1];
    return;
}
void build(int x,int l,int r){
    if (l==r){
        seg[x]=tree[l];
        return;
    }
    int mid=(l+r)/2;
    build(x*2,l,mid);
    build(x*2+1,mid+1,r);
    seg[x]=min(seg[x*2],seg[x*2+1]);
    return;
}
void edit(int x,int l,int r){
    if (l==r){
        seg[x]=val;
        return;
    }int mid=(l+r)/2;
    if (idx<=mid) edit(x*2,l,mid);
    else edit(x*2+1,mid+1,r);
    seg[x]=min(seg[x*2],seg[x*2+1]);
    return;
}
int mn(int x,int l,int r){
    if (l>=lx && r<=rx) return seg[x];
    if (l>rx || r<lx) return INT_MAX;
    int mid=(l+r)/2;
    return min(mn(x*2,l,mid),mn(x*2+1,mid+1,r));
}
int query(int x){
    //cout<<x<<endl;
    if (sz[x]==1) return 1;
    lx=tin[x]+1,rx=lx+sz[x];
    if (mn(1,1,n)>=W) return sz[x];
    int ans=1;
    if (w[x*2]>=W) ans+=query(x*2);
    if (w[x*2+1]>=W) ans+=query(x*2+1);
    return ans;
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    w[1]=INT_MAX;
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        cin>>u[i]>>v[i]>>w[v[i]];
        par[v[i]]=u[i];
    }
    dfs(1);
    build(1,1,n);
    int q;cin>>q;
    while (q--){
        int t,x,y;cin>>t>>x>>y;
        if (t==1){
            x=v[x];
            idx=tin[x],val=y;
            w[x]=y;
            edit(1,1,n);
            continue;
        }
        while (x>1){
            if (w[x]>=y) x=par[x];
            else break;
        }
        W=y;
        //cout<<x<<endl;
        cout<<query(x)<<endl;
    }
    return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27