Submission #510948

#	Time	Username	Problem	Language	Result	Execution time	Memory
510948		amukkalir	Bridges (APIO19_bridges)	C++17	0 / 100	7 ms	1260 KiB

bridges

#include <bits/stdc++.h>
using namespace std; 
typedef long long ll; 
#define pii pair<int,int> 
#define fi first 
#define se second 
#define pb push_back 
#define mp make_pair

const int INF = 1e9+1000; 
const int nax = 1000; 
int n, m; 
int a[nax+5]; 
int tree[4*nax+5]; 
vector<pair<int,pii>> b; 

int merge(int a, int b) {
    return min(a,b); 
}

void build(int idx, int l, int r) {
    if(r==l) {
        tree[idx] = a[l]; 
    }
    else {
        int m = (l+r) >> 1; 

        build(idx<<1,l,m); 
        build(idx<<1|1, m+1, r); 

        tree[idx] = merge(tree[idx<<1], tree[idx<<1|1]); 
    }
}

void upd(int idx, int l, int r, int where, int val) {
    if(r==l) tree[idx] = val; 
    else if (l <= where && where <= r) {
        int m = (l+r) >> 1; 

        upd(idx<<1, l, m, where, val); 
        upd(idx<<1|1, m+1, r, where, val); 

        tree[idx] = merge(tree[idx<<1], tree[idx<<1|1]);
    }
}

int rmq(int idx, int l, int r, int from, int to) {
    if(to < l || from > r) return INF; 
    else if(from <= l && r <= to) {
        //cerr << l << " " << r << " returns " << tree[idx] << endl; 
        return tree[idx]; 
    }
    else {
        int m = (l+r) >> 1; 
        int ret = merge(rmq(idx<<1,l,m,from,to), rmq(idx<<1|1,m+1,r,from,to)); 
        //cerr << l << " " << r << " returns " << ret << endl; 
        return ret; 
    }
}

int rmost (int x, int w) {
//cerr << " :: " << x << " " << w << endl; 

    int lo = x, hi = n-1; 
    int ret = x; 

    while(lo <= hi) {
        int mid = (lo+hi)/2; 
//cerr << mid << "? " << rmq(1, 1, n, x, mid) << endl; 
        if(w <= rmq(1, 1, n, x, mid)) {
            ret = mid+1; 
            lo = mid+1; 
        } else {
            hi = mid-1; 
        }
    }
    return ret; 
}

int lmost (int x, int w) {
    int lo = 1, hi = x; 
    int ret = x; 
    while(lo <= hi) {
        int mid = (lo+hi)/2; 
        if(w <= rmq(1,1,n,mid,x)) {
            ret = mid; 
            hi = mid-1; 
        } else {
            lo = mid+1; 
        }
    }
    return ret; 
}

signed main () {
    scanf("%d %d", &n, &m); 

    b.pb(mp(0, mp(0,0))); 
    for(int i=1; i<=m; i++) {
        int u, v, d; 
        scanf("%d %d %d", &u,&v,&d); 
        a[u] = d; 
        b.pb(mp(d, mp(u, v))); 
    }

    build(1, 1, n); 

    int q; scanf("%d", &q); 
    while(q--) {
        int tp; scanf("%d", &tp); 
        int x, w; scanf("%d%d", &x, &w); 

        if(tp==1) {
            b[x].fi = w; 
            upd(1, 1, n, b[x].se.fi, w); 
        } else {    
            int l = lmost(x, w); 
            int r = rmost(x, w); 
//cerr <<  " >> " << l << "  " << r << endl; 
            int c = r-l+1; 
            
            printf("%d\n", c); 
        }
    }
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         scanf("%d %d %d", &u,&v,&d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:108:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |     int q; scanf("%d", &q);
      |            ~~~~~^~~~~~~~~~
bridges.cpp:110:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         int tp; scanf("%d", &tp);
      |                 ~~~~~^~~~~~~~~~~
bridges.cpp:111:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         int x, w; scanf("%d%d", &x, &w);
      |                   ~~~~~^~~~~~~~~~~~~~~~

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