Submission #934055

#	Time	Username	Problem	Language	Result	Execution time	Memory
934055		vjudge1	Bridges (APIO19_bridges)	C++98	16 / 100	456 ms	1616 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int arr[50001];

struct ST{
    int tree[200001];

    void build(int node, int l, int r){
        if(l==r){
            tree[node]=arr[l];
            return;
        }
        build(2*node+1, l, (l+r)/2);
        build(2*node+2, (l+r)/2+1, r);
        tree[node]=min(tree[2*node+1], tree[2*node+2]);
    }

    void update(int node, int l, int r, int pos, int x){
        if(r<pos || l>pos)
            return;
        if(l==r){
            tree[node]=x;
            return;
        }
        update(2*node+1, l, (l+r)/2, pos, x);
        update(2*node+2, (l+r)/2+1, r, pos, x);
        tree[node]=min(tree[2*node+1], tree[2*node+2]);
    }

    int query(int node, int l, int r, int a, int b){
        if(l>b || r<a)
            return (1<<30);
        if(l>=a && r<=b){
            return tree[node];
        }
        return min(query(2*node+1, l, (l+r)/2, a, b), query(2*node+2, (l+r)/2+1, r, a, b));
    }
};

int n, m, q;
ST tree;

int buscaizq(int l, int r, int pos, int x){
    int mid;
    while(l<r){
        mid=(l+r+1)/2;
        if(pos-mid>=0 && tree.query(0, 0, n-1, pos-mid, pos-1)>=x)
            l=mid;
        else
            r=mid-1;
    }
    return l;
}

int buscadere(int l, int r, int pos, int x){
    int mid;
    while(l<r){
        mid=(l+r+1)/2;
        if(pos+mid<n && tree.query(0, 0, n-1, pos+1, pos+mid)>=x)
            l=mid;
        else
            r=mid-1;
    }
    return l;
}

void solve(){
    cin>> n>> m;
    int t, a, b, c, x, y;
    for(int i=0; i<m; i++){
        cin>> a>> b>> c;
        arr[i]=c;
    }
    tree.build(0, 0, n-1);
    cin>> q;
    for(int i=0; i<q; i++){
        cin>> t>> a>> b;
        a--;
        if(t==1){
            tree.update(0, 0, n-1, a, b);
        }
        else{
            x=buscaizq(0, n-1, a, b);
            y=buscadere(0, n-1, a-1, b);
            cout<< x+y+1<< "\n";
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin.tie(0);
    int t=1;
    //cin>> t;
    while(t--){
        solve();
    }
    return 0;
}

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