oj.uz

Submission #983277

# Submission time Handle Problem Language Result Execution time Memory
983277 2024-05-15T09:54:19 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
40 / 100
 115 ms 24032 KB 
#include<bits/stdc++.h>
#define sz size()
#define ll long long
using namespace std;
const ll N = 4e6;

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

# 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 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 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

# Verdict Execution time Memory Grader output
1 Correct 67 ms 15312 KB Output is correct
2 Correct 72 ms 15296 KB Output is correct
3 Correct 77 ms 15440 KB Output is correct
4 Correct 91 ms 22500 KB Output is correct
5 Correct 95 ms 23012 KB Output is correct
6 Correct 82 ms 22516 KB Output is correct
7 Correct 101 ms 22392 KB Output is correct
8 Correct 115 ms 24032 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12888 KB Output isn't correct
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 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 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 67 ms 15312 KB Output is correct
9 Correct 72 ms 15296 KB Output is correct
10 Correct 77 ms 15440 KB Output is correct
11 Correct 91 ms 22500 KB Output is correct
12 Correct 95 ms 23012 KB Output is correct
13 Correct 82 ms 22516 KB Output is correct
14 Correct 101 ms 22392 KB Output is correct
15 Correct 115 ms 24032 KB Output is correct
16 Correct 2 ms 12632 KB Output is correct
17 Incorrect 2 ms 12636 KB Output isn't correct
18 Halted 0 ms 0 KB -