Submission #130715

#	Time	Username	Problem	Language	Result	Execution time	Memory
130715		ae04071	Street Lamps (APIO19_street_lamps)	C++11	100 / 100	776 ms	25720 KiB

street_lamps

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using pii = pair<int,int>;

int n,q,cnt[300001],l[300001][2],r[300001][2],v[300001][2];
int ans[300001],qt[300001];
char str[300010];

set<pair<pii,int>> tr;

struct seg_tr{
    int tr[300001];
    void upd(int cur,int val) {
        while(cur<=n) {
            tr[cur] += val;
            cur += cur & -cur;
        }
    }
    int get(int  cur) {
        int ret=0;
        while(cur) {
            ret += tr[cur];
            cur -= cur & -cur;
        }
        return ret;
    }
}st;

void solve(int s,int f) {
    if(s==f) return;

    int md=(s+f)>>1;
    solve(s,md);
    solve(md+1,f);

    vector<pair<pii,int>> ia,qa;
    for(int i=s;i<=md;i++) if(cnt[i]) {
        for(int j=0;j<cnt[i];j++) ia.push_back({pii(l[i][j],r[i][j]),v[i][j]});
    }
    for(int i=md+1;i<=f;i++) if(!cnt[i]) {
        qa.push_back({pii(l[i][0],r[i][0]),i});
    }
    sort(ia.begin(),ia.end(),[](const pair<pii,int> &a, const pair<pii,int> &b) {
        return a.fi.se > b.fi.se;
    });
    sort(qa.begin(),qa.end(),[](const pair<pii,int> &a, const pair<pii,int> &b) {
        return a.fi.se > b.fi.se;
    });

    int i,j;
    for(i=0,j=0;i<(int)qa.size();i++) {
        for(;j<(int)ia.size() && ia[j].fi.se >= qa[i].fi.se; j++) st.upd(ia[j].fi.fi,ia[j].se);
        ans[qa[i].se] += st.get(qa[i].fi.fi);
    }
    for(j=j-1;j>=0;j--) st.upd(ia[j].fi.fi,-ia[j].se);
}

int main() {
    scanf("%d%d",&n,&q);
    scanf("%s",str+1);
    for(int i=1;i<=n;i++) str[i] -= '0';
    
    for(int i=1,j=1;i<=n;i=j) {
        if(!str[i]) {
            j=i+1; continue;
        }
        for(j=i;j<=n && str[j];j++);
        tr.insert({pii(i,j-1), 0});
    }

    char tmp[10];
    int a,b;
    for(int i=1;i<=q;i++) {
        scanf("%s",tmp);
        if(tmp[0] == 'q') {
            scanf("%d%d",&a,&b);
            b--;
            l[i][0]=a; r[i][0]=b;

            auto it = tr.upper_bound({pii(a,n+1),n+1});
            if(it!=tr.begin()) {
                it--;
                if(it->fi.se >= b) ans[i] += i-it->se;
            }
            qt[i]=1;
        } else {
            scanf("%d",&a);
            
            str[a]^=1;
            if(str[a]) {
                int li=a,ri=a;
                auto it = tr.lower_bound({pii(a,n), 0});
                if(it!=tr.begin()) {
                    it--;
                    if(it->fi.se == li-1) {
                        tie(l[i][cnt[i]], r[i][cnt[i]]) = it->fi;
                        v[i][cnt[i]++] = i - it->se;
                        li = it->fi.fi;
                        it = tr.erase(it);
                    } else it++;
                }
                if(it!=tr.end()) {
                    if(it->fi.fi == ri+1) {
                        tie(l[i][cnt[i]], r[i][cnt[i]]) = it->fi;
                        v[i][cnt[i]++] = i - it->se;
                        ri = it->fi.se;
                        tr.erase(it);
                    }
                }
                tr.insert({pii(li,ri), i});
            } else {
                auto it = tr.upper_bound({pii(a,n+1),n+1});
                it--;
                tie(l[i][cnt[i]], r[i][cnt[i]]) = it->fi;
                v[i][cnt[i]++] = i-it->se;

                if(it->fi.fi != a) {
                    tr.insert({pii(it->fi.fi, a-1), i});
                }
                if(it->fi.se != a) {
                    tr.insert({pii(a+1, it->fi.se), i});
                }
                tr.erase(it);
            }
        }
    }

    solve(1,q);
    for(int i=1;i<=q;i++) if(qt[i]) printf("%d\n",ans[i]);
    
    return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&q);
     ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",str+1);
     ~~~~~^~~~~~~~~~~~
street_lamps.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",tmp);
         ~~~~~^~~~~~~~~~
street_lamps.cpp:78:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d",&a,&b);
             ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:89:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a);
             ~~~~~^~~~~~~~~

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