oj.uz

Submission #237833

# Submission time Handle Problem Language Result Execution time Memory
237833 2020-06-09T01:13:00 Z jhnah917 Street Lamps (APIO19_street_lamps) C++14
60 / 100
 209 ms 23436 KB 
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
 
struct Query{
    int op, a, b;
    Query(int op, int a, int b) : op(op), a(a), b(b) {}
    Query() : Query(0, 0, 0) {}
};
 
int n, q;
string st;
Query qry[303030];
 
void sub1_floyd(int a[111][111][111], int b){
    for(int i=1; i<=n+1; i++) for(int j=1; j<=n+1; j++) a[i][j][b+1] = a[i][j][b];
    for(int k=1; k<=n+1; k++) for(int i=1; i<=n+1; i++) for(int j=1; j<=n+1; j++){
        if(a[i][k][b] && a[k][j][b]) a[i][j][b] = 1;
    }
}
 
int sub1_ans[111][111][111] = {0};
void sub1(){
    string s; cin >> s;
    for(int i=1; i<=n; i++){
        if(s[i-1] == '1') sub1_ans[i][i + 1][0] = 1;
    }
    sub1_floyd(sub1_ans, 0);
    for(int i=1; i<=q; i++){
        string op; int a, b; cin >> op;
        if(op == "toggle"){
            cin >> a;
            sub1_ans[a][a + 1][i] ^= 1;
            sub1_floyd(sub1_ans, i);
        }else{
            cin >> a >> b;
            int cnt = 0;
            for(int j=0; j<i; j++) cnt += sub1_ans[a][b][j];
            cout << cnt << "\n";
            sub1_floyd(sub1_ans, i);
        }
    }
}
 
int sz = 1 << 19;
struct Sub3_Seg{
    int tree[1 << 20][2];
    Sub3_Seg(){
        for(int i=0; i<(1<<20); i++){
            tree[i][0] = -1; tree[i][1] = 0;
        }
    }
    void update(int x, int v){
        x |= sz; tree[x][0] = v; tree[x][1] = 1;
        while(x >>= 1){
            tree[x][0] = max(tree[x << 1][0], tree[x << 1 | 1][0]);
            tree[x][1] = tree[x << 1][1] + tree[x << 1 | 1][1];
        }
    }
    int query(int l, int r){
        int range = r - l + 1;
        l |= sz; r |= sz; int ret = 0, sum = 0;
        while(l <= r){
            if(l & 1) sum += tree[l][1], ret = max(ret, tree[l][0]), l++;
            if(~r & 1) sum += tree[r][1], ret = max(ret, tree[r][0]), r--;
            l >>= 1; r >>= 1;
        }
        if(sum != range) return -1;
        return ret;
    }
} sub3seg;

int sub3_chk[303030];
void sub3(){
    string s = st;
    for(int i=1; i<=n; i++){
        if(s[i-1] == '1') sub3seg.update(i, 0);
    }
    for(int i=1; i<=q; i++){
        int op = qry[i].op, a = qry[i].a, b = qry[i].b;
        if(op == 1){
            cin >> a;
            sub3seg.update(a, i);
        }else{
            cin >> a >> b;
            int t = sub3seg.query(a, b-1);
            if(t == -1) cout << 0 << "\n";
            else cout << i - t << "\n";
        }
    }
}
 
int sub2_ans[303030], sub2_now[303030], sub2_stat[303030];
void sub2(){
    string s = st;
    for(int i=1; i<=n; i++){
        if(s[i-1] == '1') sub2_now[i] = 0, sub2_stat[i] = 1;
    }
    for(int i=1; i<=q; i++){
        int op = qry[i].op, a = qry[i].a;
        if(op == 1){
            if(sub2_stat[a]) sub2_ans[a] += i - sub2_now[a];
            sub2_now[a] = i; sub2_stat[a] ^= 1;
        }else{
            int ans = sub2_ans[a] + (i - sub2_now[a]) * sub2_stat[a];
            cout << ans << "\n";
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> q;
    if(n <= 100 && q <= 100){
        sub1(); return 0;
    }
 
    bool is_2 = true, is_3 = true;
    cin >> st;
    for(int i=1; i<=q; i++){
        string _op; int op, a, b;
        cin >> _op >> a;
        if(_op == "toggle"){
            op = 1;
            if(sub3_chk[a]) is_3 = false;
            else sub3_chk[a] = true;
	}
        else{
            op = 2; cin >> b;
            if(b - a != 1) is_2 = false;
        }
        qry[i] = {op, a, b};
    }
    if(is_2){
        sub2(); return 0;
    }
    if(is_3){
        sub3(); return 0;
    }
    exit(-1);
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct
2 Correct 12 ms 12160 KB Output is correct
3 Correct 12 ms 12416 KB Output is correct
4 Correct 133 ms 17016 KB Output is correct
5 Correct 126 ms 17016 KB Output is correct
6 Correct 133 ms 17016 KB Output is correct
7 Correct 128 ms 17016 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 16248 KB Output is correct
2 Correct 95 ms 16632 KB Output is correct
3 Correct 101 ms 17232 KB Output is correct
4 Correct 120 ms 23436 KB Output is correct
5 Correct 128 ms 22668 KB Output is correct
6 Correct 114 ms 23180 KB Output is correct
7 Correct 136 ms 19464 KB Output is correct
8 Correct 141 ms 23180 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12288 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 11 ms 12288 KB Output is correct
4 Correct 11 ms 12160 KB Output is correct
5 Correct 115 ms 18312 KB Output is correct
6 Correct 176 ms 18956 KB Output is correct
7 Correct 181 ms 19724 KB Output is correct
8 Correct 207 ms 20872 KB Output is correct
9 Correct 102 ms 15864 KB Output is correct
10 Correct 105 ms 16120 KB Output is correct
11 Correct 121 ms 16376 KB Output is correct
12 Correct 190 ms 19340 KB Output is correct
13 Correct 209 ms 20876 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 12160 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct
2 Correct 12 ms 12160 KB Output is correct
3 Correct 12 ms 12416 KB Output is correct
4 Correct 133 ms 17016 KB Output is correct
5 Correct 126 ms 17016 KB Output is correct
6 Correct 133 ms 17016 KB Output is correct
7 Correct 128 ms 17016 KB Output is correct
8 Correct 90 ms 16248 KB Output is correct
9 Correct 95 ms 16632 KB Output is correct
10 Correct 101 ms 17232 KB Output is correct
11 Correct 120 ms 23436 KB Output is correct
12 Correct 128 ms 22668 KB Output is correct
13 Correct 114 ms 23180 KB Output is correct
14 Correct 136 ms 19464 KB Output is correct
15 Correct 141 ms 23180 KB Output is correct
16 Correct 11 ms 12288 KB Output is correct
17 Correct 11 ms 12160 KB Output is correct
18 Correct 11 ms 12288 KB Output is correct
19 Correct 11 ms 12160 KB Output is correct
20 Correct 115 ms 18312 KB Output is correct
21 Correct 176 ms 18956 KB Output is correct
22 Correct 181 ms 19724 KB Output is correct
23 Correct 207 ms 20872 KB Output is correct
24 Correct 102 ms 15864 KB Output is correct
25 Correct 105 ms 16120 KB Output is correct
26 Correct 121 ms 16376 KB Output is correct
27 Correct 190 ms 19340 KB Output is correct
28 Correct 209 ms 20876 KB Output is correct
29 Runtime error 12 ms 12160 KB Execution failed because the return code was nonzero
30 Halted 0 ms 0 KB -