oj.uz

Submission #568885

# Submission time Handle Problem Language Result Execution time Memory
568885 2022-05-26T10:02:33 Z shrimb Street Lamps (APIO19_street_lamps) C++17
60 / 100
 220 ms 62588 KB 
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")

#include"bits/stdc++.h"
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;

#define int long long
#define endl '\n'
#define mod 1000000007
//\
#define mod 1686876991

const int maxn = 300005;

int pre[maxn], A[maxn];

int Sparse[maxn][20];

int Query (int l, int r) {
    int d = (r - l + 1);
    int lg = log2(d);
    return max(Sparse[l][lg], Sparse[r - (1 << lg) + 1][lg]);
}

signed main () {
    cin.tie(0)->sync_with_stdio(0);

    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    if (n <= 100 and q <= 100) {
        vector<string> v;
        while (q--) {
            v.push_back(s);
            string t;
            cin >> t;
            if (t == "query") {
                int l, r, ans = 0;
                cin >> l >> r;
                for (auto i : v) {
                    bool good = 1;
                    for (int j = l - 1 ; j < r - 1 ; j++) {
                        if (i[j] == '0') good = 0;
                    }
                    ans += good;
                }
                cout << ans << endl;
            } else {
                int i;
                cin >> i;
                s[i-1] = '0'+((s[i-1]-'0')^1);
            }
        }
        return 0;
    }

    array<int, 3> Q[q];
    bool ST2 = 1;

    for (int i = 0 ; i < q ; i++) {
        string t;
        cin >> t >> Q[i][1];
        Q[i][0] = (t == "query");
        if (Q[i][0]) cin >> Q[i][2];
        else Q[i][2] = 0;
        if (Q[i][0] and Q[i][2] - Q[i][1] != 1) ST2 = 0;
        Q[i][2]-=2, Q[i][1]--;
    }
    if (ST2) {
        memset(pre, -1, sizeof pre);
        for (int i = 0 ; i < n ; i++) if (s[i] == '1') pre[i] = 0;
        int ct = 0;
        for (auto [t, l, r] : Q) {
            ct++;
            if (t) {
                int sm = A[l];
                if (pre[l] != -1) sm += ct - pre[l];
                cout << sm << endl;
            } else {
                if (pre[l] == -1) pre[l] = ct;
                else {
                    A[l] += ct - pre[l];
                    pre[l] = -1;
                }
            }
        }
        return 0;
    }

    for (int i = 0 ; i < n ; i++) {
        if (s[i] == '1') Sparse[i][0] = 0;
        else Sparse[i][0] = INT_MAX;
    }
    for (int i = 0 ; i < q ; i++) {
        if (!Q[i][0]) Sparse[Q[i][1]][0] = i + 1;
    }
    for (int j = 1 ; j < 20 ; j++) {
        for (int i = 0 ; i < n and i + (1 << j) <= n ; i++) Sparse[i][j] = max(Sparse[i][j - 1], Sparse[i + (1 << j - 1)][j-1]);
    }
    for (int i = 0 ; i < q ; i++) {
        if (Q[i][0]) {
            cout << max(0ll, i - Query(Q[i][1], Q[i][2]) + 1) << endl;
        }
    }
}

Compilation message

street_lamps.cpp:17:1: warning: multi-line comment [-Wcomment]
   17 | //\
      | ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:106:117: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  106 |         for (int i = 0 ; i < n and i + (1 << j) <= n ; i++) Sparse[i][j] = max(Sparse[i][j - 1], Sparse[i + (1 << j - 1)][j-1]);
      |                                                                                                                   ~~^~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 10560 KB Output is correct
2 Correct 79 ms 10548 KB Output is correct
3 Correct 99 ms 10564 KB Output is correct
4 Correct 89 ms 13152 KB Output is correct
5 Correct 98 ms 11100 KB Output is correct
6 Correct 74 ms 13020 KB Output is correct
7 Correct 102 ms 10676 KB Output is correct
8 Correct 130 ms 12008 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 128 ms 54696 KB Output is correct
6 Correct 156 ms 54868 KB Output is correct
7 Correct 201 ms 55012 KB Output is correct
8 Correct 214 ms 62588 KB Output is correct
9 Correct 72 ms 9624 KB Output is correct
10 Correct 83 ms 10500 KB Output is correct
11 Correct 76 ms 10656 KB Output is correct
12 Correct 209 ms 61196 KB Output is correct
13 Correct 220 ms 62560 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 66 ms 10560 KB Output is correct
9 Correct 79 ms 10548 KB Output is correct
10 Correct 99 ms 10564 KB Output is correct
11 Correct 89 ms 13152 KB Output is correct
12 Correct 98 ms 11100 KB Output is correct
13 Correct 74 ms 13020 KB Output is correct
14 Correct 102 ms 10676 KB Output is correct
15 Correct 130 ms 12008 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 128 ms 54696 KB Output is correct
21 Correct 156 ms 54868 KB Output is correct
22 Correct 201 ms 55012 KB Output is correct
23 Correct 214 ms 62588 KB Output is correct
24 Correct 72 ms 9624 KB Output is correct
25 Correct 83 ms 10500 KB Output is correct
26 Correct 76 ms 10656 KB Output is correct
27 Correct 209 ms 61196 KB Output is correct
28 Correct 220 ms 62560 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Incorrect 1 ms 468 KB Output isn't correct
31 Halted 0 ms 0 KB -