제출 #433639

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
433639		someone	Street Lamps (APIO19_street_lamps)	C++14	60 / 100	371 ms	20604 KiB

street_lamps

#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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20