Submission #511077

#	Time	Username	Problem	Language	Result	Execution time	Memory
511077		amukkalir	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	758 ms	14660 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 = 3*nax; 
int n, q; 
int s[nax+5]; 
int mn[nax+5]; 
int tree[4*nax+5]; 

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

void build(int idx, int l, int r) {
    if(l == r) tree[idx] = mn[l]; 
    else {
        int m = (l+r)/2; 
        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) {
    //hrsnya l <= where <= r
    if(r < where || l > where) {
        return; 
    } else if(r == l && r == where) 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] = merge(tree[idx<<1], tree[idx<<1|1]); 
    }
}

int query(int idx, int l, int r, int from, int to) {
    if(r < from || l > to) return -1; 
    else if(from <= l && r <= to) return tree[idx]; 
    else {
        int m = (l+r)/2; 
        return merge (
            query(idx<<1, l, m, from, to), 
            query(idx<<1|1, m+1, r, from, to)
        ); 
    }
}

signed main () {
    scanf("%d %d", &n, &q); 

    for(int i=1; i<=n; i++) {
        scanf("%1d", &s[i]); 
        if(s[i]) mn[i] = 0; 
        else mn[i] = INF; 
    }

    build(1, 1, n); 

    for(int i=1; i<=q; i++) {
        string type; cin >> type; 

        if(type == "query") {
            int a, b; scanf("%d %d", &a, &b); 
            //segments between them are a, a+1, a+2, ... b-1 

            int ans = query(1, 1, n, a, b-1); 
            if(ans > i) ans = 0; 
            else ans = i-ans; 

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

        } else {
            int x; scanf("%d", &x); 
            s[x] ^= 1; 
            if(s[x]) { //which should be all the case here for subtask 3
                mn[x] = i; //segment ini nyala waktu i 
                upd(1, 1, n, x, i); 

            } else {
                //?? 
            }
        }
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%1d", &s[i]);
      |         ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:72:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |             int a, b; scanf("%d %d", &a, &b);
      |                       ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:82:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |             int x; scanf("%d", &x);
      |                    ~~~~~^~~~~~~~~~

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