Submission #496438

#	Time	Username	Problem	Language	Result	Execution time	Memory
496438		dantoh000	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	770 ms	30020 KiB

street_lamps

#include <bits/stdc++.h>
/// based on https://sltechnicalacademy.com/apio-2019-problems-solutions/
using namespace std;
typedef pair<int,int> ii;
int n,q;
char str[300005];
struct seg{
    int s, e, t;
    bool operator<(const seg &i)const{
		return s < i.s;
	}
};

struct evt{
    int s, e, t, type;
    bool operator<(const evt &i)const{
		return ii(s,e) < ii(i.s,i.e);
	}
};
int ans[300005];
vector<evt> ev;
set<seg> s;
struct fenwick{
    int a[300005];
    void add(int x, int v){
        while (x < 300005){
            a[x] += v;
            x += x&-x;
        }
    }
    int qu(int x){
        int ret = 0;
        while (x){
            ret += a[x];
            x -= x&-x;
        }
        return ret;
    }



}fw;

void solve(int l, int r){
    if (l == r) return;
    //printf("solving (%d %d)\n",l,r);
    int m = (l+r)/2;
    solve(l,m);
    solve(m+1,r);
    vector<evt> up, qu;
    for (int i = l; i <= m; i++){
        //printf("%d %d %d %d %d\n",i,ev[i].s, ev[i].e, ev[i].t, ev[i].type);
        if (ev[i].type == 1){
            up.push_back(ev[i]);
        }
    }
    for (int i = m+1; i <= r; i++){
        //printf("%d %d %d %d %d\n",i,ev[i].s, ev[i].e, ev[i].t, ev[i].type);
        if (ev[i].type == 2){
            qu.push_back(ev[i]);
        }
    }
    for (auto x : up){
        //printf("update %d %d %d\n",x.s,x.e,x.t);
    }
    for (auto x : qu){
        //printf("query %d %d %d\n",x.s,x.e,x.t);
    }
    sort(up.begin(),up.end());
    sort(qu.begin(),qu.end());
    int i = 0;
    for (auto Q : qu){
        while (i < up.size() && up[i].s <= Q.s){
            fw.add(up[i].e, up[i].t);
            i++;
        }
        ans[Q.t] += fw.qu(Q.e);
    }
    for (int j = 0; j < i; j++){
        fw.add(up[j].e, -up[j].t);
    }
    //printf("end solve (%d %d)\n",l,r);

}
void addrange(int s, int e, int v){
    ev.push_back({s,s,v,1});
    ev.push_back({s,e+1,-v,1});
}




int main(){
    scanf("%d%d", &n,&q);
    scanf("%s",str+1);
    for (int i = 1; i <= n; i++){
        if (str[i] == '1'){
            int e = i;
            while (e <= n && str[e] == '1') e++;
            s.insert({i,e-1,0});
            i = e-1;
        }
    }
    for (int i = 0; i < q; i++){
        string Qs;
        cin >> Qs;
        if (Qs == "toggle"){
            int x; scanf("%d",&x);
            if (str[x] == '0'){
                int st = x, ed = x;
                auto it = s.lower_bound({x+1, -1, -1});
                if (it != s.end() && it->s == x+1){
                    addrange(it->s, it->e, i+1 - it->t);
                    ed = it->e;
                    it = s.erase(it);
                }
                if (it != s.begin() && prev(it)->e == x-1){
                    --it;
                    addrange(it->s, it->e, i+1 - it->t);
                    st = it->s;
                    it = s.erase(it);
                }
                s.insert({st,ed,i+1});
            }
            else{
                auto it = --s.lower_bound({x+1, -1, -1});
                addrange(it->s, it->e, i+1 - it->t);
                int S = it->s;
                int E = it->e;
                s.erase(it);
                if (S < x) s.insert({S,x-1,i+1});
                if (x < E) s.insert({x+1,E,i+1});
            }
            str[x] ^= 1;
            ans[i] = -1;
        }
        else{
            int a,b; scanf("%d%d",&a,&b);
            b--;
            ev.push_back({a,b,i,2});
            auto it = s.lower_bound({a+1,-1,-1});
            if (it != s.begin()){
                --it;
                if (it->s <= a && b <= it->e){
                    //printf("found existing range %d %d %d\n",it->s,it->e,it->t);
                    ans[i] += i+1-it->t;
                }
            }
        }
    }
    solve(0, ev.size()-1);
    for (int i = 0; i < q; i++){
        if (ans[i] != -1) printf("%d\n",ans[i]);
    }


}

Compilation message (stderr)

street_lamps.cpp: In function 'void solve(int, int)':
street_lamps.cpp:63:15: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   63 |     for (auto x : up){
      |               ^
street_lamps.cpp:66:15: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   66 |     for (auto x : qu){
      |               ^
street_lamps.cpp:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<evt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         while (i < up.size() && up[i].s <= Q.s){
      |                ~~^~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     scanf("%d%d", &n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     scanf("%s",str+1);
      |     ~~~~~^~~~~~~~~~~~
street_lamps.cpp:108:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |             int x; scanf("%d",&x);
      |                    ~~~~~^~~~~~~~~
street_lamps.cpp:138:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |             int a,b; scanf("%d%d",&a,&b);
      |                      ~~~~~^~~~~~~~~~~~~~

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