oj.uz

답안 #216407

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
216407 2020-03-27T09:16:50 Z usachevd0 가로등 (APIO19_street_lamps) C++14
40 / 100
 127 ms 8972 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 INF32 = 1e9;
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];
        for (int i = 0; i < n; ++i)
            if (a0[i] == 1)
                when[i] = 0;
            else
                when[i] = INF32;
        for (int t = 1; t <= q; ++t)
        {
            auto &q = que[t];
            if (q.se == -1)
            {
                int i = q.fi;
                when[i] = t;
            }
        }
        for (int i = 0; i < n; ++i) cout << when[i] << ' '; cout << endl;
        const int logN = 19;
        const int N = 1 << logN;
        int sgt[2 * N];
        fill(sgt, sgt + 2 * N, INF32);
        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 (l += N, r += N; 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;
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:169:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
         for (int i = 0; i < n; ++i) cout << when[i] << ' '; cout << endl;
         ^~~
street_lamps.cpp:169:61: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
         for (int i = 0; i < n; ++i) cout << when[i] << ' '; cout << endl;
                                                             ^~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 288 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 3704 KB Output is correct
2 Correct 89 ms 3704 KB Output is correct
3 Correct 90 ms 3704 KB Output is correct
4 Correct 109 ms 7692 KB Output is correct
5 Correct 118 ms 7948 KB Output is correct
6 Correct 95 ms 7692 KB Output is correct
7 Correct 122 ms 7560 KB Output is correct
8 Correct 127 ms 8972 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 4480 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 288 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 100 ms 3704 KB Output is correct
9 Correct 89 ms 3704 KB Output is correct
10 Correct 90 ms 3704 KB Output is correct
11 Correct 109 ms 7692 KB Output is correct
12 Correct 118 ms 7948 KB Output is correct
13 Correct 95 ms 7692 KB Output is correct
14 Correct 122 ms 7560 KB Output is correct
15 Correct 127 ms 8972 KB Output is correct
16 Incorrect 9 ms 4480 KB Output isn't correct
17 Halted 0 ms 0 KB -