oj.uz

Submission #400137

# Submission time Handle Problem Language Result Execution time Memory
400137 2021-05-07T12:54:28 Z dxz05 Street Lamps (APIO19_street_lamps) C++14
60 / 100
 716 ms 15584 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << "[" << H << "]";
    debug_out(T...);
}

#ifdef dddxxz
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SZ(s) ((int)s.size())
#define all(x) (x).begin(), (x).end()
#define revall(x) (x).rbegin(), (x).rend()

clock_t startTime;

double getCurrentTime() {
    return (double) (clock() - startTime) / CLOCKS_PER_SEC;
}

typedef long long ll;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const double eps = 0.00001;
const int MOD = 1e9 + 7;
const int INF = 1000000101;
const long long LLINF = 1223372000000000555;
const int N = 5e5 + 3e2;
const int M = 2222;

string street;
int n, q;
char qch[N];
int ql[N], qr[N];

void Subtask_1(){
    vector<vector<int>> cnt(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++){
        for (int j = i; j < n; j++){
            if (street[j] == '0') break;
            cnt[i][j] = 1;
        }
    }

    for (int i = 1; i <= q; i++){
        if (qch[i] == 't'){ // toggle
            street[ql[i]] ^= '0' ^ '1';
        } else { // query
            cout << cnt[ql[i]][qr[i]] << endl;
        }

        for (int l = 0; l < n; l++){
            for (int r = l; r < n; r++){
                if (street[r] == '0') break;
                cnt[l][r]++;
            }
        }

    }

    exit(0);

}

void Subtask_2(){
    vector<int> cnt(n + 1), last(n + 1);
    for (int i = 0; i < n; i++){
        if (street[i] == '1') cnt[i] = 1, last[i] = 1; else
            last[i] = -1;
    }

    for (int i = 1; i <= q; i++){
        if (qch[i] == 't'){
            int x = ql[i];
            if (street[x] == '1'){
                cnt[x] += i - last[x];
                last[x] = -1;
            } else {
                last[x] = i;
            }

            street[x] ^= '0' ^ '1';

        } else {
            int l = ql[i];
            cout << cnt[l] + (last[l] != -1 ? i - last[l] : 0) << endl;
        }
    }

    exit(0);
}

struct SegTree{
    int size = 1;
    vector<int> tree;
    void build(int v, int tl, int tr){
        if (tl == tr){
            tree[v] = (tl < n && street[tl] == '1' ? 0 : INF);
            return;
        }
        int tm = (tl + tr) >> 1;
        build(v + v, tl, tm);
        build(v + v + 1, tm + 1, tr);
        tree[v] = max(tree[v + v], tree[v + v + 1]);
    }

    void init(){
        while (size <= n) size *= 2;
        tree.resize(size * 2);
        build(1, 0, size - 1);
    }

    void update(int v, int tl, int tr, int pos, int val){
        if (tl == tr){
            tree[v] = val;
            return;
        }
        int tm = (tl + tr) >> 1;
        if (pos <= tm) update(v + v, tl, tm, pos, val); else
            update(v + v + 1, tm + 1, tr, pos, val);
        tree[v] = max(tree[v + v], tree[v + v + 1]);
    }

    void update(int pos, int val){
        update(1, 0, size - 1, pos, val);
    }

    int get(int v, int tl, int tr, int l, int r){
        if (l <= tl && tr <= r) return tree[v];
        if (tl > r || tr < l) return 0;
        int tm = (tl + tr) >> 1;
        return max(get(v + v, tl, tm, l, r), get(v + v + 1, tm + 1, tr, l, r));
    }

    int get(int l, int r){
        return get(1, 0, size - 1, l, r);
    }

};

void Subtask_4(){
    SegTree st;
    st.init();
    for (int i = 1; i <= q; i++){
        if (qch[i] == 't'){
            st.update(ql[i], i);
        } else {
            cout << max(0, i - st.get(ql[i], qr[i])) << endl;
        }
     //   for (int j = 0; j < n; j++) cout << st.get(j, j) << ' '; cout << endl;
    }

    exit(0);
}

void solve(int TC) {
    cin >> n >> q >> street;

    bool ok2 = true;
    for (int i = 1; i <= q; i++){
        string t;
        cin >> t >> ql[i];
        qch[i] = t[0];
        ql[i]--;
        if (qch[i] == 'q') {
            cin >> qr[i];
            qr[i] -= 2;
            ok2 &= ql[i] == qr[i];
        }
    }

    if (n <= 100 && q <= 100){
        Subtask_1();
    }

    if (ok2){
        Subtask_2();
    }

    Subtask_4();

}


int main() {
    startTime = clock();
    cin.tie(nullptr); cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    bool llololcal = false;
#ifdef dddxxz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    llololcal = true;
#endif

    int TC = 1;
    //cin >> TC;

    for (int test = 1; test <= TC; test++) {
        //debug(test);
        //cout << "Case #" << test << ": ";
        solve(test);
    }

    if (llololcal) cerr << endl << "Time: " << int(getCurrentTime() * 1000) << " ms" << endl;

    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 3896 KB Output is correct
2 Correct 313 ms 3908 KB Output is correct
3 Correct 309 ms 3900 KB Output is correct
4 Correct 326 ms 6360 KB Output is correct
5 Correct 369 ms 6872 KB Output is correct
6 Correct 265 ms 5656 KB Output is correct
7 Correct 567 ms 6516 KB Output is correct
8 Correct 553 ms 7812 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 150 ms 7404 KB Output is correct
6 Correct 338 ms 12568 KB Output is correct
7 Correct 494 ms 13092 KB Output is correct
8 Correct 704 ms 15584 KB Output is correct
9 Correct 460 ms 6080 KB Output is correct
10 Correct 504 ms 6588 KB Output is correct
11 Correct 500 ms 6852 KB Output is correct
12 Correct 716 ms 14020 KB Output is correct
13 Correct 706 ms 15444 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 301 ms 3896 KB Output is correct
9 Correct 313 ms 3908 KB Output is correct
10 Correct 309 ms 3900 KB Output is correct
11 Correct 326 ms 6360 KB Output is correct
12 Correct 369 ms 6872 KB Output is correct
13 Correct 265 ms 5656 KB Output is correct
14 Correct 567 ms 6516 KB Output is correct
15 Correct 553 ms 7812 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 3 ms 332 KB Output is correct
20 Correct 150 ms 7404 KB Output is correct
21 Correct 338 ms 12568 KB Output is correct
22 Correct 494 ms 13092 KB Output is correct
23 Correct 704 ms 15584 KB Output is correct
24 Correct 460 ms 6080 KB Output is correct
25 Correct 504 ms 6588 KB Output is correct
26 Correct 500 ms 6852 KB Output is correct
27 Correct 716 ms 14020 KB Output is correct
28 Correct 706 ms 15444 KB Output is correct
29 Correct 3 ms 332 KB Output is correct
30 Incorrect 2 ms 332 KB Output isn't correct
31 Halted 0 ms 0 KB -