Submission #1020224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020224		_8_8_	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	5055 ms	34612 KiB

street_lamps

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

typedef long long ll;
const int  N = 3e5 + 20, MOD = (int)1e9+7;

int n,q;
vector<int> t[N];
vector<pair<int,int>> qr[N];
int mn[N * 4],mx[N * 4],mod[N*4];
void assign(int v,int val){
    mx[v] = mn[v] = mod[v] = val;
}
void build(int v = 1,int tl = 1,int tr = q){
    mx[v] = mn[v] = (int)1e9;
    if(tl == tr) return;
    int tm = (tl + tr) >> 1;
    build(v+v,tl,tm);
    build(v+v+1,tm+1,tr);
}
void push(int v){
    if(mod[v]){
        assign(v+v,mod[v]);
        assign(v+v+1,mod[v]);
        mod[v]=0;
    }
}
void upd(int l,int r,int val,int v = 1,int tl = 1,int tr = q){
    if(l > r || tl > r || l > tr) return;
    if(tl >= l && tr <= r){
        assign(v,val);
    }else{
        push(v);
        int tm = (tl + tr) >> 1;
        upd(l,r,val,v+v,tl,tm);
        upd(l,r,val,v+v+1,tm+1,tr);
        mx[v] = max(mx[v + v],mx[v + v + 1]);
        mn[v] = min(mn[v + v],mn[v +v + 1]);
    }
}
int get(int l,int r,int val,int v = 1,int tl = 1,int tr = n){
    if(l > r || tl > r || l > tr || mn[v] > val) return 0;
    if(tl >= l && tr <= r && mx[v] <= val){
        return tr - tl + 1;
    }
    push(v);
    int tm = (tl + tr) >> 1;
    return get(l,r,val,v+v,tl,tm) + get(l,r,val,v+v+1,tm+1,tr);
}
ll res[N];
void test(){
    cin >> n >> q;
    for(int i = 1;i <= n;i++){
        char x;
        cin >> x;
        if(x == '0'){
            t[i].push_back(0);
        }
    }
    for(int i = 1;i <= q;i++){
        res[i] = -1;
        string tp;
        cin >> tp;
        if(tp == "toggle"){
            int a;
            cin >> a;
            t[a].push_back(i);
        }else{
            int l,r;
            cin >> l >> r;
            --r;
            qr[l].push_back({r,i});
        }
    }
    for(int i = n;i >= 1;i--){
        vector<pair<int,int>> o;
        t[i].push_back(q + 1);
        for(int j = 0;j < (int)t[i].size() - 1;j += 2){
            o.emplace_back(t[i][j],t[i][j + 1] - 1);
        }
        for(auto [l,r]:o){
            upd(l,r,i);
        }
        for(auto [r,id]:qr[i]){
            res[id] = id - get(1,id,r);
        }
    }
    for(int i = 1;i <= q;i++){
        if(res[i] != -1){
            cout << res[i] << '\n';
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--){
        test();
    }
}

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