Submission #544554

#	Time	Username	Problem	Language	Result	Execution time	Memory
544554		Victor	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	62 ms	15228 KiB

street_lamps

// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

struct Fenwick {
    vi ft;
    Fenwick(int n) { ft.assign(n+1,0); }

    int rsq(int i) {
        int sum=0;
        for(;i;i-=i&-i) sum+=ft[i];
        return sum;
    }
    int rsq(int i,int j) { return rsq(j)-rsq(i-1); }

    void update(int i,int v) {
        for(;i<sz(ft);i+=i&-i) ft[i]+=v;
    }
};

int n, q;
string state;
map<ii,int> build_intervals;
vector<pair<ii,ii>> intervals;
int ans[300005];
string types[300005];
int queries[300005][2],first_query=INF,last_toggle=-1;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    cin >> n >> q >> state;
    state+='0';
    rep(i,0,n) {
        if(state[i]=='0')continue;
        rep(j,i,n+1) if(state[j]=='0') {
            build_intervals.insert({{i,j},-1});
            i=j;
            break;
        }
    }

    rep(i,0,q) {
        cin>>types[i];
        int vals=1+(types[i]=="query");
        rep(j,0,vals) cin>>queries[i][j];

        if(types[i]=="query") first_query=min(first_query,i);
        else last_toggle=i;
    }

    if(last_toggle>first_query) return 0;

    rep(i,0,first_query) {
        int pos=queries[i][0];
        int start=pos,stop=pos;
        
        vii rem,add;
        if(state[pos]=='0') {
            auto it=build_intervals.lower_bound(ii(pos,0));

            if(it!=build_intervals.end()&&it->first.first==pos+1) {
                stop=it->first.second;
                rem.emplace_back(it->first);
            }

            if(it!=build_intervals.begin()&&(--it)->first.second==pos) {
                start=it->first.first;
                rem.emplace_back(it->first);
            }
            add.emplace_back(start,stop);

        } else {
            auto it=build_intervals.upper_bound(ii(pos,INF));

            if(it!=build_intervals.begin()) {
                --it;
                int lo,hi;
                tie(lo,hi)=it->first;

                if(pos<hi) {
                    start=lo;
                    stop=hi;

                    if(pos!=hi-1) add.emplace_back(pos+1,hi);
                    if(pos!=lo) add.emplace_back(lo,pos);
                }
            }
        }

        trav(item,rem) {
            int lo,hi;
            tie(lo,hi)=item;
            int last_update=build_intervals[{lo,hi}];
            intervals.pb({{lo,0},{hi,i-last_update}});
            build_intervals.erase({lo,hi});
        }

        trav(item,add) {
            int lo,hi;
            tie(lo,hi)=item;
            build_intervals.insert({{lo,hi},i});
        }
    }

    trav(item,build_intervals) {
        int lo,hi;
        tie(lo,hi)=item.first;
        int last_update=build_intervals[{lo,hi}];
        intervals.pb({{lo,0},{hi,first_query-last_update}});
    }

    //debug(first_query);
    rep(i,first_query,q) {
        rep(j,0,2) queries[i][j]-=1+j;
        intervals.pb({{queries[i][0],1},{queries[i][1],i-first_query}});
    }
    sort(all(intervals));

    Fenwick fenwick(n+3);
    trav(interval,intervals) {
        int lo,type,hi,cnt;
        tie(lo,type)=interval.first;
        tie(hi,cnt)=interval.second;
        ++lo; ++hi;

        //cout<<"lo = "<<lo<<" hi = "<<hi<<" type = "<<type<<" cnt = "<<cnt<<endl;
        if(!type) {
            fenwick.update(hi-1,cnt);

        } else {
            ans[cnt]=fenwick.rsq(hi,n+3);
        }
    }

    rep(i,0,q-first_query) {
        auto it=build_intervals.upper_bound(ii(queries[i+first_query][0],INF));
        if(it!=build_intervals.begin()) {
            --it;
            if(it->first.second>queries[i+first_query][1]) ans[i]+=i;
        }
        cout<<ans[i]<<'\n';
    }
    return 0;
}

Compilation message (stderr)

street_lamps.cpp: In member function 'void Fenwick::update(int, int)':
street_lamps.cpp:45:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(;i<sz(ft);i+=i&-i) ft[i]+=v;
      |               ^

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