oj.uz

Submission #216401

# Submission time Handle Problem Language Result Execution time Memory
216401 2020-03-27T09:11:12 Z usachevd0 Street Lamps (APIO19_street_lamps) C++14
40 / 100
 143 ms 9868 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;

void debug_out()
{
    cerr << endl;
}

template<typename T1, typename... T2> void debug_out(T1 A, T2... B)
{
    cerr << ' ' << A;
    debug_out(B...);
}

#ifdef DEBUG
    #define time(...) 42
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
    #define debug(...) 42
#endif

template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; }
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; }

const int maxN = 300005;
char a0[maxN];
pii que[maxN];

signed main()
{
#ifdef DEBUG
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    if (n <= 100 && q <= 100)
    {
        char t[q + 1][n];
        memset(t, 0, sizeof(t));
        string s;
        cin >> s;
        for (int i = 0; i < n; ++i) t[0][i] = s[i] - '0';
        for (int i = 1; i <= q; ++i)
        {
            memcpy(t[i], t[i - 1], sizeof(t[i]));
            string cmd;
            cin >> cmd;
            if (cmd == "toggle")
            {
                int j;
                cin >> j;
                --j;
                t[i][j] ^= 1;
            }
            else
            {
                int l, r;
                cin >> l >> r;
                r -= 2;
                l--;
                int ans = 0;
                for (int u = 0; u < i; ++u)
                {
                    bool ok = true;
                    for (int j = l; j <= r; ++j)
                    {
                        ok &= t[u][j];
                    }
                    if (ok) ++ans;
                }
                cout << ans << '\n';
            }
        }
        exit(0);
    }
    // normal
    string tmp;
    cin >> tmp;
    for (int i = 0; i < n; ++i) a0[i] = tmp[i] - '0';
    bool all_ones = true;
    bool toggle_to_one = true;
    int _a[n];
    for (int i = 0; i < n; ++i) _a[i] = a0[i];
    for (int t = 1; t <= q; ++t)
    {
        string cmd;
        cin >> cmd;
        auto &q = que[t];
        if (cmd == "toggle")
        {
            q.se = -1;
            cin >> q.fi;
            q.fi--;
            int i = q.fi;
            _a[i] ^= 1;
            toggle_to_one &= _a[i] == 1;
        }
        else
        {
            cin >> q.fi >> q.se;
            q.fi--;
            q.se -= 2;
            all_ones &= q.fi == q.se;
        }
    }
    if (all_ones)
    {
        int when[n], sum[n];
        memset(when, 0, sizeof(when));
        memset(sum, 0, sizeof(sum));
        for (int t = 1; t <= q; ++t)
        {
            auto &q = que[t];
            if (q.se == -1)
            {
                int i = q.fi;
                if (a0[i] == 0)
                {
                    when[i] = t;
                }
                else
                {
                    sum[i] += t - when[i];
                }
                a0[i] ^= 1;
            }
            else
            {
                int i = q.fi;
                cout << sum[i] + (a0[i] == 1 ? t - when[i] : 0) << '\n';
            }
        }
        exit(0);
    }
    if (toggle_to_one)
    {
        int when[n];
        memset(when, 0x3f, sizeof(when));
        for (int i = 0; i < n; ++i) if (a0[i] == 1) when[i] = 0;
        for (int t = 1; t <= q; ++t)
        {
            auto &q = que[t];
            if (q.se == -1)
            {
                int i = q.fi;
                when[i] = t;
            }
        }
        const int logN = 19;
        const int N = 1 << logN;
        int sgt[2 * N];
        memset(sgt, 0x3f, sizeof(sgt));
        for (int i = 0; i < n; ++i)
        {
            sgt[i + N] = when[i];
        }
        for (int v = N - 1; v >= 1; --v)
        {
            sgt[v] = max(sgt[v << 1], sgt[v << 1 | 1]);
        }
        for (int t = 1; t <= q; ++t)
        {
            auto &q = que[t];
            if (q.se != -1)
            {
                int l = q.fi;
                int r = q.se;
                int mx = -1e9;
                for (int L = l, R = r; L <= R; L >>= 1, R >>= 1)
                {
                    if (L & 1)  chkmax(mx, sgt[L++]);
                    if (!R & 1) chkmax(mx, sgt[R--]);
                }
                cout << max(0, t - mx) << '\n';
            }
        }
        exit(0);
    }

    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 4216 KB Output is correct
2 Correct 96 ms 4216 KB Output is correct
3 Correct 106 ms 4216 KB Output is correct
4 Correct 127 ms 8588 KB Output is correct
5 Correct 122 ms 8840 KB Output is correct
6 Correct 107 ms 8460 KB Output is correct
7 Correct 143 ms 8456 KB Output is correct
8 Correct 133 ms 9868 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4480 KB Output is correct
2 Incorrect 9 ms 4480 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 88 ms 4216 KB Output is correct
9 Correct 96 ms 4216 KB Output is correct
10 Correct 106 ms 4216 KB Output is correct
11 Correct 127 ms 8588 KB Output is correct
12 Correct 122 ms 8840 KB Output is correct
13 Correct 107 ms 8460 KB Output is correct
14 Correct 143 ms 8456 KB Output is correct
15 Correct 133 ms 9868 KB Output is correct
16 Correct 8 ms 4480 KB Output is correct
17 Incorrect 9 ms 4480 KB Output isn't correct
18 Halted 0 ms 0 KB -