oj.uz

Submission #433639

# Submission time Handle Problem Language Result Execution time Memory
433639 2021-06-20T09:03:42 Z someone Street Lamps (APIO19_street_lamps) C++14
60 / 100
 371 ms 20604 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 << 19, 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 0 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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 8656 KB Output is correct
2 Correct 96 ms 8684 KB Output is correct
3 Correct 97 ms 8668 KB Output is correct
4 Correct 117 ms 9852 KB Output is correct
5 Correct 120 ms 9808 KB Output is correct
6 Correct 107 ms 9960 KB Output is correct
7 Correct 127 ms 8596 KB Output is correct
8 Correct 138 ms 9740 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12620 KB Output is correct
2 Correct 8 ms 12620 KB Output is correct
3 Correct 8 ms 12620 KB Output is correct
4 Correct 10 ms 12620 KB Output is correct
5 Correct 125 ms 18552 KB Output is correct
6 Correct 203 ms 18816 KB Output is correct
7 Correct 276 ms 18992 KB Output is correct
8 Correct 371 ms 20604 KB Output is correct
9 Correct 146 ms 17324 KB Output is correct
10 Correct 167 ms 17992 KB Output is correct
11 Correct 162 ms 17828 KB Output is correct
12 Correct 355 ms 17988 KB Output is correct
13 Correct 369 ms 20564 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12684 KB Output is correct
2 Incorrect 9 ms 12620 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 0 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 93 ms 8656 KB Output is correct
9 Correct 96 ms 8684 KB Output is correct
10 Correct 97 ms 8668 KB Output is correct
11 Correct 117 ms 9852 KB Output is correct
12 Correct 120 ms 9808 KB Output is correct
13 Correct 107 ms 9960 KB Output is correct
14 Correct 127 ms 8596 KB Output is correct
15 Correct 138 ms 9740 KB Output is correct
16 Correct 9 ms 12620 KB Output is correct
17 Correct 8 ms 12620 KB Output is correct
18 Correct 8 ms 12620 KB Output is correct
19 Correct 10 ms 12620 KB Output is correct
20 Correct 125 ms 18552 KB Output is correct
21 Correct 203 ms 18816 KB Output is correct
22 Correct 276 ms 18992 KB Output is correct
23 Correct 371 ms 20604 KB Output is correct
24 Correct 146 ms 17324 KB Output is correct
25 Correct 167 ms 17992 KB Output is correct
26 Correct 162 ms 17828 KB Output is correct
27 Correct 355 ms 17988 KB Output is correct
28 Correct 369 ms 20564 KB Output is correct
29 Correct 9 ms 12684 KB Output is correct
30 Incorrect 9 ms 12620 KB Output isn't correct
31 Halted 0 ms 0 KB -