oj.uz

답안 #983251

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
983251 2024-05-15T09:45:38 Z vjudge1 가로등 (APIO19_street_lamps) C++17
40 / 100
 130 ms 29796 KB 
#include<bits/stdc++.h>
#define sz size()
#define ll long long
using namespace std;
const ll N = 800800;

ll f[N], s[N], T = 1;
ll fget(ll i, ll res = 0)
{
    for(; i > 0; i -= (i & -i))
        res += f[i];
    return res;
}
void fupd(ll i, ll x)
{
    for(; i < N; i += (i & -i))
        f[i] = x;
}

ll get(ll l, ll r, ll res = 0)
{
    l += T - 1, r += T - 1;
    for(; l <= r; l >>= 1, r >>= 1)
    {
        if(l % 2 == 1) res = max(res, s[l++]);
        if(r % 2 == 0) res = max(res, s[r--]);
    }
    return res;
}
void upd(ll i, ll x)
{
    i += T - 1;
    s[i] = x;
    for(; i > 1; i >>= 1)
        s[i >> 1] = max(s[i], s[i ^ 1]);
}

ll cnt[205][205];
void solve()
{
    ll n, q, i, j, k;
    cin >> n >> q;
    while(T < n) T <<= 1;
    string s;
    cin >> s;

    ll a[n + 1], sum[n + 1] = {}, lst[n + 1] = {};
    for(i = 1; i <= n; ++i)
        a[i] = s[i - 1] - '0';

    if(n <= 200 && q <= 200)
    {
        for(i = 1; i <= n; ++i)
            for(j = i; j <= n; ++j)
            {
                if(!a[j]) break;
                ++cnt[i][j];
            }
        while(q--)
        {
            cin >> s;
            ll l, r;
            if(s == "toggle")
                cin >> l,
                    a[l] ^= 1;
            else
                cin >> l >> r,
                    cout << cnt[l][r - 1] << '\n';
            for(i = 1; i <= n; ++i)
                for(j = i; j <= n; ++j)
                {
                    if(!a[j]) break;
                    ++cnt[i][j];
                }
        }
        return;
    }

    string s1[q + 1];
    ll l1[q + 1], r1[q + 1];
    ll ok = 1;
    for(i = 1; i <= q; ++i)
    {
        cin >> s1[i] >> l1[i];
        if(s1[i] == "query")
        {
            cin >> r1[i];
            ok &= (r1[i] - l1[i] == 1);
        }
    }

    if(ok)
    {
        for(i = 1; i <= q; ++i)
        {
            s = s1[i];
            ll l = l1[i], r = r1[i];
            if(s == "toggle")
            {
                cin >> l;
                sum[l] += (i - lst[l]) * a[l];
                a[l] ^= 1;
                lst[l] = i;
                continue;
            }
            cin >> l >> r;
            cout << sum[l] + (i - lst[l]) * a[l] << '\n';
        }
        return;
    }

    for(i = 1; i <= q; ++i)
    {
        s = s1[i];
        ll l = l1[i], r = r1[i];
        if(s == "toggle")
        {
            fupd(l, 1);
            upd(l, i);
            continue;
        }
        ll ans = 0;
        if(fget(r - 1) - fget(l - 1) == r - l)
            ans = (i - get(l, r - 1));
        cout << ans << '\n';
    }

}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    solve();
}

Compilation message

street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:41:20: warning: unused variable 'k' [-Wunused-variable]
   41 |     ll n, q, i, j, k;
      |                    ^

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 18472 KB Output is correct
2 Correct 75 ms 18760 KB Output is correct
3 Correct 94 ms 19352 KB Output is correct
4 Correct 114 ms 28000 KB Output is correct
5 Correct 96 ms 28272 KB Output is correct
6 Correct 86 ms 27484 KB Output is correct
7 Correct 130 ms 28388 KB Output is correct
8 Correct 117 ms 29796 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 94 ms 18472 KB Output is correct
9 Correct 75 ms 18760 KB Output is correct
10 Correct 94 ms 19352 KB Output is correct
11 Correct 114 ms 28000 KB Output is correct
12 Correct 96 ms 28272 KB Output is correct
13 Correct 86 ms 27484 KB Output is correct
14 Correct 130 ms 28388 KB Output is correct
15 Correct 117 ms 29796 KB Output is correct
16 Correct 2 ms 8540 KB Output is correct
17 Incorrect 1 ms 8540 KB Output isn't correct
18 Halted 0 ms 0 KB -