Submission #769713

#	Time	Username	Problem	Language	Result	Execution time	Memory
769713		boyliguanhan	Bridges (APIO19_bridges)	C++17	16 / 100	920 ms	4736 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000100
int n,m,q, l[MAXN], r[MAXN], v[MAXN];
void build(int i, int rl, int rr) {
    if(i>2e5) return;
    l[i] = rl, r[i] = rr;
    if(rl!=rr)
        build(i*2,rl,rl+rr>>1),
        build(i*2+1,rl+rr+2>>1,rr);
}
void upd(int i, int p, int x) {
    if(i>2e5) return;
    if(l[i]==r[i]) return (void)(v[i]=x);
    if(p>r[i*2])
        upd(i*2+1,p,x);
    else upd(i*2,p,x);
    v[i]=min(v[i*2],v[i*2+1]);
}
int query(int i, int rl, int rr){
    if(i>2e5) return 2e9;
    if(rl>r[i]||l[i]>rr) return 2e9;
    if(rl<=l[i]&&r[i]<=rr) return v[i];
    return min(query(i*2,rl,rr),query(i*2+1,rl,rr));
}
signed main() {
    cin >> n >> m;
    build(1,1,m);
    for(int i = 1; i <= m; i++) {
        int a;
        cin >> a >> a >> a;
        upd(1,i,a);
    }
    cin >> q;
    while(q--) {
        int a,b,c;
        cin>>a>>b>>c;
        if(a-1){
            int l = 1, r = b, lpos;
            while(l<r) {
                int mid = l+r>>1;
                if(query(1,mid,b-1) >= c)
                    r = mid;
                else
                    l = mid+1;
            }
            lpos = l;
            l = b, r = n;
            while(l<r){
                int mid = l+r+2>>1;
                if(query(1, b, mid-1) >= c)
                    l = mid;
                else
                    r = mid-1;
            }
            cout << r-lpos+1 << '\n';
        } else upd(1,b,c);
    }
}

Compilation message (stderr)

bridges.cpp: In function 'void build(int, int, int)':
bridges.cpp:9:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    9 |         build(i*2,rl,rl+rr>>1),
      |                      ~~^~~
bridges.cpp:10:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   10 |         build(i*2+1,rl+rr+2>>1,rr);
      |                     ~~~~~^~
bridges.cpp: In function 'int main()':
bridges.cpp:41:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |                 int mid = l+r>>1;
      |                           ~^~
bridges.cpp:50:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |                 int mid = l+r+2>>1;
      |                           ~~~^~

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