oj.uz

Submission #240124

# Submission time Handle Problem Language Result Execution time Memory
240124 2020-06-18T06:36:57 Z wiwiho Street Lamps (APIO19_street_lamps) C++14
20 / 100
 319 ms 48496 KB 
//#define NDEBUG

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define iceil(a, b) ((a + b - 1) / b)
#define tomax(a, b) (a = max(a, b))
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

//#define TEST

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

int main(){
    StarBurstStream

    int n, q;
    cin >> n >> q;

    string s;
    cin >> s;

    vector<int> o(n, q);
    for(int i = 0; i < n; i++){
        if(s[i] == '1') o[i] = -1;
    }

    vector<pair<int, pii>> qry;

    for(int i = 0; i < q; i++){
        string t;
        cin >> t;

        if(t == "toggle"){
            int x;
            cin >> x;
            x--;
            o[x] = i;
        }
        else{
            int a, b;
            cin >> a >> b;
            a--; b -= 2;
            qry.eb(mp(i, mp(a, b)));
        }
    }

    vector<vector<int>> st(n, vector<int>(20));
    for(int i = 0; i < n ;i++) st[i][0] = o[i];
    for(int i = 1; i < 20; i++){
        for(int j = 0; j + (1 << i) - 1 < n; j++){
            st[j][i] = max(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
        }
    }

    for(auto i : qry){
        int l = i.S.F, r = i.S.S;
        int lg = __lg(r - l + 1);
        int tmp = max(st[l][lg], st[r - (1 << lg) + 1][lg]);
        cout << max(0, i.F - tmp) << "\n";
    }

    return 0;
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 3568 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 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 154 ms 41452 KB Output is correct
6 Correct 212 ms 43060 KB Output is correct
7 Correct 272 ms 44952 KB Output is correct
8 Correct 313 ms 48476 KB Output is correct
9 Correct 92 ms 7012 KB Output is correct
10 Correct 101 ms 9700 KB Output is correct
11 Correct 89 ms 9828 KB Output is correct
12 Correct 276 ms 47096 KB Output is correct
13 Correct 319 ms 48496 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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