oj.uz

Submission #433637

# Submission time Handle Problem Language Result Execution time Memory
433637 2021-06-20T09:02:04 Z someone Street Lamps (APIO19_street_lamps) C++14
20 / 100
 102 ms 18584 KB 
#include <bits/stdc++.h>
using namespace std;

struct Req {
    bool isQ;
    int deb, fin, pos;
};

struct Node {
    int deb, fin, maxi;
};

const int M = 1 << 17, N = 2*M, L = 142, INF = 1e9 + 42;

bool b[L][L];
Node node[N];
vector<Req> req;
int n, q, val[N], last[N], t[N];

void setMax(int i, int newMax) {
    if(i == 0)
        return;
    if(i >= M) {
        node[i].maxi = newMax;
        //cout << node[i].deb << ' ' << node[i].fin << ' ' << newMax << '\n';
    } else {
        node[i].maxi = max(node[i*2].maxi, node[i*2+1].maxi);
    }
    setMax(i/2, newMax);
}

int getMax(int i, int deb, int fin) {
    if(fin <= node[i].deb || node[i].fin <= deb)
        return -INF;
    if(deb <= node[i].deb && node[i].fin <= fin) {
        //cout << node[i].deb << ' ' << node[i].fin << ' ' << node[i].maxi << '\n';
        return node[i].maxi;
    }
    int v = max(getMax(i*2, deb, fin), getMax(i*2+1, deb, fin));
    //cout << node[i].deb << ' ' << node[i].fin << ' ' << v << '\n';
    return v;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q;
    for(int i = 0; i < n; i++) {
        char c;
        cin >> c;
        if(c == '1')
            val[i] = 1;
    }
    for(int i = 0; i < q; i++) {
        string str;
        cin >> str;
        if(str[0] == 'q') {
            int deb, fin;
            cin >> deb >> fin;
            req.push_back({true, deb-1, fin-1, -1});
        } else {
            int pos;
            cin >> pos;
            req.push_back({false, -1, -1, pos-1});
        }
    }
    if(n <= 100 && q <= 100) {
        for(int i = 0; i < n; i++)
            b[0][i] = (val[i] == 1);
        for(int i = 0; i < q; i++) {
            for(int j = 0; j < n; j++)
                b[i+1][j] = b[i][j];
            if(req[i].isQ) {
                int nb = 0;
                for(int j = 0; j <= i; j++) {
                    bool possible = true;
                    for(int k = req[i].deb; k < req[i].fin; k++)
                        if(!b[j][k])
                            possible = false;
                    if(possible)
                        nb++;
                }
                cout << nb << '\n';
            } else {
                b[i+1][req[i].pos] = !b[i+1][req[i].pos];
            }
        }
        return 0;
    }
    bool one = true;
    for(int i = 0; i < q; i++)
        if(req[i].isQ)
            if(req[i].deb + 1 != req[i].fin)
                one = false;

    if(one) {
        for(int i = 0; i < n; i++)
            last[i] = -1;
        for(int i = 0; i < q; i++) {
            if(req[i].isQ) {
                if(val[req[i].deb] == 1) {
                    cout << t[req[i].deb] + i - last[req[i].deb] << '\n';
                } else {
                    cout << t[req[i].deb] << '\n';
                }
            } else {
                if(val[req[i].pos] == 1) {
                    t[req[i].pos] += i - last[req[i].pos];
                } else {
                    last[req[i].pos] = i;
                }
                val[req[i].pos] = 1 - val[req[i].pos];
            }
        }
        return 0;
    } else {
        for(int i = M; i < N; i++) {
            node[i].deb = i - M;
            node[i].fin = i - M + 1;
            if(i >= n + M) {
                node[i].maxi = -INF;
            } else {
                if(val[i - M] == 0)
                    node[i].maxi = INF;
                else
                    node[i].maxi = -1;
            }
        }
        for(int i = M-1; i > 0; i--) {
            node[i].deb = node[i*2].deb;
            node[i].fin = node[i*2+1].fin;
            node[i].maxi = max(node[i*2].maxi, node[i*2+1].maxi);
        }

        for(int i = 0; i < q; i++) {
            if(req[i].isQ) {
                int l = getMax(1, req[i].deb, req[i].fin);
                cout << max(0, i - l) << '\n';
                //cout << req[i].deb << ' ' << req[i].fin << ' ' << max(0, i - l) << ' ' << l << '\n';
            } else {
                setMax(req[i].pos + M, i);
            }
        }
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 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 1 ms 332 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 8576 KB Output is correct
2 Correct 96 ms 8552 KB Output is correct
3 Correct 102 ms 8604 KB Output is correct
4 Incorrect 26 ms 9656 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Correct 3 ms 3404 KB Output is correct
3 Correct 3 ms 3404 KB Output is correct
4 Correct 3 ms 3404 KB Output is correct
5 Runtime error 85 ms 18584 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Incorrect 3 ms 3404 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 332 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 1 ms 332 KB Output is correct
8 Correct 90 ms 8576 KB Output is correct
9 Correct 96 ms 8552 KB Output is correct
10 Correct 102 ms 8604 KB Output is correct
11 Incorrect 26 ms 9656 KB Output isn't correct
12 Halted 0 ms 0 KB -