Submission #494284

#	Time	Username	Problem	Language	Result	Execution time	Memory
494284		teee	Street Lamps (APIO19_street_lamps)	C++14	0 / 100	144 ms	116884 KiB

street_lamps

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
struct seg{
    struct node{
        int l,r;
        int val;
    };
    vector<node> tree;
    void init(){
        tree.push_back({0,0,0});
        tree.push_back({0,0,0});
    }
    void insert(int n,int s,int e,int t,int diff){
        tree[n].val+=diff;
        int mid=s+e>>1;
        if(diff<=mid){
            if(!tree[n].l){
                tree[n].l=tree.size();
                tree.push_back({0,0,diff});
                return;
            }insert(tree[n].l,s,mid,t,diff);
        }else{
            if(!tree[n].r){
                tree[n].r=tree.size();
                tree.push_back({0,0,diff});
                return;
            }insert(tree[n].r,mid+1,e,t,diff);
        }
    }
    int query(int n,int s,int e,int l,int r){
        if(!n||!tree[n].val||e<l||r<s)return 0;
        int mid=s+e>>1;
        return query(tree[n].l,s,mid,l,r)+query(tree[n].r,mid+1,e,l,r);
    }
};
seg tree[1048564];
int N;
void update(int n,int s,int e,int t,int k,int diff){
    if(e<t||t<s)return;
    tree[n].insert(1,1,N,k,diff);
    if(s==e)return;
    int mid=s+e>>1;
    update(n<<1,s,mid,t,k,diff);
    update(n<<1|1,mid+1,e,t,k,diff);
}
int query(int n,int s,int e,int l,int r,int ll,int rr){
    if(e<l||r<s)return 0;
    if(l<=s&&e<=r){
        int t=tree[n].query(1,1,N,ll,rr);
        return t;
    }
    int mid=s+e>>1;
    return query(n<<1,s,mid,l,r,ll,rr)+query(n<<1|1,mid+1,e,l,r,ll,rr);
}map<int,pair<int,int>> t;
string arr;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n,q,b,c;
    cin>>n>>q>>arr;N=n;
    for(int i=1;i<1048564;i++)tree[i].init();
    arr='0'+arr+'0';
    int w=0;
    for(int i=1;i<arr.length();i++){
        if(arr[i-1]=='1'&&arr[i]=='0'){
            t.insert({w,{i-1,0}});
        }if(arr[i-1]=='0'&&arr[i])w=i;
    }
    string a;
    for(int i=1;i<=q;i++){
        cin>>a>>b;
        if(a[0]=='q'){
            cin>>c;c--;
            int res=0;
            auto e=t.upper_bound(b);
            if(e!=t.begin()&&c<=prev(e)->second.first)res+=i-prev(e)->second.second;
            res+=query(1,1,n,1,b,c,n);
            cout<<res<<'\n';
        }else{
            if(arr[b]=='1'){
                auto e=prev(t.upper_bound(b));
                update(1,1,n,e->first,e->second.first,i-e->second.second);
                if(e->first!=b){
                    t.insert({e->first,{b-1,i}});
                }if(e->second.first!=b){
                    t.insert({b+1,{e->second.first,i}});
                }t.erase(e);arr[b]='0';
            }else{
                if(arr[b-1]=='1'&&arr[b+1]=='1'){
                    auto e=t.lower_bound(b);
                    update(1,1,n,e->first,e->second.first,i-e->second.second);
                    int E=e->second.first;
                    auto e2=prev(e);
                    update(1,1,n,e2->first,e2->second.first,i-e2->second.second);
                    int S=e2->first;
                    t.erase(e);t.erase(e2);
                    t.insert({S,{E,i}});
                }else if(arr[b-1]=='1'){
                    auto e2=prev(t.lower_bound(b));
                    update(1,1,n,e2->first,e2->second.first,i-e2->second.second);
                    int S=e2->first;
                    t.erase(e2);
                    t.insert({S,{b,i}});
                }else if(arr[b+1]=='1'){
                    auto e=t.lower_bound(b);
                    update(1,1,n,e->first,e->second.first,i-e->second.second);
                    int E=e->second.first;
                    t.erase(e);
                    t.insert({b,{E,i}});
                }else{
                    t.insert({b,{b,i}});
                }arr[b]='1';
            }
        }
    }
}

Compilation message (stderr)

street_lamps.cpp: In member function 'void seg::insert(int, int, int, int, int)':
street_lamps.cpp:18:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |         int mid=s+e>>1;
      |                 ~^~
street_lamps.cpp: In member function 'int seg::query(int, int, int, int, int)':
street_lamps.cpp:35:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         int mid=s+e>>1;
      |                 ~^~
street_lamps.cpp: In function 'void update(int, int, int, int, int, int)':
street_lamps.cpp:45:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |     int mid=s+e>>1;
      |             ~^~
street_lamps.cpp: In function 'int query(int, int, int, int, int, int, int)':
street_lamps.cpp:55:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |     int mid=s+e>>1;
      |             ~^~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i=1;i<arr.length();i++){
      |                 ~^~~~~~~~~~~~~

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