제출 #257436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
257436		balbit	가로등 (APIO19_street_lamps)	C++14	100 / 100	1902 ms	133916 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define int ll

#define pii pair<int, int>
#define f first
#define s second

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<" "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x ){ cerr<<x<<endl; }
template<typename T, typename ...S> void _do(T && x , S&&...y){ cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define endl '\n'
#define bug(...)
#endif // BALBIT

const int maxn = 3e5+5;

//vector<pii> g[maxn];
int n,q;
bool hi[maxn];
int ps[maxn];
int ans[maxn], lt[maxn];

struct con{
    // connected group of 1s
    int l,r,t; // l, r, time when it was created
    bool operator < (const con &oth) const{
        return l!=oth.l?l<oth.l:(tie(r,t) < tie(oth.r, oth.t));
    }
};

struct BIT{
    int mxn = 0;
    vector<int> s;
    ll QU(int e) {
        ll re = 0; for (++e; e>0; e-=e&-e) re += s[e]; return re;
    }
    void MO(int e, ll v) {
        for (++e; e<mxn; e+=e&-e) s[e] += v;
    }
    BIT(int xx) {
        mxn = xx+1; s.resize(mxn+1);
    }
    BIT(){
    }
};

vector<int> hvq[maxn];
BIT bb[maxn];
ll QU(int e, int y){
    ll re = 0;
    for (++e; e>0; e-=e&-e) {
        int xx = upper_bound(ALL(hvq[e]),y) - hvq[e].begin() -1;
        re += bb[e].QU(xx);
    }
    return re;
}

void MO(int e, int y, ll v) {
    for (++e; e<maxn; e+=e&-e) {
        int xx = upper_bound(ALL(hvq[e]),y)-hvq[e].begin()-1;
        bb[e].MO(xx,v);
    }
}

int NOWI = 0;
vector<array<int, 3> > mos[maxn];

void PMO(int e, int y, ll v) {
    mos[NOWI].pb({{e,y,v}});
    for (++e; e<maxn; e+=e&-e) {
        hvq[e].pb(y);
    }
}

set<con> st;
void dump(){
    #ifdef BALBIT
    for (auto & c : st) {
        cout<<"("<<c.l<<","<<c.r<<")- "<<c.t<<endl;
    }
    #endif
}


signed main(){
    IOS();
    cin>>n>>q;
    int tmpl = 0;
    for (int i = 0; i<=n; ++i) {
        char c='0'; if (i!=n)cin>>c;
        hi[i] = c=='1';
        if (!hi[i]) {
            if(tmpl <= i-1) {
                st.insert({tmpl, i-1, -1});
            }
            tmpl = i+1;
        }
    }
    dump();
    // done building segments
    vector<pii> ques; // if a is -1, b is x
    for (int i = 0; i<q; ++i) {
        NOWI = i;
        string tp; cin>>tp;
        if (tp[0] == 'q') {
            int a,b; cin>>a>>b; --a; --b; --b;
            ques.pb({a,b});
            auto it = st.upper_bound({a,100000000,-1});
            if (it != st.begin()) {
                --it;
                bug("HI?");
                if (it->r >= b) {
                    bug(i,"OIJEWFOIWJE");
                    ans[i] += i - it->t;
                }
            }

        }else{
            int x; cin>>x; --x;
            ques.pb({-1,x});
            if (hi[x]) {
                // turn off (break segment)
                bug("Hiii");
                auto it = (st.upper_bound({x,100000000,-1}));
//                if (it == st.begin()) while (1);
                --it;
                con tmp = *it;
                // use it to update
                PMO((it->l), n - it->r, i - it->t);
                if (tmp. l <= x-1) st.insert({tmp.l, x-1, i});
                if (x+1 <= tmp.r) st.insert({x+1, tmp.r, i});
                st.erase(tmp);
            }else{
                // merge??????????????
                con ns = {x,x,i};
                auto it = (st.upper_bound({x,-1,-1}));
                if (it != st.begin()) {
                    --it;
                    if (it -> r == x-1) {
                        PMO((it->l),  n - it->r, i - it->t);
                        // merge!
                        ns.l = it->l;
                        st.erase(it);
                    }
                }
                it = (st.upper_bound({x,-1,-1}));
                if (it != st.end()) {
                    if (it->l == x+1) {
                        PMO((it->l), n- it->r, i - it->t);
                        ns.r = it->r;
                        st.erase(it);
                    }
                }
                st.insert(ns);
            }
            hi[x] ^= 1;
        }
        dump();
    }

    for (int i =0 ; i<maxn; ++i) {
        bb[i] = BIT(SZ(hvq[i]));
        sort(ALL(hvq[i]));
    }

    for (int i = 0; i<q; ++i) {
        if (ques[i].f == -1) {
            // is a toggle
            int x=ques[i].s;
            for (auto a : mos[i]) {
                MO(a[0], a[1], a[2]);
                bug(a[0], a[1], a[2]);
            }
        }else{
            int l = ques[i].f, r = ques[i].s;
            ll lol = QU(l, n - r);
            bug(ans[i], lol);
            cout<<ans[i]+lol<<endl;
        }
    }

}

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

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:180:17: warning: unused variable 'x' [-Wunused-variable]
             int x=ques[i].s;
                 ^

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