Submission #859298

#	Time	Username	Problem	Language	Result	Execution time	Memory
859298		amogususus	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	2943 ms	115024 KiB

street_lamps

#pragma GCC optimize("Ofast,unroll-loops,inline")
#pragma GCC target("avx2,bmi,bmi2")
#include<bits/stdc++.h>
#define ll int
#define ld long double
#define pb push_back
#define prec fixed<<setprecision
#define endl '\n'
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
using namespace std;
const int maxN=3e5+69;
const int mod=998244353;
ll n,q;
string s;
vector<ll> BIT[maxN];
vector<ll> node[maxN];
void fakeUpdate(int x, int y) {
    for (; x <= n+1; x += x & -x)
        node[x].push_back(y);
}
void fakeGet(int x, int y) {
    for (; x ; x -= x & -x)
        node[x].push_back(y);
}
void update(int x, int yy, int val) {
    for (; x <= n+1; x += x & -x)
        for (int y = lower_bound(all(node[x]), yy) - node[x].begin() + 1; y <= node[x].size(); y += y & -y)
            BIT[x][y-1] += val;
}
int get(int x, int yy) {
    int res = 0;
    for (; x>0 ; x -= x & -x)
        for (int y = lower_bound(all(node[x]), yy) - node[x].begin() + 1; y > 0; y -= y & -y)
            res += BIT[x][y-1];
    return res;
}
vector<pll> query;
set<ll> off;
ll ffirst(ll x){return (off.lower_bound(x)==off.begin()?0:*(--off.lower_bound(x)));}
ll flast(ll x){return (off.upper_bound(x)==off.end()?n+1:(*off.upper_bound(x)));}
void Enter(){
    cin>>n>>q>>s;s=' '+s;string x=s;
    for(int i=1;i<=n;i++)if(s[i]=='0')off.insert(i);
    for(int i=1;i<=q;i++){
        string type;
        ll u,v;
        cin>>type>>u;
        if(type[0]=='t'){
            query.pb({u,0});
            ll ax=ffirst(u),ay=u,bx=u,by=flast(u);
            fakeUpdate(ax+1,ay+1);fakeUpdate(ax+1,by+1);fakeUpdate(bx+1,ay+1);fakeUpdate(bx+1,by+1);
            if(s[u]=='0')off.erase(u);
            else off.insert(u);
            s[u]='1'+'0'-s[u];
        } else cin>>v,query.pb({u,v}),fakeGet(u,v);
    }
    off.clear();s=x;
    for(int i=1;i<=n+1;i++)sort(all(node[i])),node[i].resize(unique(all(node[i]))-node[i].begin()),BIT[i].resize(node[i].size());
    for(int i=1;i<=n;i++)if(s[i]=='0')off.insert(i);
    for(int i=1;i<=q;i++){
        auto [u,v]=query[i-1];
        if(!v){
            ll ax=ffirst(u),ay=u,bx=u,by=flast(u);
            if(s[u]=='0')i=-i;
            update(ax+1,ay+1,i);update(ax+1,by+1,-i);update(bx+1,ay+1,-i);update(bx+1,by+1,i);
            if(s[u]=='0')i=-i;
            if(s[u]=='0')off.erase(u);
            else off.insert(u);
            s[u]='1'+'0'-s[u];
        } else cout<<get(u,v)+i*(v<=flast(u)&&ffirst(v)<u)<<endl;
    }
}
//amogus
signed main(){
    //open("PAINT");
    cin.tie(nullptr);ios_base::sync_with_stdio(NULL);
    //ll t=1;cin>>t;while(t--)
    Enter();
}

Compilation message (stderr)

street_lamps.cpp: In function 'void update(int, int, int)':
street_lamps.cpp:29:77: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for (int y = lower_bound(all(node[x]), yy) - node[x].begin() + 1; y <= node[x].size(); y += y & -y)
      |                                                                           ~~^~~~~~~~~~~~~~~~~

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