oj.uz

Submission #237439

# Submission time Handle Problem Language Result Execution time Memory
237439 2020-06-06T15:12:57 Z jhnah917 Street Lamps (APIO19_street_lamps) C++14
40 / 100
 211 ms 16992 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;

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]++, 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] == 1) sub2_ans[a] += i - sub2_now[a], sub2_now[a] = 0;
            else sub2_now[a] = i;
            sub2_stat[a] ^= 1;
        }else{
            cout << sub2_ans[a] + i - sub2_now[a] + 1 <<"\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;
    cin >> st;
    for(int i=1; i<=q; i++){
        string _op; int op, a, b;
        cin >> _op >> a;
        if(_op == "toggle") op = 1;
        else{
            op = 2; cin >> b;
            if(b - a != 1) is_2 = false;
        }
        qry[i] = {op, a, b};
    }
    if(is_2){
        sub2(); return 0;
    }
    sub3();
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 13 ms 12416 KB Output is correct
4 Correct 128 ms 16896 KB Output is correct
5 Correct 127 ms 16984 KB Output is correct
6 Correct 125 ms 16992 KB Output is correct
7 Correct 126 ms 16896 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 13176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 11 ms 12160 KB Output is correct
4 Correct 12 ms 12160 KB Output is correct
5 Correct 118 ms 12812 KB Output is correct
6 Correct 134 ms 13068 KB Output is correct
7 Correct 176 ms 13144 KB Output is correct
8 Correct 211 ms 14860 KB Output is correct
9 Correct 99 ms 12920 KB Output is correct
10 Correct 105 ms 13048 KB Output is correct
11 Correct 105 ms 13176 KB Output is correct
12 Correct 182 ms 13452 KB Output is correct
13 Correct 208 ms 14860 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct
2 Incorrect 11 ms 12160 KB Output isn't correct
3 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 11 ms 12160 KB Output is correct
3 Correct 13 ms 12416 KB Output is correct
4 Correct 128 ms 16896 KB Output is correct
5 Correct 127 ms 16984 KB Output is correct
6 Correct 125 ms 16992 KB Output is correct
7 Correct 126 ms 16896 KB Output is correct
8 Incorrect 85 ms 13176 KB Output isn't correct
9 Halted 0 ms 0 KB -