oj.uz

Submission #952983

# Submission time Handle Problem Language Result Execution time Memory
952983 2024-03-25T08:38:02 Z Vladth11 Street Lamps (APIO19_street_lamps) C++14
20 / 100
 195 ms 25936 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;

const ll NMAX = 300001;
const int INF = 1e9;
const ll nrbits = 20;
const ll MOD = 998244353;

int a[NMAX];
string s[NMAX];
int qa[NMAX];
int qb[NMAX];

int aint[NMAX * 4];

void update(int node, int st, int dr, int a, int b){
    if(st == dr){
        aint[node] = b;
        return;
    }
    int mid = (st + dr) / 2;
    if(a <= mid)
        update(node * 2, st, mid, a, b);
    else
        update(node * 2 + 1, mid + 1, dr, a, b);
    aint[node] = max(aint[node * 2], aint[node * 2 + 1]);
}

int query(int node, int st, int dr, int a, int b){
    if(a <= st && dr <= b)
        return aint[node];
    int mid = (st + dr) / 2;
    int sol = 0;
    if(a <= mid)
        sol = max(sol, query(node * 2, st, mid, a, b));
    if(b > mid)
        sol = max(sol, query(node * 2 + 1, mid + 1, dr, a, b));
    return sol;
}

signed main() {
#ifdef HOME
    ifstream cin(".in");
    ofstream cout(".out");
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, i, q;
    cin >> n >> q;
    for(int i = 0; i < NMAX * 4; i++)
        aint[i] = 2e9;
    for(i = 1; i <= n; i++){
        char c;
        cin >> c;
        a[i] = c - '0';
        if(a[i] == 1){
            update(1, 1, n, i, 0);
        }
    }
    for(i = 1; i <= q; i++){
        cin >> s[i];
        cin >> qa[i];
        if(s[i][0] == 'q'){
            cin >> qb[i];
            qb[i]--;
            cout << max(0, i - query(1, 1, n, qa[i], qb[i])) << "\n";
        }else{
            update(1, 1, n, qa[i], i);
        }
    }
    return 0;
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 19380 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 16984 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 4 ms 17244 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 90 ms 21552 KB Output is correct
6 Correct 116 ms 22960 KB Output is correct
7 Correct 144 ms 23636 KB Output is correct
8 Correct 195 ms 25880 KB Output is correct
9 Correct 65 ms 20560 KB Output is correct
10 Correct 68 ms 20816 KB Output is correct
11 Correct 70 ms 21076 KB Output is correct
12 Correct 159 ms 24568 KB Output is correct
13 Correct 183 ms 25936 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16984 KB Output is correct
2 Incorrect 3 ms 16988 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 16984 KB Output isn't correct
2 Halted 0 ms 0 KB -