Submission #1160566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160566		eggx50000	Street Lamps (APIO19_street_lamps)	C++20	100 / 100	680 ms	23628 KiB

street_lamps

#include <iostream>
#include <vector>
#include <deque>
#include <string.h>
#include <map>
#include <algorithm>
using namespace std;
using ll = long long;
const ll mod = 100000007;

int n, q, x, y, ret[300099];
bool is[300099];
char ca[300099], cc[10];

struct Segtree{

    int tr[1200099];

    void upd(int node, int s, int e, int qi, int qv){
        if(qi < s || e < qi) return;
        if(s == e){
            tr[node] = qv;
            return;
        }
        int m = (s + e) / 2;
        upd(node * 2, s, m, qi, qv);
        upd(node * 2 + 1, m + 1, e, qi, qv);
        tr[node] = tr[node * 2] + tr[node * 2 + 1];
    }

    int qry(int node, int s, int e, int qs, int qe){
        if(qe < s || e < qs) return 0;
        if(qs <= s && e <= qe) return tr[node];
        int m = (s + e) / 2;
        return qry(node * 2, s, m, qs, qe) + qry(node * 2 + 1, m + 1, e, qs, qe);
    }

    int kth(int node, int s, int e, int k){//k이상의 최소 인덱스
        if(k > tr[1]) return n + 1;
        if(s == e) return s;
        int m = (s + e) / 2;
        if(tr[node * 2] >= k) return kth(node * 2, s, m, k);
        else return kth(node * 2 + 1, m + 1, e, k - tr[node * 2]);
    }

} segt;

struct MAS{

    int tr[1200099];

    void upd(int node, int s, int e, int qi, int qv){
        if(qi < s || e < qi) return;
        if(s == e){
            tr[node] = qv;
            return;
        }
        int m = (s + e) / 2;
        upd(node * 2, s, m, qi, qv);
        upd(node * 2 + 1, m + 1, e, qi, qv);
        tr[node] = max(tr[node * 2], tr[node * 2 + 1]);
    }

    int qry(int node, int s, int e, int qs, int qe){
        if(qe < s || e < qs) return 0;
        if(qs <= s && e <= qe) return tr[node];
        int m = (s + e) / 2;
        return max(qry(node * 2, s, m, qs, qe), qry(node * 2 + 1, m + 1, e, qs, qe));
    }


} mse;

struct Few{
    int tr[300099];

    void upd(int i, int v){
        while(i <= n){
            tr[i] += v;
            i += i & -i;
        }
    }
    int que(int a){
        int su = 0;
        while(a){
            su += tr[a];
            a -= a & -a;
        }
        return su;
    }
} fe;

int cn;
struct Sw{
    int t, x, p, i;

    bool operator <(const Sw &a) const{
        if(x != a.x) return x < a.x;
        else return t > a.t;
    }

} swr[600099];

void dnc(int s, int e){
    if(s >= e) return;
    int m = (s + e) / 2;
    dnc(s, m);
    dnc(m + 1, e);
    vector <Sw> ve;
    for(int i = s; i <= m; i ++){
        if(swr[i].t == 2) ve.push_back(swr[i]);
    }
    for(int i = m + 1; i <= e; i ++){
        if(swr[i].t == 1) ve.push_back(swr[i]);
    }
    sort(ve.begin(), ve.end());
    for(Sw &e : ve){
        if(e.t == 2) fe.upd(e.p, e.i);
        else ret[e.i] += fe.que(n) - fe.que(e.p - 1);
    }
    for(Sw &e : ve){
        if(e.t == 2) fe.upd(e.p, -e.i);
    }
}

struct Se{
    int x, y;
};

Se re(int x){
    if(segt.qry(1, 1, n, x, x) == 1) return {x + 1, x};
    int v = segt.qry(1, 1, n, 1, x);
    int s = segt.kth(1, 1, n, v), e = segt.kth(1, 1, n, v + 1) - 1;
    if(v) s ++;
    return {s, e};
}

int main()
{
    scanf("%d %d", &n, &q);
    scanf("%s", ca + 1);
    for(int i = 1; i <= n; i ++) ca[i] -= '0';
    for(int i = 1; i <= n; i ++){
        if(ca[i] == 0) segt.upd(1, 1, n, i, 1);
    }
    for(int i = 1; i <= q; i ++){
        scanf(" %s %d", cc + 1, &x);
        if(cc[1] == 'q'){
            scanf("%d", &y);
            y --;
            swr[++cn] = {1, x, y, i};
            if(segt.qry(1, 1, n, x, y) == 0){
                Se kk = re(x);
                ret[i] += i - mse.qry(1, 1, n, kk.x, kk.y);
            }
            is[i] = true;
        }
        else{
            if(ca[x] == 0){
                Se s1 = re(x - 1), s2 = re(x + 1);
                if(s1.x <= s1.y) swr[++cn] = {2, s1.x, s1.y, i - mse.qry(1, 1, n, s1.x, s1.y)};
                if(s2.x <= s2.y) swr[++cn] = {2, s2.x, s2.y, i - mse.qry(1, 1, n, s2.x, s2.y)};
                segt.upd(1, 1, n, x, 0);
                ca[x] = 1;
            }
            else{
                Se s = re(x);
                if(s.x <= s.y) swr[++cn] = {2, s.x, s.y, i - mse.qry(1, 1, n, s.x, s.y)};
                segt.upd(1, 1, n, x, 1);
                ca[x] = 0;
                if(segt.qry(1, 1, n, x - 1, x - 1) == 0) mse.upd(1, 1, n, x - 1, i);
                if(segt.qry(1, 1, n, x + 1, x + 1) == 0) mse.upd(1, 1, n, x + 1, i);
            }
            mse.upd(1, 1, n, x, i);
        }
    }
    dnc(1, cn);
    for(int i = 1; i <= q; i ++){
        if(is[i]) printf("%d\n", ret[i]);
    }
    return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:140:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:141:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |     scanf("%s", ca + 1);
      |     ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:147:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |         scanf(" %s %d", cc + 1, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:149:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |             scanf("%d", &y);
      |             ~~~~~^~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20