oj.uz

Submission #920506

# Submission time Handle Problem Language Result Execution time Memory
920506 2024-02-02T16:19:17 Z boris_mihov Street Lamps (APIO19_street_lamps) C++17
20 / 100
 482 ms 1288 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 1288 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 482 ms 1288 KB Output is correct
9 Runtime error 1 ms 604 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -