Submission #1228920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228920		Jer	Street Lamps (APIO19_street_lamps)	C++20	20 / 100	271 ms	11152 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 300005;
int n, q;
bool on[MAXN];

pair<int, bool> tree[4 * MAXN];

#define ff first
#define ss second

pair<int, bool> merge(const pair<int, bool> &a, const pair<int, bool> &b)
{
    return {max(a.ff, b.ff), a.ss && b.ss};
}

void build(int v, int l, int r)
{
    if (l == r)
        return void(tree[v] = {0, on[l]});

    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    tree[v] = merge(tree[2 * v], tree[2 * v + 1]);
}

void update(int v, int l, int r, int pos, pair<int, bool> val)
{
    if (l == r)
    {
        on[pos] = val.ss;
        return void(tree[v] = val);
    }
    int m = (l + r) / 2;
    if (pos <= m)
        update(2 * v, l, m, pos, val);
    else
        update(2 * v + 1, m + 1, r, pos, val);
    tree[v] = merge(tree[2 * v], tree[2 * v + 1]);
}

pair<int, bool> query(int v, int tl, int tr, int l, int r)
{
    if (l > r)
        return {0, true};
    if (l == tl and r == tr)
        return tree[v];

    int m = (tl + tr) / 2;
    pair<int, bool> left = query(2 * v, tl, m, l, min(r, m));
    pair<int, bool> right = query(2 * v + 1, m + 1, tr, max(l, m + 1), r);

    return merge(left, right);
}

bool scan_ev()
{
    char c;
    scanf(" %c", &c);
    if (c == 't')
    {
        for (int i = 0; i < 5; i++)
            scanf(" %c", &c);
        return true;
    }

    for (int i = 0; i < 4; i++)
        scanf(" %c", &c);
    return false;
}

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

    char s[MAXN];
    scanf(" %s", &s);
    for (int i = 0; i < n; i++)
        on[i] = s[i] - '0';

    build(1, 0, n - 1);

    int a, b, c;
    for (int h = 1; h <= q; h++)
    {
        if (scan_ev())
        {
            scanf("%d", &c);
            c--;
            update(1, 0, n - 1, c, {h, !on[c]});
        }
        else
        {
            scanf("%d%d", &a, &b);
            a--, b--;
            pair<int, bool> res = query(1, 0, n - 1, a, b - 1);
            printf("%d\n", (res.ss) ? h - res.ff : 0);
        }
    }

    return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:80:14: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[300005]' [-Wformat=]
   80 |     scanf(" %s", &s);
      |             ~^   ~~
      |              |   |
      |              |   char (*)[300005]
      |              char*
street_lamps.cpp: In function 'bool scan_ev()':
street_lamps.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     scanf(" %c", &c);
      |     ~~~~~^~~~~~~~~~~
street_lamps.cpp:66:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |             scanf(" %c", &c);
      |             ~~~~~^~~~~~~~~~~
street_lamps.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         scanf(" %c", &c);
      |         ~~~~~^~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |     scanf(" %s", &s);
      |     ~~~~~^~~~~~~~~~~
street_lamps.cpp:91:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |             scanf("%d", &c);
      |             ~~~~~^~~~~~~~~~
street_lamps.cpp:97:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |             scanf("%d%d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~

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