oj.uz

Submission #511105

# Submission time Handle Problem Language Result Execution time Memory
511105 2022-01-15T06:05:19 Z amukkalir Bridges (APIO19_bridges) C++17
16 / 100
 1191 ms 5772 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 573 ms 4368 KB Output is correct
2 Correct 409 ms 4420 KB Output is correct
3 Correct 380 ms 4364 KB Output is correct
4 Correct 363 ms 4404 KB Output is correct
5 Correct 369 ms 4448 KB Output is correct
6 Correct 1045 ms 4264 KB Output is correct
7 Correct 807 ms 4472 KB Output is correct
8 Correct 598 ms 4388 KB Output is correct
9 Correct 657 ms 2180 KB Output is correct
10 Correct 837 ms 3344 KB Output is correct
11 Correct 719 ms 3312 KB Output is correct
12 Correct 1191 ms 4884 KB Output is correct
13 Correct 172 ms 3784 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 398 ms 3752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 730 ms 5772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 573 ms 4368 KB Output is correct
2 Correct 409 ms 4420 KB Output is correct
3 Correct 380 ms 4364 KB Output is correct
4 Correct 363 ms 4404 KB Output is correct
5 Correct 369 ms 4448 KB Output is correct
6 Correct 1045 ms 4264 KB Output is correct
7 Correct 807 ms 4472 KB Output is correct
8 Correct 598 ms 4388 KB Output is correct
9 Correct 657 ms 2180 KB Output is correct
10 Correct 837 ms 3344 KB Output is correct
11 Correct 719 ms 3312 KB Output is correct
12 Correct 1191 ms 4884 KB Output is correct
13 Correct 172 ms 3784 KB Output is correct
14 Incorrect 398 ms 3752 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -