Submission #510824

#	Time	Username	Problem	Language	Result	Execution time	Memory
510824		amukkalir	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	518 ms	732 KiB

street_lamps

#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 nax = 3e5; 
const int INF = 5*nax;
int n, q; 
int tree[4*nax+5]; 
int s[nax+5]; 
int mn[nax+5]; //mulai nyala kapan 

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

void build(int idx, int l, int r) {
    if(r==l) {
        tree[idx] = mn[l]; 
        //cerr << l << " " << tree[idx] << endl ; 
    }
    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 -1; 
    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; 
    }
}

signed main () {
    scanf("%d %d", &n, &q); 
    for(int i=1; i<=n; i++) {
        int x; 
        scanf("%1d", &x); 
        s[i] = x; 

        if(s[i]) mn[i] = 0; 
        else mn[i] = INF; 
    }

    build(1, 1, n); 

    for(int t=1; t<=q; t++) {
        string ts; cin >> ts; 
        if(ts == "query") {
            int a, b; scanf("%d %d", &a, &b); 
            int ans = rmq(1, 1, n, a, b-1); 
            //cerr << ans << endl; 
            if(ans > t) ans = 0; 
            else ans = t-ans; 

            assert(0 <= ans && ans <= t); 

            printf("%d\n", ans); 

        } else {
            int x; scanf("%d", &x);            
            upd(1, 1, n, x, t); 
        }
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'void build(int, int, int)':
street_lamps.cpp:27:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |         int m = l+r >> 1;
      |                 ~^~
street_lamps.cpp: In function 'void upd(int, int, int, int, int)':
street_lamps.cpp:37:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         int m = l+r >> 1;
      |                 ~^~
street_lamps.cpp: In function 'int rmq(int, int, int, int, int)':
street_lamps.cpp:51:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |         int m = l+r >> 1;
      |                 ~^~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         scanf("%1d", &x);
      |         ~~~~~^~~~~~~~~~~
street_lamps.cpp:74:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |             int a, b; scanf("%d %d", &a, &b);
      |                       ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:85:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |             int x; scanf("%d", &x);
      |                    ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20