Submission #598253

#	Time	Username	Problem	Language	Result	Execution time	Memory
598253		Ozy	Bridges (APIO19_bridges)	C++17	0 / 100	368 ms	2848 KiB

bridges

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)

#define w first
#define u second.first
#define v second.second

#define LIM 1000000007
#define MAX 50000

lli n,m,q,a,b,c,r,l,x,y;
pair< lli, pair<lli,lli> > arr[MAX+2];
lli  st[MAX*4],offset;

void update(lli pos, lli ini, lli fin, lli des, lli val) {
    lli mitad;

    if (ini > des || fin < des) return;
    if (ini == fin && ini == des) {
        st[pos] = val;
        return;
    }

    mitad = (ini+fin)/2;
    update(pos*2, ini, mitad, des, val);
    update((pos*2)+1, mitad+1, fin, des, val);
    st[pos] = min(st[pos*2], st[(pos*2)+1]);
}

lli query(lli pos, lli ini, lli fin, lli l, lli r) {

    if (ini > r || fin < l) return LIM;
    if (l <= ini && fin <= r) return st[pos];

    lli mitad = (ini+fin)/2;
    return min(query(pos*2, ini, mitad, l ,r),
               query((pos*2)+1, mitad+1, fin, l, r) );
}

lli b1 (lli ini,lli fin, lli val) {
    lli mitad,a;
    lli star = ini;

    lli ult = ini-1;
    while (ini <= fin) {
        mitad = (ini+fin)/2;
        a = query(1,1,offset,star,mitad);

        if (a <= val) {
            ult =  mitad;
            ini = mitad+1;
        }
        else fin = mitad-1;
    }
    return ult;
}

lli b2 (lli ini,lli fin, lli val) {
    lli mitad,a;
    lli star = fin-1;
    lli ult = fin;

    while (ini <= fin) {
        mitad = (ini+fin)/2;
        a = query(1,1,offset,mitad,star);

        if (a <= val) {
            ult =  mitad;
            fin = mitad-1;
        }
        else ini = mitad+1;
    }
    return ult;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    offset = 1;
    while (offset < n) offset *= 2;

    rep(i,1,m) {
        cin >> a >> b >> c;
        arr[i] = {c, {a,b} };
        st[offset+a-1] = c;
    }
    rep(i,offset+n, (offset*2)-1) st[i] = LIM;
    repa(i,offset-1,1) st[i] = min(st[i*2], st[(i*2)+1]);

    cin >> q;
    rep(Q, 1, q) {

        cin >> a >> b >> c;
        if (a == 1) {
            //actualiza
            x = arr[b].u;
            y = c;
            update(1,1,offset,x,y);
        }
        else {

            x = b1(b,n-1,c);
            x++;
            y = b2(1,b,c);
            a = x-y+1;
            cout << a << "\n";
        }
    }
}

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