oj.uz

Submission #253524

# Submission time Handle Problem Language Result Execution time Memory
253524 2020-07-28T06:48:06 Z SorahISA Street Lamps (APIO19_street_lamps) C++17
20 / 100
 281 ms 15244 KB 
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define double long double
using pii = pair<int, int>;
template<typename T>
using Prior = priority_queue<T>;
template<typename T>
using prior = priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back
#define fastIO() ios_base::sync_with_stdio(false), cin.tie(0)

#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)

const int maxn = 1 << 19;
const int INF = 0x7f7f7f7f;

int seg[maxn << 1];
/// single modify, range maximum ///

int Query(int qL, int qR, int id = 1, int nL = 0, int nR = maxn-1) {
    if (qL <= nL and nR <= qR) return seg[id];
    if (qR < nL or nR < qL) return -1; /// return any number <= 0 ///
    
    int nM = nL + nR >> 1;
    return max(Query(qL, qR, ls(id), nL,     nM),
               Query(qL, qR, rs(id), nM + 1, nR));
}

int32_t main() {
    fastIO();
    
    int n, q, x, l, r;
    string s, op;
    cin >> n >> q >> s;
    
    for (int i = 0, j = maxn; i < n; ++i, ++j) {
        seg[j] = (s[i] == '0' ? INF : 0);
    }
    for (int j = maxn-1; j >= 1; --j) {
        seg[j] = max(seg[ls(j)], seg[rs(j)]);
    }
    
    for (int i = 1; i <= q; ++i) {
        cin >> op;
        if (op == "toggle") {
            cin >> x, x += maxn - 1;
            seg[x] = i;
            while (x >>= 1) seg[x] = max(seg[ls(x)], seg[rs(x)]);
        }
        if (op == "query") {
            cin >> l >> r, l -= 1, r -= 2;
            int ans = Query(l, r);
            cout << (ans == INF ? 0 : i - ans) << "\n";
        }
    }
    
    return 0;
}

Compilation message

street_lamps.cpp: In function 'int64_t Query(int64_t, int64_t, int64_t, int64_t, int64_t)':
street_lamps.cpp:32:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int nM = nL + nR >> 1;
              ~~~^~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4480 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 111 ms 8184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4480 KB Output is correct
2 Correct 4 ms 4480 KB Output is correct
3 Correct 4 ms 4480 KB Output is correct
4 Correct 4 ms 4480 KB Output is correct
5 Correct 113 ms 11488 KB Output is correct
6 Correct 179 ms 12172 KB Output is correct
7 Correct 203 ms 12940 KB Output is correct
8 Correct 263 ms 15116 KB Output is correct
9 Correct 136 ms 8184 KB Output is correct
10 Correct 162 ms 8440 KB Output is correct
11 Correct 128 ms 8696 KB Output is correct
12 Correct 272 ms 13708 KB Output is correct
13 Correct 281 ms 15244 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4480 KB Output isn't correct
2 Halted 0 ms 0 KB -