Submission #511016

#	Time	Username	Problem	Language	Result	Execution time	Memory
511016		amukkalir	다리 (APIO19_bridges)	C++17	0 / 100	289 ms	524292 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 = 50000; // kalo m 2 kalinya 
int n, m; 
int tree[4*nax+5]; 
vector<pair<int,pii>> b; 
int a[nax+5]; 

void build(int idx, int l, int r) {
    if(l == r) tree[idx] = a[l]; 
    else {
        int m = (l+r) >> 1; 
        build (idx << 1, l, m); 
        build(idx << 1 | 1, m+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 && to <= r) 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; 
        if(where <= m) upd(idx<<1,l,m,where,val); 
        else 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 << "? " << 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; 
        if(w <= rmq(1,1,n-1,mid,x-1)) {
            ret = mid; 
            hi = mid-1; 
        } else {
            lo = mid+1; 
        }
    }
    return ret; 
}
 

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; 
    }
    
    build(1, 1, n-1); 

    int q; scanf("%d", &q); 
    while(q--) {
        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); 
        } else {    
            int r = rmost(x, w); 
            int l = lmost(x, w); 
            //cerr << l << " " << r << endl; 
            int c = rmost(x,w) - lmost(x,w) + 1; 
            printf("%d\n", c); 
        }
    }
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:101:17: warning: unused variable 'r' [-Wunused-variable]
  101 |             int r = rmost(x, w);
      |                 ^
bridges.cpp:102:17: warning: unused variable 'l' [-Wunused-variable]
  102 |             int l = lmost(x, w);
      |                 ^
bridges.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         scanf("%d %d %d", &u,&v,&d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:92:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |     int q; scanf("%d", &q);
      |            ~~~~~^~~~~~~~~~
bridges.cpp:94:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         int tp; scanf("%d", &tp);
      |                 ~~~~~^~~~~~~~~~~
bridges.cpp:95:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         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