Submission #920506

#	Time	Username	Problem	Language	Result	Execution time	Memory
920506		boris_mihov	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	482 ms	1288 KiB

street_lamps

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>

typedef long long llong;
const int MAXN = 100 + 10;
const int INF  = 1e9;

int n, q;
char a[MAXN];
char s[MAXN];
int t[MAXN][MAXN];
bool state[MAXN][MAXN];

void update(int fromX, int fromY, int toX, int toY, int val)
{
    fromX--; fromY--;
    t[toX][toY] += val;
    t[fromX][toY] -= val;
    t[toX][fromY] -= val;
    t[fromX][fromY] += val;
    state[toX][toY] ^= 1;
    state[fromX][toY] ^= 1;
    state[toX][fromY] ^= 1;
    state[fromX][fromY] ^= 1;
}

int query(int r, int c, int time)
{
    int res = 0;
    for (int i = r ; i <= n ; ++i)
    {
        for (int j = c ; j <= n ; ++j)
        {
            res += t[i][j];
        }
    }

    int myState = 0;
    for (int i = r ; i <= n ; ++i)
    {
        for (int j = c ; j <= n ; ++j)
        {
            myState ^= state[i][j];
        }
    }

    if (myState == 1)
    {
        res += time + 1;
    }
    
    return res;
}

void toggle(int idx, int time)
{
    int lPos = idx - 1;
    while (lPos > 0 && s[lPos] == '1')
    {
        lPos--;
    } 

    lPos++;

    int rPos = idx + 1;
    while (rPos <= n && s[rPos] == '1')
    {
        rPos++;
    } 

    rPos--;
    update(lPos, idx, idx, rPos, (s[idx] == '1' ? time + 1 : -time - 1));
    s[idx] = '0' + ('1' - s[idx]);
}

void solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        s[i] = '0';
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        if (a[i] == '1')
        {
            toggle(i, 0);
        }
    }

    for (int i = 1 ; i <= q ; ++i)
    {
        std::string qType;
        std::cin >> qType;

        if (qType == "toggle")
        {
            int pos;
            std::cin >> pos;
            toggle(pos, i);
        } else
        {
            int l, r;
            std::cin >> l >> r;
            std::cout << query(l, r - 1, i) << '\n';
        }
    }
}

void input()
{
    std::cin >> n >> q;
    std::cin >> a + 1;
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'void input()':
street_lamps.cpp:115:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  115 |     std::cin >> a + 1;
      |                 ~~^~~

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