Submission #511105

#	Time	Username	Problem	Language	Result	Execution time	Memory
511105		amukkalir	Bridges (APIO19_bridges)	C++17	16 / 100	1191 ms	5772 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
#define wek cerr << "wekwek" << endl;
 
const int INF = 1e9+1000; 
const int nax = 50000; // kalo m 2 kalinya 
int n, m; 
int tree[4*nax+5]; 
int a[nax+5]; 

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

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

        tree[idx] = min(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) return tree[idx]; 
    else {
        int m = (l+r)/2; 
        return min(rmq(idx<<1,l,m,from,to), rmq(idx<<1|1,m+1,r,from,to)); 
    }
}

void upd(int idx, int l, int r, int where, int val) {
    if(where < l || where > r) return; 
    else if(l == r) tree[idx] = val; 
    else {
        int m = (l+r)/2; 

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

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

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

void cek () {
    puts("-------"); 
    for(int i=1; i<=4*n; i++) cout<< i << " " << tree[i] << endl; 
    puts("-------"); 
}

signed main () {
    scanf("%d %d", &n, &m); 
 
    for(int i=1; i<=m; i++) {
        int u, v, d; 
        scanf("%d %d %d", &u,&v,&d); 
        //u == i dan v == i+1 
        a[i] = d; 
    }

    int q; scanf("%d", &q); 
    while(q--) {
        //cek(); 

        int tp; scanf("%d", &tp); 
        int x, w; scanf("%d%d", &x, &w); 
 
        if(tp==1) {
            a[x] = w; 
            upd(1, 1, n-1, x, w); 
 //           wek
        } else {    
            int r = x; 
            int l = x; 

            while(l-1 >= 1 && a[l-1] >= w) l--; 
            while(r+1 <= n && a[r] >= w) r++; 
            cerr << l << " " << r << endl; 
            int c = r - l + 1; 
            printf("%d\n", c); 
        }
        
    }
}

Compilation message (stderr)

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

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