제출 #681258

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
681258		qwerasdfzxcl	가로등 (APIO19_street_lamps)	C++17	100 / 100	2488 ms	45384 KiB

street_lamps

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct Seg1{
    int tree[1201200], sz;
    void init(int i, int l, int r, char s[]){
        if (i==1) sz = r;
        if (l==r){tree[i] = s[l]-'0'; return;}

        int m = (l+r)>>1;
        init(i<<1, l, m, s); init(i<<1|1, m+1, r, s);
        tree[i] = tree[i<<1] + tree[i<<1|1];
    }
    void update(int i, int l, int r, int p){
        if (r<p || p<l) return;
        if (l==r) {tree[i] ^= 1; return;}
        int m = (l+r)>>1;
        update(i<<1, l, m, p); update(i<<1|1, m+1, r, p);
        tree[i] = tree[i<<1] + tree[i<<1|1];
    }
    int query(int i, int l, int r, int p){
        if (r<p || p<l) return 0;
        if (l==r) return tree[i];
        int m = (l+r)>>1;
        return query(i<<1, l, m, p) + query(i<<1|1, m+1, r, p);
    }

    pair<int, int> _search(int i, int l, int r, int p, int x){
        if (tree[i]==(r-l+1) * x) return {l, r};
        if (l==r) return {-1, -1};

        int m = (l+r)>>1;
        if (r<p || (m+1 <= p && p <= r)){
            auto ret = _search(i<<1|1, m+1, r, p, x);
            if (ret.first != m+1) return ret;
            auto ret2 = _search(i<<1, l, m, p, x);

            if (ret2.second==-1) return ret;
            return {ret2.first, ret.second};
        }
        else{
            auto ret = _search(i<<1, l, m, p, x);
            if (ret.second != m) return ret;
            auto ret2 = _search(i<<1|1, m+1, r, p, x);

            if (ret2.first==-1) return ret;
            return {ret.first, ret2.second};
        }
    }

    pair<pair<int, int>, int> calc(int p, bool no = 0){
        int x = query(1, 1, sz, p);
        if (x==0) update(1, 1, sz, p);

        auto ret = _search(1, 1, sz, p, 1);
        if ((x==0) == no) update(1, 1, sz, p);
        return {ret, x};
    }
    void toggle(int p){update(1, 1, sz, p);}
}tree1;

struct Seg2{
    ll tree[600600], sz;
    vector<int> st;

    void init(int n){
        sz = n;
        for (auto &x:st) tree[x] = 0;
        st.clear();
    }

    void update(int l, int r, int x){
        ++r;
        //printf(" update: %d %d %d\n", l, r, x);
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1){
                st.push_back(l);
                tree[l] += x;
                l++;
            }
            if (r&1){
                --r;
                st.push_back(r);
                tree[r] += x;
            }
        }
    }
    ll query(int p){
        //printf(" query: %d\n", p);
        ll ret = 0;
        for (p+=sz;p;p>>=1) ret += tree[p];
        return ret;
    }
}tree2;

char buf[1010];
struct Query{
    int a, b, i, typ;

    Query(){}

    void input(int _i){
        i = _i;
        scanf("%s", buf);
        if (buf[0]=='q'){
            scanf("%d %d", &a, &b);
            typ = 1;
            --b;
        }
        else{
            scanf("%d", &a);
            b = -1;
            typ = 0;
        }
    }
}query[300300];

struct Query2{
    int x, y1, y2, z, typ;
    Query2(){}
    Query2(int _x, int _y1, int _y2, int _z, int _typ): x(_x), y1(_y1), y2(_y2), z(_z), typ(_typ) {}
    bool operator < (const Query2 &Q) const{
        if (x==Q.x) return typ < Q.typ;
        return x < Q.x;
    }
};
char s[300300];
int n, q;
ll ans[300300];

void process(const vector<Query> &T, const vector<Query> &Q){
    vector<Query2> V;
    for (auto &[a, b, i, typ]:T){
        assert(typ==0);
        auto [p, x] = tree1.calc(a);
        auto [l, r] = p;
        //printf("%d %d %d\n", l, r, x);

        assert(l!=-1);
        int add = -(x?(q-i):(i-q));
        V.emplace_back(l, a, r, add, 0);
        V.emplace_back(a+1, a, r, -add, 0);
    }

    for (auto &[a, b, i, typ]:Q){
        assert(typ==1);
        V.emplace_back(a, b, -1, i, 1);
    }

    sort(V.begin(), V.end());
    tree2.init(n+3);
    for (auto &[x, y1, y2, z, typ]:V){
        if (typ==0) tree2.update(y1, y2, z);
        else ans[z] += tree2.query(y1);

        //if (typ==1) printf("%d -> add %lld\n", z, tree2.query(y1));
    }
}

void dnc(int l, int r){
    if (l==r){
        if (query[l].typ==0) return;
        auto [p, x] = tree1.calc(query[l].a, 1);
        if (p.second >= query[l].b && x==1){
            ans[query[l].i] -= q-query[l].i;
        }

        return;
    }

    int m = (l+r)>>1;
    dnc(l, m);

    vector<Query> T, Q;
    for (int i=l;i<=m;i++) if (query[i].typ==0) T.push_back(query[i]);
    for (int i=m+1;i<=r;i++) if (query[i].typ==1) Q.push_back(query[i]);
    process(T, Q);

    dnc(m+1, r);

    for (auto &[a, b, i, typ]:T) tree1.toggle(a);
}

int main(){
    scanf("%d %d", &n, &q);
    scanf("%s", s+1);

    tree1.init(1, 1, n, s);

    for (int i=1;i<=q;i++){
        query[i].input(i);
        if (query[i].typ==1){
            auto [p, x] = tree1.calc(query[i].a, 1);

            if (p.second >= query[i].b && x==1) ans[i] += q;
        }
    }

    dnc(1, q);
    for (int i=1;i<=q;i++) if (query[i].typ==1) printf("%lld\n", ans[i]);
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:186:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:187:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  187 |     scanf("%s", s+1);
      |     ~~~~~^~~~~~~~~~~
street_lamps.cpp: In member function 'void Query::input(int)':
street_lamps.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         scanf("%s", buf);
      |         ~~~~~^~~~~~~~~~~
street_lamps.cpp:107:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |             scanf("%d %d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:112:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |             scanf("%d", &a);
      |             ~~~~~^~~~~~~~~~

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