oj.uz

Submission #982534

# Submission time Handle Problem Language Result Execution time Memory
982534 2024-05-14T11:06:11 Z Tuanlinh123 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 5000 ms 50976 KB 
#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;

const ll maxn=300005;
vector <ll> upd[maxn];
vector <pll> H[maxn], Q[maxn];
ll a[maxn], last[maxn], answer[maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, q; cin >> n >> q;
    for (ll i=1; i<=n; i++) {char c; cin >> c; a[i]=c=='1';}
    for (ll i=1; i<=q; i++) answer[i]=-1;
    for (ll i=1; i<=q; i++)
    {
        string t; cin >> t;
        if (t=="query") {ll l, r; cin >> l >> r, Q[r-1].pb({l, i}), answer[i]=0;}
        else {ll x; cin >> x, upd[x].pb(i);}
    }
    for (ll i=1; i<=n; i++)
    {
        upd[i].pb(q);
        for (ll j=0, s=a[i]; j<sz(upd[i]); j++, s^=1)
            if (!s) H[i].pb({j?upd[i][j-1]+1:1, upd[i][j]});
    }
    for (ll i=1; i<=n; i++)
    {
        for (auto [l, r]:H[i])
            for (ll j=l; j<=r; j++)
                last[j]=i+1;
        for (auto [l, id]:Q[i])
            for (ll j=1; j<=id; j++)
                if (last[j]<=l) answer[id]++;
    }
    for (ll i=1; i<=q; i++)
        if (answer[i]>=0) cout << answer[i] << "\n";
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 24924 KB Output is correct
2 Correct 7 ms 24772 KB Output is correct
3 Correct 6 ms 24924 KB Output is correct
4 Correct 6 ms 24924 KB Output is correct
5 Correct 6 ms 24760 KB Output is correct
6 Correct 6 ms 24924 KB Output is correct
7 Correct 5 ms 22876 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5067 ms 31568 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 24920 KB Output is correct
2 Correct 6 ms 24920 KB Output is correct
3 Correct 7 ms 24924 KB Output is correct
4 Correct 6 ms 22876 KB Output is correct
5 Execution timed out 5039 ms 48004 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 24924 KB Output is correct
2 Correct 6 ms 24924 KB Output is correct
3 Correct 7 ms 24924 KB Output is correct
4 Correct 6 ms 24924 KB Output is correct
5 Execution timed out 5074 ms 50976 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 24924 KB Output is correct
2 Correct 7 ms 24772 KB Output is correct
3 Correct 6 ms 24924 KB Output is correct
4 Correct 6 ms 24924 KB Output is correct
5 Correct 6 ms 24760 KB Output is correct
6 Correct 6 ms 24924 KB Output is correct
7 Correct 5 ms 22876 KB Output is correct
8 Execution timed out 5067 ms 31568 KB Time limit exceeded
9 Halted 0 ms 0 KB -