oj.uz

Submission #1020245

# Submission time Handle Problem Language Result Execution time Memory
1020245 2024-07-11T18:11:32 Z _8_8_ Street Lamps (APIO19_street_lamps) C++17
60 / 100
 5000 ms 51040 KB 
#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 = 0,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 = 0,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 = 0,int tr = q){
    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);
}
int gett(int l,int r,int v = 1,int tl = 0,int tr = q){
    if(l > r || tl > r || l > tr) return 0;
    if(tl >= l && tr <= r && tl == tr){
        return mx[v];
    }
    push(v);
    int tm = (tl + tr) >> 1;
    return gett(l,r,v+v,tl,tm) + gett(l,r,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});
        }
    }build();
    for(int i = n;i >= 1;i--){
        vector<pair<int,int>> o;
        t[i].push_back(q);
        for(int j = 0;j < (int)t[i].size() - 1;j += 2){
            o.emplace_back(t[i][j]+1,t[i][j + 1]);
        }
        for(auto [l,r]:o){
            upd(l,r,i);
            // cout << l << ' ' << r << ' ' << i <<  "x\n";
        }
        for(auto [r,id]:qr[i]){
            // for(int j = 1;j <= q;++j){
            //     cout << gett(j,j) << ' ';
            // }
            // cout << '\n';
            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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 6 ms 14428 KB Output is correct
4 Correct 10 ms 14428 KB Output is correct
5 Correct 6 ms 14428 KB Output is correct
6 Correct 6 ms 14344 KB Output is correct
7 Correct 6 ms 14684 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5065 ms 31816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 8 ms 14428 KB Output is correct
4 Correct 8 ms 14424 KB Output is correct
5 Correct 266 ms 42764 KB Output is correct
6 Correct 269 ms 45932 KB Output is correct
7 Correct 255 ms 48212 KB Output is correct
8 Correct 133 ms 48212 KB Output is correct
9 Correct 110 ms 28880 KB Output is correct
10 Correct 137 ms 35416 KB Output is correct
11 Correct 118 ms 35152 KB Output is correct
12 Correct 296 ms 51024 KB Output is correct
13 Correct 136 ms 48212 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Correct 6 ms 14552 KB Output is correct
3 Correct 7 ms 14428 KB Output is correct
4 Correct 6 ms 14876 KB Output is correct
5 Correct 294 ms 50896 KB Output is correct
6 Correct 266 ms 48976 KB Output is correct
7 Correct 231 ms 46664 KB Output is correct
8 Correct 200 ms 43092 KB Output is correct
9 Correct 205 ms 35412 KB Output is correct
10 Correct 185 ms 33720 KB Output is correct
11 Correct 207 ms 35412 KB Output is correct
12 Correct 193 ms 34128 KB Output is correct
13 Correct 201 ms 35408 KB Output is correct
14 Correct 183 ms 33904 KB Output is correct
15 Correct 312 ms 51040 KB Output is correct
16 Correct 117 ms 48384 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 6 ms 14428 KB Output is correct
4 Correct 10 ms 14428 KB Output is correct
5 Correct 6 ms 14428 KB Output is correct
6 Correct 6 ms 14344 KB Output is correct
7 Correct 6 ms 14684 KB Output is correct
8 Execution timed out 5065 ms 31816 KB Time limit exceeded
9 Halted 0 ms 0 KB -