Submission #967492

#	Time	Username	Problem	Language	Result	Execution time	Memory
967492		socpite	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	3759 ms	181616 KiB

street_lamps

#include<bits/stdc++.h>
using namespace std;

const int maxn = 3e5+10;

set<int> lpos, rpos;

int n, q;
vector<int> pfw[maxn];
vector<long long> FW[maxn];
int a[maxn], org[maxn];
int U[maxn], V[maxn], ty[maxn];

void fadd(int x, int y, bool type, int t){
    for(x; x <= n+1; x+=x&(-x)){
        if(!type)pfw[x].push_back(y);
        else for(int idx = lower_bound(pfw[x].begin(), pfw[x].end(), y) - pfw[x].begin(); idx < pfw[x].size(); idx += idx&(-idx))FW[x][idx]+=t;
    }
}

long long query(int x, int y){
    long long re = 0;
    for(x; x > 0; x-=x&(-x)){
        for(int idx = upper_bound(pfw[x].begin(), pfw[x].end(), y) - pfw[x].begin() - 1; idx > 0; idx -= idx&(-idx))re += FW[x][idx];
    }
    return re;
}

void fadd_range(int a, int b, bool type, int t){
    // cout << "SUS " << a << " " << b << " " << t << endl;
    fadd(a, a, type, t);
    fadd(a, b+1, type, -t);
    fadd(b+1, a, type, -t);
    fadd(b+1, b+1, type, t);
}

void new_range(int l, int r, int type, int t){
    int fr = *prev(rpos.lower_bound(l)), fl = *lpos.upper_bound(r); 
    fadd_range(fr+1, fl, type, t);
    fadd_range(fr+1, l, type, -t);
    fadd_range(r+1, fl, type, -t);
    lpos.insert(l);
    rpos.insert(r);
}

void change_l(int l_old, int l_new, int type, int t){
    int fr = *prev(rpos.lower_bound(l_old));
    fadd_range(fr+1, l_old, type, t);
    fadd_range(fr+1, l_new, type, -t);
    lpos.erase(l_old);
    lpos.insert(l_new);
}

void change_r(int r_old, int r_new, int type, int t){
    int fl = *lpos.upper_bound(r_old);
    fadd_range(r_old+1, fl, type, t);
    fadd_range(r_new+1, fl, type, -t);
    rpos.erase(r_old);
    rpos.insert(r_new);
}

void del_range(int l, int r, int type, int t){
    int fr = *prev(rpos.lower_bound(l)), fl = *lpos.upper_bound(r); 
    fadd_range(fr+1, fl, type, -t);
    fadd_range(fr+1, l, type, t);
    fadd_range(r+1, fl, type, t);
    lpos.erase(l);
    rpos.erase(r);
}

void turn_on(int pos, bool type, int t){
    if(!a[pos-1] && !a[pos+1])new_range(pos, pos, type, t);
    else if(a[pos-1] && !a[pos+1])change_r(pos-1, pos, type, t);
    else if(!a[pos-1] && a[pos+1])change_l(pos+1, pos, type, t);
    else {
        fadd_range(pos, pos+1, type, t);
        lpos.erase(pos+1);
        rpos.erase(pos-1);
    }
}

void turn_off(int pos, bool type, int t){
    if(!a[pos-1] && !a[pos+1])del_range(pos, pos, type, t);
    else if(a[pos-1] && !a[pos+1])change_r(pos, pos-1, type, t);
    else if(!a[pos-1] && a[pos+1])change_l(pos, pos+1, type, t);
    else {
        fadd_range(pos, pos+1, type, -t);
        lpos.insert(pos+1);
        rpos.insert(pos-1);
    }
}

void toggle(int pos, bool type, int t){
    // cout << "TOGGLE " << pos << endl;
    if(a[pos])turn_off(pos, type, t);
    else turn_on(pos, type, t);
    a[pos]^=1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    a[0] = org[0] = 1;
    a[n+1] = org[n+1] = 1;
    for(int i = 1; i <= n; i++){
        char x;
        cin >> x;
        a[i] = (x-'0')^1;
        org[i] = a[i];
    }
    int last = -1;
    for(int i = 0; i <= n+1; i++){
        if(!a[i]){
            if(a[i-1]){
                lpos.insert(last);
                rpos.insert(i-1);
                last = -1;
            }
        }
        else if(last == -1)last = i;
    }
    lpos.insert(last);
    rpos.insert(n+1);
    for(int i = 0; i < q; i++){
        string str;
        cin >> str;
        if(str == "query"){
            ty[i] = 1;
            cin >> U[i] >> V[i];
        }
        else {
            cin >> V[i];
            toggle(V[i], 0, 0);
        }
    }
    lpos.clear();
    rpos.clear();
    last = -1;
    for(int i = 0; i <= n+1; i++){
        a[i] = org[i];
        if(!a[i]){
            if(a[i-1]){
                lpos.insert(last);
                rpos.insert(i-1);
                last = -1;
            }
        }
        else if(last == -1)last = i;
    }
    lpos.insert(last);
    rpos.insert(n+1);
    for(int i = 1; i <= n+1; i++){

        pfw[i].push_back(0);
        sort(pfw[i].begin(), pfw[i].end());
        pfw[i].erase(unique(pfw[i].begin(), pfw[i].end()), pfw[i].end());
        FW[i].assign(pfw[i].size(), 0);

    }
    for(int i = 0; i < q; i++){
        // cout << i << endl;
        // for(int j = 1; j <= n; j++)cout << a[j] << " ";
        // cout << endl;
        // for(auto v: lpos)cout << v << " ";
        // cout << endl;
        // for(auto v: rpos)cout << v << " ";
        if(!ty[i]){
            toggle(V[i], 1, i+1);
        }
        else {
            long long ans = query(U[i], V[i]);
            if(U[i] >= *rpos.begin() + 1){
                int fr = *prev(rpos.lower_bound(U[i])), fl = *lpos.upper_bound(fr);
                if(fr+1 <= U[i] && V[i] <= fl)ans += i+1;
            }
            cout << ans << "\n";
        }
    }
    

}

Compilation message (stderr)

street_lamps.cpp: In function 'void fadd(int, int, bool, int)':
street_lamps.cpp:15:9: warning: statement has no effect [-Wunused-value]
   15 |     for(x; x <= n+1; x+=x&(-x)){
      |         ^
street_lamps.cpp:17:95: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         else for(int idx = lower_bound(pfw[x].begin(), pfw[x].end(), y) - pfw[x].begin(); idx < pfw[x].size(); idx += idx&(-idx))FW[x][idx]+=t;
      |                                                                                           ~~~~^~~~~~~~~~~~~~~
street_lamps.cpp: In function 'long long int query(int, int)':
street_lamps.cpp:23:9: warning: statement has no effect [-Wunused-value]
   23 |     for(x; x > 0; x-=x&(-x)){
      |         ^

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